Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-optimization]

Discrete optimization is a branch of optimization in applied mathematics and computer science. As opposed to continuous optimization, some or all of the variables used in a discrete mathematical program are restricted to be discrete variables—that is, to assume only a discrete set of values, such as the integers. (Def: http://en.m.wikipedia.org/wiki/Discrete_optimization)

1
vote
0answers
24 views

Conjecture about smallest grammar problem.

Given an input string $s \in \Sigma^*$, we say $t \leqslant s$ if $t \in \Sigma^*$, and for some $\mu, \nu \in \Sigma^*$ we have $\mu t \nu = s$. In other words, $t$ is a substring of $s$. Now ...
-1
votes
0answers
25 views

Find matrix $\mathbf{C}$ and its factorization of basic operations such that $(a,b)\mathbf C=(1,0)$ and gcd$(a,b)=1$.

It's true that Hermite normal form can be computed in polynomial time for any integer matrix. However I had a question regarding how this can be expressed in terms of elementary matrix operations for ...
1
vote
1answer
68 views

$A_1,A_2,…,A_k\subseteq \{1,2,…,11\}$ are such that for any three of them at least two are not comparable by inclusion. What is a maximum of $k$?

Say $A_1,A_2,...,A_k\subseteq \{1,2,...,11\}$ are such a distinct sets that for any three of them at least two are not comparable by inclusion. What is a maximum of $k$? I'v got idea for this problem ...
1
vote
0answers
26 views

Maximum number of triangles given fixed number of edges

Consider all graphs with E many edges. The question is to find the maximum number of triangles such a graph can have. The answer is $O(E^{1.5})$ and the maximum occurs with it’s a clique. Now my ...
1
vote
1answer
41 views

Selecting elements from overlapping sets in any order without repetition

(there are examples below in this question, which probably explain it all better) Consider a finite set $R = \{1, 2, ..., N\}$ and a tuple of sets $Q = (S_1, S_2, ..., S_M)$, which are possibly non-...
0
votes
0answers
22 views

How to recognize an ARMA process? [migrated]

By looking at the autocovariance, how could you recognise what discrete model (MA(q), AR(p), or ARMA(p,q)) is more appropriate to describe your data?
0
votes
1answer
96 views

How to solve the following combinatorial optimization problem?

Is there some efficient method to solve the following optimization problem? If $x_i$ is in a continuous set, is there some efficient method? Thanks. $\min$ $x_1+x_2+\dots+x_n$ subject to: $a_1\log ...
6
votes
1answer
43 views

Minimum number of rectangles to cover diagonal-free grid

I'm trying to figure out the minimum number of rectangles required to cover an $n \times n$ grid, minus the diagonal. What this is means is the following: Suppose we have an $n \times n$ grid, with ...
1
vote
2answers
40 views

Finding Lowest Elevation Path Between Two Points

Let's say I have a matrix of values that represent heights with function $f(x,y)$ and I am trying to find the "lowest value path" beween two points. So this would be the reverse of hill climbing, as ...
0
votes
1answer
25 views

Given $n$ vectors, find partitions with closest centroids

Given vectors $a_1, \dots, a_n\in \mathbb R^d$ where $n$ is even, I want to find partitions $I$ and $J$ of $[n]$ with $|I|=|J|=\frac n2$ to minimize $$\left\| \sum_{i\in I} a_i - \sum_{j\in J} a_j \...
0
votes
1answer
21 views

How to proceed when you have an invalid range in a sum?

this is my very first post here. I think this might be a really stupid question (sorry), but I just need to guarantee it. I have the following equation: $$F_i = \min_{i \ \leq \ j \ \leq \ q} \{\sum_{...
0
votes
0answers
18 views

Expensive combinatorial optimization of choice of subset from a large finite space

I have a fairly general question -- what's a good (gradient-free) approach to optimizing an expensive function whose input is a choice of subset from a large finite population? That is, I have a set ...
0
votes
0answers
23 views

Binary Polymatroid Optimization Problem

Let $\mathcal{N}$ denote the finite set $\{1, 2, \ldots, n\}$, and let $\mathcal{S}_j$ denote the set $\{1, 2, \ldots, j\}$; let $f\colon \mathcal{N} \to \mathbb{N}$ be nondecreasing, submodular and ...
0
votes
0answers
18 views

Infimum of $f(\theta)= -\sum_{i=1}^n (y_i - \alpha p(y_i|x;\theta)) \ln p(y_i|x) $

Suppose $y_1 = 1, y_2 = y_3 = ...=y_n = 0\ (n\geq2)$, and $\sum_{i=1}^np(y_i|x;\theta) = 1$, $0\leq p(y_i|x;\theta)\leq1$. Meanwhile $\alpha > 0$ is a constant. Let's define a function $$f(\theta)...
0
votes
1answer
41 views

Approximate function by stacking building blocks

I need some help with a 'generalised Lego problem': Given a function $f(x)\geq 0$ on an interval $[a,b]$, and a 'building block' function $p(x)\geq 0$ with compact support. The maximum of f shall be ...
1
vote
0answers
27 views

When are quadratic integer programs easy to solve? [duplicate]

Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to maximize $f$ on $N$. $f$ has the following form $$ f(n) = \sum_i A_i n_i -\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^...
0
votes
0answers
12 views

Deconvolution of accumulated values

Introduction I have an unknown function of time $f(t)$ that I would like to learn based on experimental observations. I have an observable $g(t)$, which, to the best of my knowledge, is given by the ...
2
votes
2answers
53 views

Minimum distance between sequence a and all permutations of another sequence b

Let $a$ and $b$ be finite sequences of length $n$, i.e. $a=(a_1,a_2,...,a_n), b=(b_1,b_2,...,b_n)$. I want to calculate the minimum of the distances (in an Lp norm) between $a$ and all permutations of ...
0
votes
0answers
21 views

Maximum weight matching with repeated nodes

We are given two sets of nodes $A$ and $B$ forming a graph where each element $x \in A$ can be connected with an element $y \in B$ with different possible weights. The graph can be explained in two ...
1
vote
0answers
15 views

Finding discrete solutions to inequality involving Exponential Integral

I want to identify the least natural number $n$ (of course, it suffices to solve this problem for the reals, and then take the floor) such that $$-c \text{Ei}\left(-e^{\frac{a-d}{c}} (n+1)\right)+a-...
0
votes
1answer
23 views

Count the number of unique elements in a vector by linear constraints (ILP)

Let $\mathbf{x}\in \{0,1\}^n$, be the objective variables of an ILP. Further, let $\mathbf{a} \in \mathbb{N}_{\geq 0}^n$ be a given random vector and $\mathbf{w} = \mathbf{x} \odot \mathbf{a}$ where ...
0
votes
0answers
17 views

Property of submodular non-decreasing function

Let $f:\mathcal{P}(N) \longrightarrow \mathbb{R}$ be a set function. $f$ is submodular if \begin{align} f(A) + f(B) &\geq f(A \cup B) + f(A \cap B) &\text{for all } A, B \in \mathcal{P}(N), \...
0
votes
0answers
12 views

Bus fleet requirement for transporting passengers/baggage between airport terminals

I am trying to determine the optimum number of buses required for loading and unloading of passengers/baggage. The buses perform following tasks: Transport terminating passengers and their carry on ...
0
votes
1answer
18 views

Ordering tours in a Euclidean TSP according to (strictly) increasing length

Let $H$ be the set of all Hamiltonian cycles on the complete graph $K_n$ associated with a set of $n \geq 4$ points $P$ in the plane where edge weights are defined using the Euclidean distance between ...
1
vote
0answers
41 views

How to find a spanning tree?

The question is: Describe how you can find a spanning tree for which (a) the product of the edge-costs is minimal (b) the maximum of the edge-costs is minimal Somebody has told me to use ...
0
votes
0answers
16 views

Is it possible to turn this into a (standard) integer convex knapsack problem?

I have found a solution algorithm for integer knapsack problems of the following form: $\max\limits_{x_j \in [l_j,u_j]} \sum_{j=1}^n f_j(x_j)$ such that $\sum_{j=1}^n g_j(x_j) \leq b$ ...
1
vote
0answers
25 views

Solving motion equations using linear programming

I'm trying to solve this physics problem using the Simplex method $$\text{Minimize}\qquad \int _0 ^T |f(t)|dt \qquad \text{subject to}\\ j(t) = j(0) + \int_0^t f(t)dt, \forall t \in [0,T] \\ m(t) = m(...
0
votes
1answer
21 views

Searching Solver for a convex seperable Integer programm

I have given a problem of the form $\min \sum_{j=1}^n f_j(x_j)$, s.t. $\sum_{j=1}^n g_j(x_j) \leq b$. Both the $g_j$ and $f_j$ are convex functions and $x_j$ are integer, so its a convex seperable ...
0
votes
0answers
31 views

Production time optimization model

I have a problem where I have 2 different types of raw-material. These materials can be processed in two different production-lines which take different amount of time, depending on raw material. ...
2
votes
1answer
122 views

What is the maximum value of $x^TAx$ subject to $x\in\{\pm1\}^n$?

Let $A \in \mathbb{R}^{n\times n}$ be symmetric and positive definite. What is the following maximum? $$\max_{x\in\{\pm1\}^n}x^T A x$$ My attempt: if all $a_{ij}\geq 0$, then \begin{equation} \...
0
votes
0answers
20 views

What are the directions of research in Numerical Optimization?

I have just begun reading in the field of Numerical Optimization. Are people trying to invent new Algorithms? or proving the convergence of Heuristic Algorithms? and what else? What are the tools a ...
0
votes
1answer
65 views

Maximise $z = \frac{y}{2x+2y}+\frac{50-y}{200-2x-2y}$ given that $x+y$ is non zero and $x+y<100$. Also, $x\leq50$ and $y\leq50$ and non-negative.

Z is actually a probability function. I am finding where the probability is maximized. But I could find no way how to maximize this function. Original question is as follows: Mr A wants to join a ...
4
votes
2answers
103 views

What is the biggest possible sum $|X_1-X_2|+|X_2-X_3|+\cdots+|X_{n-1}-X_n|$ where $X_1,X_2,\cdots,X_n$ are first $n$ positive integers?

What is the biggest possible sum $|X_{1}-X_{2}|+|X_{2}-X_{3}|+\cdots+|X_{n-1}-X_{n}|$ where $X_{1},X_{2},\cdots,X_{n}$ are first $n$ positive integers?
3
votes
1answer
36 views

Limitations of SDP

Semidefinite programming seems to be a very powerful tool to approach NP-hard optimisation problems, for example in discrete optimisation and there are some very interesting results (like the max cut ...
0
votes
0answers
8 views

Applications of high mean escape time subgraphs

I am learning about algorithms for finding subgraphs with high mean escape time, and I am wondering if someone could enlighten me on what applications there are for such a task. Applications to either ...
0
votes
0answers
22 views

Discretization of PDE

Set $\Omega = (0,1)$. (*) I have given $\int_{\Omega} e^x u' v' = \int_{\Omega} fv $ for all $v \in H_0^1(\Omega)$. I found the solution $u \in H_0^1(\Omega)$: $u = -c_1 e^{-x} + c_2 - e^{-x} $ for ...
0
votes
0answers
15 views

need help (or literature) with an optimization problem

Hello, during my master thesis i came across an optimization problem which essentially has the form: $\min_{(n,L) \in \mathbb{N}^2} n C_1 h^{-rL}$ such that $C_2h^{q_1 L}+\frac{C_3}{n^{1-\frac{1}...
0
votes
0answers
33 views

Trying to formulate optimization problems as a linear program (LP) or a quadratic program (QP)

I'm trying to formulate and determine the variables, objective, and constraints for the minimization problem $\min_\vec{x}f(\vec{x})$ for the following functions $f \in$ ($q,r,s,t$) as linear program (...
0
votes
0answers
24 views

Show that the set of nonpositive rational numbers is countable [duplicate]

Can someone show that the set of nonpositive rational numbers is countable ?
0
votes
2answers
39 views

How to find the modules of a big number with a big powe ?? [closed]

How to find the modulus of a big number with a big power? Such as $2222^{5555}$ or $5555^{2222}$ (mod 7)?
1
vote
0answers
58 views

Fock-space-related combinatorial problem

I don't really know how to approach a combinatorial problem arising from the physics context. Here's the setting. The state of a bosonic system in ${(1+1)}$ dimensions is described by a vector of the ...
0
votes
0answers
18 views

Symmetry breaking in VRP families problem

Hollo everybody I have a question about symmetry in VRP problem. What is the meaning of symmetry and asymmetry condition in the optimization problem and could you pls tell me, how can we break it from ...
0
votes
1answer
29 views

- Optimization - Standard Grid Search

I'm struck into an portfolio opt. problem and the paper I'm replicating (or, better, trying to) is using a "Standard Grid Search". Since I never encountered it before, I would like to ask you about: ...
0
votes
0answers
43 views

Combination of unique subsets - Combo menu problem

I have a food menu with multiple categories and several options in each one. The combo meal selects one from each category. I want to find how many combinations I can make from this menu, but with the ...
1
vote
1answer
32 views

Converting a supermodular optimization problem to submodular optimization

A constrained concave maximization problem can be converted to a constrained convex minimization problem by negating the objective function and keeping the constraints intact. But in case of ...
0
votes
0answers
31 views

Integer Optimization with a specific form ($\sum f_{ij} (x_i,x_j)$)

I encountered a series of integer optimization problems that share a similar structure. The integer variables are $(x_1,x_2,\cdots,x_n)$, where each $x_i$ is non-negative. The objective function $f$ ...
0
votes
1answer
23 views

Optimizing in role-playing games [closed]

I know the answer to this must be out there somewhere, because people play a lot of games (online or otherwise) that do this sort of thing, but I don't know what words to search for. (The existence of ...
1
vote
0answers
33 views

Under what condition, the optimal solution of assignment problem is unique?

Is there any conditions that can make the optimal solution of a assignment problem unique? I know if there is no conditions on the cost matrix, it is not guaranteed to have a unique solution. (e.g. ...
-1
votes
1answer
41 views

definition of a set function?

Assuming $A$ is a set, then $F: A\rightarrow \mathbb{R}$. We can define $F(\varnothing) = 0$. But what is $F(x)$ for $x\notin A$? Is it 0?
0
votes
0answers
12 views

Submodular functions and roof duality

Is there a good online source to understand roof duality derivation and possibly a toy example coded in python? Not sure if the question is valid for this forum. I have searched a lot to find some ...