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
1answer
287 views

System of congruences

I have a system of $n$ congruences. the generic $m$_th congruence of the system ($m = 1,\dots,n$) is in the form: $(p_n\#)^2(\displaystyle\sum_{\substack{i=1\\i\neq m}}^n{\frac{x_iy_m}{p_ip_m}}+\...
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
2answers
307 views

basis of the lattice generated by the integer points inside a subspace of R^L

Consider $K$ linearly independent vectors $\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{a}_K \in \mathbb{Z}^L$, where $1 \leq K<L $. Hence, the span of $\lbrace\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{...
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,\...
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
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 ...
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}$ ...
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: $$...
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
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
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\...
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
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
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-...
8
votes
0answers
177 views

What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

The Tutte polynomial is a bivariate polynomial with positive integer coefficient which is a graph invariant and can be defined recursively. Evaluating it is $\#P$-complete even when restricted to (...
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 ...
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? ...
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
182 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
2answers
536 views

Reference Request for Integer factorization with LP/ILP

Have there been attempts to factor integers with Linear Programming? Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...
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 ...
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 $...
31
votes
4answers
3k views

Why are optimization problems often called “programs”?

Why are optimization problems often called programs? linear programming geometric programming convex programming Integer programming ...
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 ...
3
votes
0answers
2k views

0,1 solution to system of linear integer equations

I have the following problem: $A x = b$ where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively). $x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
6
votes
1answer
322 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\...
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 ...
6
votes
1answer
306 views

Is a Parametric Integer Linear Programming Problem eventually quasi-polynomial?

I will consider a family of Integer Linear Programs parametrized by a positive integer $t$. Let $\mathbf{x} = (x_1, \ldots, x_n)$ be the indeterminates. Let $A$ an $m$ by $n$ matrix whose elements ...
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 ...
3
votes
1answer
160 views

Separation of Anti-Hole Inequality

Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent. An induced subgraph $H$ of $G$ is called an odd-antihole ...
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{...