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.

50 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 (...
7
votes
1answer
168 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 \...
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 ...
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 ...
4
votes
0answers
119 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. ...
4
votes
0answers
363 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 ...
4
votes
0answers
232 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 ...
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-...
3
votes
0answers
84 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}{...
3
votes
0answers
219 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 ...
3
votes
0answers
119 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 ...
3
votes
0answers
40 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
0answers
316 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
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 ...
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
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
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
0answers
78 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]$...
2
votes
0answers
115 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 ...
2
votes
0answers
75 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 ...
2
votes
0answers
108 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 ...
2
votes
0answers
157 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 ...
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
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
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\...
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-...
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,\...
1
vote
0answers
42 views

Distribution of maximum minor of a random matrix with one special column

Given $m,n,\ell\in\Bbb N$ and $\beta\in(0,1)$ consider the uniformly picked random matrix $A\in\Bbb Z^{n\times (n+1)}$ with $0\neq|\mathsf{det}(A^\circ)|\leq m^{\frac 1\ell}$ where $A^\circ$ is the ...
1
vote
0answers
99 views

Strong Duality of Mixed Integer Linear Program

The problem at hand is to optimize a mixed-integer linear program closely related to the maximum flow problem. I would like to reformulate the problem with its dual and I'm concerned with the ...
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
0answers
112 views

The column generation technique on a Train Unit Assignment Problem [Linear Programming]

I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...
1
vote
0answers
73 views

Are there any known bounds on the value of solutions of linear integer programming?

Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints? ...
1
vote
0answers
303 views

Complexity of Nested Linear Optimization

My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint: $$\max(\...
1
vote
0answers
1k views

Subtour Elimination in Travelling Salesman Problem using MTZ

I am trying to formulation a problem similar to a Traveling Salesman with Time Window constraints. To eliminate subtours, I need to use some constraint similar to a generalization of MTZ constraints ...
1
vote
0answers
62 views

What is the solution to \min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}

(I've posted this question at Math.SE but got no answer, so I hope I can get a solution here.) This problem looks familiar, but I don't remember its solution: $$ \min_k \ \ \frac{b^k/n}{\lfloor b^k/...
1
vote
0answers
385 views

Maximum subset of set of Integers with minimum distance

Hi, i have a set of integers for example: {0,1,3,100,102} and i am looking for a maximum subset in which all elements have a minimum distance to all elements (or the "next" doesnt matter i guess) for ...
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\}$...
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
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 \...
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 $...
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 ...
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 ...
0
votes
0answers
476 views

Maximum shortest path problem

I have the following problem. You have a graph and every edge has a certain set of possible weights. The question is to find the assignment of those weight which will maximize the shortest path. In ...
0
votes
0answers
128 views

Mixed-Integer Bilinear Program (MIBLP)

Consider the problem of \begin{align} \min_{x,y} \quad &a^Tx + b^Ty + x^TQy \\ &Ax \leq d \\ &Cy \leq e \\ &x_i \in \mathbb{R} \quad i \in \{1,2,\ldots,N\} \\ &y_i \in {\{0,1\}} \...
0
votes
0answers
100 views

Linear system with many solutions from a finite set

Basically I am looking for a linear system with many solutions from a finite set. Choose a finite set of rationals $S$ and fix positive integer $k$. Let $A$ be a linear system with $n$ variables $...
0
votes
0answers
406 views

LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
0
votes
0answers
195 views

Knapsack Constraint

I'm trying to implement a recursive algorithm that I came up with that first solves the knapsack for a given objective and then cuts off the solution and then finds the next best solution. However, I ...