Questions tagged [integer-programming]

Integer programming regards optimization problems, where one seeks to find integer values for a set of unknowns, that optimizes the objective function. A common subset of this type of problems are integer linear programming problems, where all inequalities, equalities and the objective function are linear in the unknowns.

Filter by
Sorted by
Tagged with
1
vote
2answers
58 views

Integer linear programming (ILP) formulation of connectivity of induced subgraph

Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but ...
0
votes
0answers
17 views

How do you refer to the feasible set of solutions to a mixed-integer program?

I frequently want to refer to the feasible set of solutions to a mixed integer programming instance. Is there a name for a subset of $\mathbb{R}^n\times\{0,1\}^m$ of the form $\{(x,a)| Ax + Ba\leq b\}$...
1
vote
1answer
112 views

Gröbner basis via integer programming

I have studied some papers related to solving integer programs via Gröbner bases. I wonder if the other way is possible or not — i.e., given any ideal, can we find the Gröbner basis by translating ...
0
votes
1answer
140 views

What are all the possibilities of $A$ s.t. $\det(A)=k$?

Suppose we have $A \in M_3(\Bbb N\cup\{0\})$ s.t. sum of the elements of each row is $k $ for some fixed $k\in \Bbb N\cup\{0\}$. What are all the possibilities of $A$ s.t. $\det(A)=k$? We can start ...
0
votes
1answer
56 views

How do I solve this integer programming problem with non convex constraints?

I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place. I have an optimization problem like this ...
5
votes
1answer
117 views

Is Binary Integer Linear Programming solvable in polynomial time?

The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...
0
votes
0answers
29 views

Feasibility Criteria in Integer Linear Programming

Consider an integer linear programming problem: For $A\in M(m, n, \mathbb{Z})$ and $b\in \mathbb{Z}^m$ find $x=(x_1,\ldots,x_n)^T\in \mathbb{Z}^n_{\geqslant0}$ such that $Ax=b$. Sometimes one ...
0
votes
1answer
74 views

Integer programming problem

I have an integer optimization problem with a non-linear function ($F(X)$) in the objective and one of the constraints. $F(X)=x_n^{i,j}\Big[\sum\limits_{\forall s\neq i}\sum\limits_{\forall m\in\...
1
vote
0answers
31 views

Modelling exact unions of polytopes in homogeneous case?

We can model disjunctions (note I am not looking for convex hull) of $t$ unbounded convex polyhedra given by $A^{(1)}x^{(1)}\leq b^{(1)}$,$\dots$,$A^{(t)}x^{(t)}\leq b^{(t)}$ exactly with a mixed ...
1
vote
0answers
66 views

Mixed integer formulation of union of polytopes?

Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
0
votes
1answer
108 views

Convex integer program with totally unimodular constraints

Suppose I have a convex (nonlinear) integer program with totally unimodular linear constraints. What are sufficient conditions one can impose on the convex objective function such that relaxing the ...
1
vote
1answer
71 views

Algorithm for (binary) integer programming

I am looking for an algorithm that can solve the following (binary) integer programming problem. The problem description is given below: \begin{align*} &\max\sum_{i\in I}\sum_{j\in J}g_{ij}w_{ij} \...
6
votes
0answers
220 views

Efficient solutions to general Bézout’s identity $a_1 b_1 + \dots + a_n b_n = 1$

Suppose I have integers $a_1, \dots, a_n$ which are coprime, meaning that $$a_1 b_1 + \dots + a_n b_n = 1$$ has a solution in integers $b_1, \dots, b_n$. I would like to get a bound saying ...
1
vote
0answers
34 views

Fast certficate of negativity for objective value of mixed-integer linear program

Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP) $$ \begin{split} f^* = &\max \; ...
1
vote
0answers
72 views

Smallest integer lattice point by box measure in a polytope?

Given an integer lattice $\mathcal L\subseteq\mathbb Z^n$ represented by basis $\mathcal B$ and an integer linear program $Ax\leq b$ where $x\in\mathbb Z^n$ is unknown with $A\in\mathbb Z^{m\times n}$ ...
2
votes
1answer
209 views

Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way [closed]

I need to emulate this sequence for a program: http://oeis.org/A025302 Stuff that I've taken into account: After finding the prime divisors of a number. I take any divisor as p and apply the ...
1
vote
1answer
147 views

Minimizing sum of ratio of linear functions (Sum of Linear Ratios Problem)

Given constants $c_i \in \mathbb{R}$ and $d_i \in \mathbb{R}$ and variables $x_i \in \mathbb{R}$, where $c_i > 0, d_i > 0, x_i > 0$ can we easily solve the following optimization problem: $$...
1
vote
0answers
84 views

When are quadratic integer programs “easy to solve”?

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)^...
1
vote
1answer
123 views

How good is the LP relaxation?

Consider the optimization problem \begin{align} \max_{x\in\mathbb{R}^n}~c^Tx~, \text{ s.t. } Ax=b,~x_i\in\{0,1\}~\forall i \end{align}where $c,b\in\mathbb{R}_{+}^n$ and $A\in\mathbb{R}_{+}^{n\times n}$...
4
votes
2answers
343 views

What are the definable sets in Skolem arithmetic?

Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets and quantifier free part corresponds to Integer Programming with linear inequalities ...
1
vote
0answers
90 views

How to solve such integer program problem?

Consider a $3$-tuple $(a,b,s)$ with $a,b\in\mathbb{Z}_+,s\in\mathbb{Q}_+$. Denote $ab-s$ by $\Delta$. Let $A$ be a positive number. What are the values of $A$ such that for any $(a,b,s)$ with $\Delta\...
1
vote
0answers
46 views

How to minimize n-polytope's bounding box with linear transformation?

I am working on an exact algorithm for integer linear programming for my master's thesis: $Ax\leq b, x \in \mathbb{Z}^n$ $cx\rightarrow min$ For my idea to work out, I need a guarantee that n-...
0
votes
1answer
142 views

Relax a rectangular linear assignment problem

I wonder if there is any literature on the following problem $$\begin{array}{ll} \underset{X \in \mathbb R^{m\times n}}{\text{minimize}} & \displaystyle\sum_{i,j} C_{i,j} X_{i,j}\\ \text{subject ...
1
vote
1answer
243 views

Feasibility Mixed integer Linear programming with quadratic constraints?

Consider the mixed integer program $$Ax\leq b$$ $$By\leq c$$ $$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer ...
-1
votes
2answers
89 views

On OR condition in Linear Programming with exponentially many constraints [closed]

Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
2
votes
1answer
55 views

Clarification on FPTAS optimization in a paper

In the abstract of this paper by Hildebrand, Weismantel & Zemmer it is stated that they provide an FPTAS for $$\min x'Qx$$ over a fixed dimension polyhedron when $Q$ has at most one negative or ...
1
vote
1answer
76 views

Convex integer programming on totally unimodular polytope?

If $$\min x'Qx + Rx$$ $$Ax\leq b$$ $$x\in\mathbb Z^n$$ is a quadratic program with $x'Qx$ is convex is there a polynomial time algorithm for this if $A$ is totally unimodular? In particular if we ask ...
0
votes
0answers
181 views

Finding a point in the relative interior of the convex hull of a set of integer-valued vectors

Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
2
votes
0answers
73 views

What does Lenstra's MILP do?

Honestly I do not understand why Lenstra's MILP is in $P$ if the number of integer dimensions is fixed. Here is what Lenstra says in 'http://people.csail.mit.edu/rrw/presentations/Lenstra81.pdf' in ...
1
vote
1answer
201 views

Bit complexity of Barvinok's algorithm

I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension. What exactly is this arithmetic complexity? ...
2
votes
1answer
136 views

On software for ILP

In 'Computational Experience with Lenstra's Algorithm' by L Gao, Y Zhang it is claimed that they have an implementation of Lenstra's fixed dimension integer programming algorithm. Is this available ...
0
votes
0answers
66 views

Discrete primal-duality in optimization

I would like to inquire about the existence of something perhaps similar to the duality theorem in the convex analysis or convex programming in the discrete setting. Here is a concrete example. Let $...
1
vote
2answers
147 views

Detection of gaps in binary vector through linear methods

Suppose I have a binary vector a = (0,1,1,1,0,0) of length $N$. I want to detect in a linear way whether a has any gaps in ...
4
votes
1answer
129 views

On necessary condition for no integer points in polytope

For a convex polytope $\mathcal K$ in $\Bbb R^n$ presented by $O(n^c)$ linear inequalities is it true that for $|\mathcal K\cap \Bbb Z^n|=0$ it is necessary that at least one axis of John's ellipsoid ...
3
votes
1answer
439 views

Under what conditions does an Integer Programming problem run in polynomial time?

Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...
2
votes
0answers
100 views

Gap in Successive minima on lattice spanned by rational and integer combination of integer vectors

We are given a rank $r$ matrix $B\in\Bbb Z^{k\times n}$ where $0\leq r\leq k\leq n$ holds. We have $$\mathcal L_\Bbb Z=\{uB\in\Bbb Z^n:u\in\Bbb Z^k\}\subseteq\mathcal L_\Bbb Q=\{uB\in\Bbb Z^n:u\in\...
2
votes
2answers
97 views

Integer points spanned by real, rational and integer combination of integer vectors

We are given a rank $r$ matrix $B\in\Bbb Z^{k\times n}$ where $0\leq r\leq k\leq n$ holds. We have $\mathcal L_\Bbb Z\subseteq \mathcal L_\Bbb Q\subseteq\mathcal L_\Bbb R$ where $$\mathcal L_\Bbb Z=\...
2
votes
0answers
73 views

Making a polyhedron integral by selecting value for a specific co-ordinate of constraint vector

I am currently trying to solve a binary integer programming(maximization) problem, where the first row of the constraint matrix corresponds to the constraints on the total number of 1's in the vector ...
2
votes
1answer
103 views

Feasibility of constrained multivariable diophantine equations

Let $d$ be day, $m$ be month and $y$ be year fields of a date. I want to find few dates of format $$(d^2\, mod\,\, 2 + (my + d^3) \,mod \,4) = 2$$ Is there a method to solve this type of equation or ...
5
votes
1answer
277 views

Maximize the determinant of Boolean combinations of positive definite matrices

I have the following optimization problem. $$\begin{array}{ll} \text{maximize} & \det \left(\sum^n_{i=1}z_i W_i \right)\\ \text{subject to} & \sum_{i=1}^n z_i = N\\ & z_i \in \{0,1\}\end{...
3
votes
2answers
602 views

Equality constraints in mixed-integer optimization

Suppose I have a linear mixed-integer optimization problem of the form $$MIP: min_{(x,y) \in \mathbb{R}^n \times \mathbb{Z}^m} c^\top x + d^\top y \hspace{0.2cm} \text{s.t.} \hspace{0.1cm} Ax+By \leq ...
0
votes
0answers
189 views

MIQP formulation in L0 norm optimization

Consider the L0 norm compressed sensing problem: $$\eqalign{ & \min \quad {x^T}Qx + {c^T}x + {\mu\left\| x \right\|_0} \cr & s.t:\quad Ax \le b \cr} $$ Suppose I do want to solve this ...
1
vote
1answer
203 views

Lot Sizing Problem: How to add these cuts efficiently

Consider the set of constraints of the uncapacitated lot sizing problem: $$ \{(x,s,y)\in \mathbb{R}^n_+ \times \mathbb{R}^n_+ \times \mathbb{B}^n \;|\;s_{t-1}+x_t = d_t+s_t,\; x_t \le My_t,\; t=1,\...
3
votes
0answers
91 views

Optimally placing rectangles with obstacles

I am struggling with a fairly simple and natural geometric optimization problem, but I have not been able to find an obvious canonical method for solving it: I am given a collection of $m$ axis-...
2
votes
1answer
99 views

Does this simple non-convex problem involving discrete phase shifts have an exact solution?

Let the optimization problem be \begin{equation} \max_{\phi_n} \left|\sum_{n=1}^N e^{i\phi_n} a_n \right|, \end{equation} where $a_n\in\mathbb{C}$ and the optimization variables have discrete phase ...
3
votes
2answers
225 views

Integer programming of free energy

Given $k$, $f(x) = e^{x_1}+e^{x_1+x_2}+\cdots+e^{x_1+x_2+\cdots+x_k},$ $x=(x_1,x_2,\ldots,x_k),$ where $x_i \in \{0,1\}$. We want to compute: $\inf_{x \neq y}|f(x)-f(y)|$ or a lower bound of $\inf_{x ...
0
votes
2answers
251 views

Lattice question

Consider a lattice $\mathcal{L} = \mathbb{Z}v_1 \oplus \ldots \oplus \mathbb{Z}v_l$ in $\mathbb{R}^n$ and let $S_0$ be the set of edges of the fundamental unit of $\mathcal{L}$. We call a region $X$ ...
0
votes
0answers
66 views

A seemingly easy integer programming question

Let $k, m \in \mathbb{Z}_{ > 1}$. Let $a \in \mathbb{Z}_{> 0}^m$ and $t \in \mathbb{Z}^k$. Let $\varepsilon = (\varepsilon_{i,j})_{1 \leq i \leq m \\1 \leq j \leq k}$ be a matrix with entries in ...
5
votes
0answers
100 views

Lattice paths in polytopes

Let $P$ be a polytope in $\mathbb{R}^n$. Let $A_ix = b_i$ be the defining equations of its codimension $1$ faces. Is there an algorithm or some kind of criterion to decide if the lattice points inside ...
6
votes
1answer
321 views

Existence of nonnegative solution in diophantine linear equations system with non negative coefficents

Given a Diophantine system of linear equations $Ax = b$, where $A \in \mathbb{N}^{m\times n}$ and $b\in\mathbb{N}^{m}$, is there a method to determine whether there exists a nonnegative solution $x\...