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.
77 questions with no upvoted or accepted answers
8 votes
0 answers
282 views
Complexity of integer programming with added predicates
A classical theorem in Integer Programming by Lenstra says that any integer system $$A x \le b$$ can be solved in polynomial time, where $A \in \mathbb{Z}^{m \times n}, x \in \mathbb{Z}^n, b \in \...
- 353
8 votes
0 answers
234 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 (...
- 25.7k
7 votes
0 answers
484 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 ...
- 4,232
5 votes
0 answers
311 views
Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$
Crossposted at Theoretical Computer Science SE A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$....
- 123
5 votes
0 answers
163 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 ...
- 501
4 votes
0 answers
123 views
Questions in number theory related to $NC$ and $P$-completeness
Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$. Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$. Euclidean algorithm solves both. My question is if either 1 or 2 is in ...
- 1
4 votes
0 answers
157 views
Choice of MIP (mixed integer programming) solver
I would start using MIP solver for the research on the tiling. I know (heard of) the open source solver jump: https://github.com/JuliaOpt/JuMP.jl and also the gold standard solver from IBM cplex. ...
- 877
4 votes
0 answers
436 views
Matching a binary matrix
Given a MxN 0-1 matrix D, with the property that both M and N are odd numbers its row sums and column sums in the $\mathbb{Z}_2$ field are all equal to the same number (0 or 1). How do we find M ...
- 167
4 votes
0 answers
266 views
Domination in Nice Lattices
Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions. Call a lattice ...
- 1,328
3 votes
0 answers
182 views
Why is this constrained quadratic-over-linear integer program separable?
Consider the following splitting problem. Given $Y$ balls of which $X\leqslant Y$ of them are blue balls. The goal is to split the balls by placing them in $K$ baskets based on the following quadratic-...
- 31
3 votes
0 answers
446 views
Hemisphere containing the maximum number of points scattered on a sphere
Consider a set of points $x_1, \ldots,x_n$ on $\mathbb{S}^{k-1}$ (the unit sphere in $\mathbb{R}^k$). The goal is finding the hemisphere which contains the maximum number of $x_i$'s. Basically, we ...
- 127
3 votes
0 answers
138 views
The matrix representation of an interval graph
It is well-known that many classes of graphs have matrix representations that can be written concisely. For example, The set of all directed acyclic graphs consists of binary matrices $x_{ij} \in \{...
- 4,131
3 votes
0 answers
68 views
Modular counting of integral points under sparse non-negativity
Given a polyhedron $$Ax\geq b$$ where every entry of $A,b$ are non-negative and $A\in\{0,1\}^{m\times n}$ and there are $O(1)$ (say $\leq8$) non-negative entries per row of $A$ is it possible to ...
- 1
3 votes
0 answers
147 views
Does Barvinok's algorithm apply to convex integer program?
Barvinok provided a counting algorithm to count number of integer solutions to integer linear program that runs in polynomial time if the number of integer variables is fixed. If we have convex ...
- 1,846
3 votes
1 answer
461 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,\...
- 225
3 votes
0 answers
122 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-...
- 4,131
3 votes
0 answers
181 views
The complexity of an optimization problem involving sum of binomial coefficients
I'm just new to this community. So please forgive me if the question is not properly asked. I would like to get the natural number e such that the following function can be minimized: $f(e)=\frac{b}{...
- 31
3 votes
0 answers
258 views
Lenstra's integer programming algorithm: Finding a lattice point “near the center”
I have already posted this question on the mathematics forum, but I suspect the question needs more detailed knowledge than most users have; please excuse the duplicate post. Any help is greatly ...
- 31
3 votes
0 answers
207 views
Reference request: how to find the k'th best solution to the 1-0 knapsack problem?
How do I find the k'th best solution to the 1-0 knapsack problem without finding the Top-k solutions? Is there any mathematical research that deals with the k'th best solutions to the mixed integer ...
- 319
3 votes
0 answers
52 views
About the partial expectation polynomials in the Interlacing-I paper and perfect matchings
I am thinking of the polynomials $f_{s_1,s_2,..,s_k}$ as in the definition 4.3 in this paper http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf In the use of these ...
3 votes
0 answers
382 views
Beating Kadane's Algorithm
I am seeking some reference on already existing work for the following problem. Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...
3 votes
0 answers
3k 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 ...
- 149
2 votes
0 answers
137 views
Why cannot we adapt Barvinok type counting techniques to general convex integer programs?
Decision problems in Integer Linear Programming have Lenstra type algorithms (https://www.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf) have been generalized to convex integer program ...
- 1
2 votes
0 answers
282 views
Modular inverse computation - avoiding Euclidean algorithm
Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime. If we already know ...
- 1
2 votes
0 answers
173 views
Modified quadratic assignment problem
Let $Y,Z$ be $n\times k$ matrices and assume all columns have been standardized such that their means are zero and variances 1. I seek an $n\times n$ permutation matrix $P$ such that $$\left\Vert Y^{T}...
- 133
2 votes
0 answers
95 views
Polyhedron coordinate bound
Given a polyhedron $$Ax\leq b$$ where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
- 1
2 votes
0 answers
170 views
Complete graph invariant based on integer programming?
Roughly speaking, we are trying to find complete graph invariant as the lexicographically first matrix from the permutations of the adjacency matrix. Let $G$ be graph, possibly directed graph, of ...
- 25.7k
2 votes
0 answers
455 views
Pros and cons of using integer programming alone or combined integer and global optimization?
First, I am not sure if this is the right question to ask in this forum. But I have been looking for answers for a long time and I have been also asking my university's "engineering" professors but I ...
2 votes
0 answers
88 views
Deciding whether a system of linear integer inequalities has infinitely many solutions
I have a quick question that I am struggling to find a solution to: Given a system of linear integer inequalities $A\textbf{x} \leq \textbf{b}$, where $A\in \mathbb{Z}^{m\times n}$ and $\textbf{b}\...
- 21
2 votes
0 answers
122 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
2 votes
0 answers
156 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\...
- 1
2 votes
0 answers
96 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 ...
- 123
2 votes
0 answers
108 views
On design of a (preferrably unimodular) matrix
Assume each entry is in $\Bbb Z$. Say we want to solve $Ax=b$ where known $A$ is $n\times n$, unknown $x$ is $n\times1$ and $b$ is $n\times1$. The absolute value of minors of augmented matrix $[A|b]$...
- 1
2 votes
0 answers
179 views
Listing all Lattice Points in a Box
Let $B := [-1,1]^n$ be an $n$-dimensional box. Moreover, let $v_1,\ldots,v_n \in \mathbb{R}^n$ form a basis of $\mathbb{R}^n$, where the entries of the $v_i$ are explicitly irrational. We can assume ...
- 173
2 votes
0 answers
100 views
Reference request: Edmond's Algorithm for integer hull
I'm looking for a good reference for the algorithm (supposedly by Edmonds) to compute the integer hull of a polytope, not by cutting plane methods but by starting with a set of integer points and then ...
- 243
2 votes
0 answers
153 views
integrality of a linear program -- binary equality constaints
Consider the following linear program: $\left\{ \begin{array}{l} \underset{x}{max} \;\;c^Tx\\ [I, \;B]x = \mathbf{1}\\ x\geq 0 \end{array} \right.$ where $c$ is a vector ...
- 127
2 votes
0 answers
207 views
existence of lattice point in polytope
This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
- 501
1 vote
0 answers
106 views
System of linear diophantine equations with many small solutions?
Let $n$ be positive integer, $k$,$B$ fixed positive integers. Let $f_i(x_1,x_2...x_n)$ be a system of $n-k$ linearly independent linear equations over the integers. Let $S(f_i,k,B)$ be the set of ...
- 25.7k
1 vote
0 answers
120 views
Proof for non-existence of short integer program for squares
We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question. Is there a way to show within an ...
- 1
1 vote
0 answers
79 views
learning about split cut (Integer Programming)
Here is a part of Integer Programming (Graduate Texts in Mathematics, 271) 2014th Edition. In lemma 5.9, aiming at showing that a finite number of splits ${(\pi, \pi_0)}$ are sufficient to generate ...
- 11
1 vote
1 answer
216 views
Mixed integer program and continuous Diophantine approximation
Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem. $$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$ subject to ...
1 vote
0 answers
125 views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61
1 vote
0 answers
121 views
Integer programming using the Steinitz lemma
I am trying to implement an algorithm that I read on the paper entitled: "Proximity results and faster algorithms for integer programming using the Steinitz lemma", published by Friedrich ...
- 111
1 vote
0 answers
52 views
Sum of all integer binary solutions of a TUM linear system
I have the following problem: $A x = b$ where $A$ is a $m \times n$ total unimodular matrix (TUM) with entries in $\{0,1\}$ and $b$ is a $m$-vector of strictly positive integers. Let $\mathcal X$ be ...
- 11
1 vote
0 answers
107 views
$\mathsf{NP}$ complete version of 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
1 vote
0 answers
59 views
Structural properties of polytopes for mainstream integer or linear programs
Are there any papers/textbooks/monographs that describe distinguishing properties of the polytopes that arise when solving the linear relaxation of well-known integer programs? For example, it is ...
- 4,131
1 vote
0 answers
48 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,846
1 vote
0 answers
149 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,846
1 vote
0 answers
58 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 \; ...
- 7,033
1 vote
0 answers
123 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