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
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
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
6
votes
2
answers
447
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{...
- 91
3
votes
2
answers
1k
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
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
3
votes
1
answer
368
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
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
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
3
votes
2
answers
233
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 ...
- 89
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
0
votes
0
answers
68
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 ...
- 501
5
votes
0
answers
129
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
6
votes
1
answer
407
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\...
- 61
1
vote
0
answers
43
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 ...
- 13.9k
2
votes
0
answers
92
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]$...
- 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
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
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
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
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
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
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
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
8
votes
0
answers
231
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 \...
- 343
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
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
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
6
votes
1
answer
264
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
2
votes
0
answers
112
views
Pcross-like, nonogram-like in near-linear time [closed]
I have a problem with a puzzle game like pcross in which I have a nxn square: At any index of rows and columns I have an integer that say the maximum numbers of points that I can place in that row/col....
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
608
views
Minimal solution of simultaneous congruences
I would to determine the set of values $\lbrace a_1,a_2,a_3,\ldots,a_n \rbrace$ that minimizes the value of $x$ such that:
$$x\equiv a_1\mod p_1$$
$$\vdots$$
$$x\equiv a_n\mod p_n$$
where every ...
- 31
3
votes
0
answers
167
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 ...
- 329
2
votes
1
answer
366
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}}+\...
- 21
2
votes
0
answers
154
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
3
votes
0
answers
41
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 ...
1
vote
0
answers
120
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 ...
- 111
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
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
1
vote
0
answers
132
views
Complexity :: Integer Programming :: Non-Poly Example [closed]
When learning about computational complexity I find that when discussing the NP-Complete problems authors always give examples of such problems that can in fact be solved in poly time.
I understand ...
- 19
1
vote
2
answers
753
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{...
- 51
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
2
answers
202
views
Combinatorial optimization problem involving infinite spin system
In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity.
...
- 867
0
votes
1
answer
270
views
Generalized assignment problem with no integrality gap
Suppose I am solving the generalized assignment problem, so that I
am given matrices $U$ and $W$ and a vector $c$ (all three of which
have, say, positive entries), and I want to solve
$$\text{...
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
2
votes
1
answer
143
views
Find base of kernel with as many 0 as possible
I have a 400x132 rectangular matrix with only 0 and 1.
I am looking for the linear combinations of the columns of the matrix that sum to 0.
For example C1 + C2 - C3 = 0.
I want to find the linear ...
- 83
2
votes
0
answers
83
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
0
votes
2
answers
462
views
Mixed integer programming formulation for Ising model [closed]
I want to implement a minimisation on a 2D spin Ising model with 30x30 grid. The spin variables is 0,1 and the objective is to minimize the sum of products of spins. For simplicity, I only include NN ...
- 867
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
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
4
votes
0
answers
136
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.
...
- 867