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.
198 questions
1
vote
0
answers
101
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,982
2
votes
1
answer
191
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 ...
- 13.9k
4
votes
1
answer
866
views
When is a triangular matrix totally unimodular?
I have a {0,1}, invertible, triangular matrix, that I would like to show is totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
- 1,182
4
votes
1
answer
150
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 ...
- 13.9k
2
votes
1
answer
69
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 ...
- 13.9k
0
votes
0
answers
891
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 ...
- 342
3
votes
2
answers
1k
views
SDP relaxation vs LP relaxation
I have a question I hope you might be able to answer.
Let's say we have an integer program for the stable set problem (or clique, not principal).
\begin{equation}
\begin{aligned}
& \text{...
- 342
2
votes
2
answers
105
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=\...
- 13.9k
3
votes
1
answer
447
views
An interesting problem which I think only needs elementary number theory
A problem about elementary number theory
While writing my paper, I came across the following problem:
(all the discussion assume that $q$ is prime and $\alpha $ is a positive integer. ) We first ...
- 363
1
vote
1
answer
122
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 ...
- 13.9k
0
votes
0
answers
27
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\}$...
- 85
0
votes
2
answers
318
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$ ...
- 501
1
vote
0
answers
35
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,836
1
vote
0
answers
74
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-...
- 11
2
votes
1
answer
530
views
Integer programming and Groebner basis
I enjoyed reading different papers about using Groebner basis to solve integer programming.
Is there any literature about the complexity and/or comparison with other (more classical) methods like ...
- 337
3
votes
2
answers
2k
views
Sherali-Adams relaxation
I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...
- 113
6
votes
1
answer
371
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 ...
- 71
5
votes
1
answer
2k
views
Algorithm to minimally connect line segments in Euclidean plane
Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...
- 153
2
votes
0
answers
103
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 ...
- 13.9k
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
1
vote
0
answers
37
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 \; ...
- 6,853
0
votes
0
answers
299
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 ...
- 867
2
votes
1
answer
202
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 ...
- 131
2
votes
0
answers
120
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\...
- 13.9k
0
votes
0
answers
72
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 $...
- 2,251
8
votes
1
answer
336
views
On linear integer inequalities with infinitely many solutions
Suppose that a linear system of inequalities $Ax \le b$, where $A\in Z^{m\times n}$ and $b\in Z^m$ have integral coefficients, has an infinite number of integral solutions $x$.
Can one conclude that ...
- 3,873
3
votes
2
answers
2k
views
Finding closest point to a set of circles
My requirement is to find the point closest to three circles. So lets say the three circles are C1, C2, C3. I want to find the point in the space such that the SUM of its distance from C1, C2 and C3 ...
- 33
6
votes
1
answer
1k
views
Speed up Linear programming
I have a linear programming problem like this:
minimize $c^t X$
under the constraint that $AX \ge b$.
I will need to solve this linear programming problem online many times. I need it to be as fast ...
- 83
1
vote
1
answer
116
views
Sign Enumeration
What is the number of solutions of $(a_i)_{i=1}^n$ such that
$$\sum_{i=1}^nia_i\le b,\quad a_i\in\{-1,1\},\quad \sum_{i=1}^n{a_i}=c$$
given $b,c\in\mathbf Z$?
Is there a generating function solution?
- 2,251
6
votes
1
answer
263
views
Algorithm that solves every Mixed Integer Linear Program (to optimality)?
Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically?
I know that you usually ...
- 1,282
1
vote
3
answers
2k
views
How to solve Linear Programming problem with tighter Integer Programming constraints
I want to learn a bit about Linear Programming.
After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally ...
2
votes
1
answer
107
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 ...
- 345
2
votes
1
answer
191
views
programming to compute kernel quotient image of a $\mathbb{Z}$-module endomorphism
Let the integers $n\geq 2$, $k\geq 1$, $v=0$ or $1$ and $n_1,\cdots,n_k\geq 1$ such that
$$
\sum_{i=1}^k n_i+v=n.
$$
Define $P_a^b=0$ if both $a,b$ are odd and $P_a^b={{[a/2]}\choose {[(a+b)/2]}}$ ...
- 1,990
4
votes
3
answers
2k
views
Lattice points close to a line
Take a sheet of grid paper and draw a straight line in any direction from the origin. What is the closest non-zero grid point $\boldsymbol{p}\in\mathbb{Z}^2$ within a distance $\epsilon>0$ of the ...
- 561
4
votes
2
answers
2k
views
Simplified knapsack problem
There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
- 41
1
vote
1
answer
286
views
maximization of harmonic mean
Suppose x is a vector of size N with positive real elements sorted in decreasing order. Is it possible to find the analytical solution (no iterative solution) to the optimum value of M (1<= M <=...
2
votes
0
answers
80
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
8
votes
0
answers
200
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.4k
5
votes
1
answer
1k
views
Minimum distance between adjacent concentric circles that cross integer lattice points
This problem looks simple, but I searched around and couldn't find any similar problems or related resources. Hope someone could provide a clue or at least a hint of what class of prolbems it belongs ...
- 53
1
vote
1
answer
3k
views
Multiple disjoint subset sum problem
Given two sets of nonnegative integer numbers:
$X = {x_1, x_2, ... x_n}$
$Y = {y_1, y_2, ... y_m}$
Need to find partition of $X$ on $m$ disjoint subsets, such as sum of elements in $i$-th subset ...
- 149
3
votes
0
answers
149
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
0
votes
0
answers
181
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\}} \...
- 113
3
votes
1
answer
388
views
Sufficient condition for solvability of linear diophantine system
I would like to know under what conditions does an integer solution exist to the under-determined linear system:
Ax = b. (without constraints)
Where A is m x n matrix with positive integers entries (...
- 31
3
votes
0
answers
100
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,049
3
votes
0
answers
237
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
5
votes
2
answers
635
views
Area of a lattice polygon in terms of its width
Let $M$ be a lattice polygon on a plane (i.e. its vertices are integer points $(i,j)\in\mathbb Z^2$).
Let us define lattice width in a direction $v=(m,n)\in\mathbb Z^2$ as $w_v(M)=\max\limits_{x,y\in ...
- 5,063
2
votes
1
answer
6k
views
sum of maxima vs the maximum of the sum
Consider the following integer program
$$
\begin{align}
\max &\sum\nolimits_{i}\sum\nolimits_{j} U_i(j)\cdot x_{i,j}\\
\text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant c_j,&...
- 21
2
votes
1
answer
1k
views
Finding integer points inside of a parallelogram
Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...
- 1,318
1
vote
0
answers
187
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 ...
- 11
0
votes
2
answers
708
views
Approximate solution to large mixed integer programming problem
What are the available approaches to find an approximate solution to a large mixed integer programming problem?
I ran my problem in the Gurobi MIP solver.
It can find a feasible solution in ...
user24451