Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
16 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: $$...
1
vote
0answers
71 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)^...
0
votes
0answers
85 views

Is there a notion of linear $\mathbb F_q[x]$ program?

A feasibility linear integer program is essentially deciding if a convex polytope represented by a set of inequalities has an integer point and a minimization linear integer program is to find the ...
0
votes
1answer
74 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}$...
0
votes
0answers
9 views

How to Create Point-Optimal Objective Functions

Here is a problem that has originated from some IP research i'm working on. You are given a polyhedron $P$ in standard matrix inequality form of $Ax \le b$, $x \in \mathbb{R}^n$ as well as a point $...
3
votes
2answers
232 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
85 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
32 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-...
2
votes
0answers
71 views

Quadratic integer program over a sphere

Given vector $a \in \mathbb{R}^K$ and symmetric and positive definite matrix $M \in \mathbb{R}^{K \times K}$, \begin{align} \underset{\vec{x}}{\text{minimize}}\quad &(\vec{x}-a)^\dagger M(\vec{x}-...
0
votes
1answer
62 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
132 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
84 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 ...
0
votes
0answers
75 views

Faster Mixed Integer Linear Programming Searchless Feasibility

We know Lenstra's Mixed Integer LP with Kannan's modificiation solves feasibility Mixed Integer LP in $n$ integer variables, $r$ real variables and $m$ constraints by solving the search version in $n^{...
0
votes
0answers
16 views

Mod in an Inequality in a Proof of Addition Chain element Bounds

Using IP I was able to find an improvement of the best known bounds for addition chain elements. Essentially you can look at the end of an addition chain as a linear system and solve it over the ...
2
votes
1answer
49 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
55 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
69 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
0answers
70 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 ...
0
votes
0answers
46 views

On integer programming augmented with Barvinok's counting version?

Suppose we have an Integer Linear program with $m$ number of inequalities and $n+2$ integer variables ($a_1,\dots,a_n,x,y$). We introduce two extra variables $t$ and $u$ and inequalities $$1\leq t\...
0
votes
0answers
7 views

Fixed dimension Integer programming minus LLL in $NC$?

If you remove LLL part then is remaining part of Lenstra algorithm Barvinok algorithm in $NC$ in fixed dimension?
0
votes
0answers
46 views

On fixed dimension integer programming complexity when LLL is perfect

Fixed dimension integer programming (both Lenstra's and Barvinok's) uses LLL which guarantees short vectors but not the shortest possible. Suppose for a given integer programming problem find $x\in\...
1
vote
1answer
165 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? ...
2
votes
1answer
99 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
42 views

Formalizing a projective additive construction of polytopes?

Given a polytope represented by $$Ax\leq b$$ where $A\in\Bbb Z^{m\times n}$, $x\in\Bbb Z^n$ and $b\in\Bbb Z^m$ with $N\geq 0$ number of integer points can we construct a polytope with $N+1$ integer ...
0
votes
0answers
64 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 $...
1
vote
2answers
139 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 ...
4
votes
1answer
128 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
310 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
91 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
90 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=\...
0
votes
0answers
38 views

Complexity of fixed variable integer program with OR condition (or equivalently on disjoint polytopes)

In Integer programming we seek to find $x\in\Bbb Z^n$ when $A\in\Bbb Z^{m\times n}$ and $B\in\Bbb Z^m$ are given and $Ax\leq B$ holds and we know an $O(n^nmL)$ arithmetic operation on $O(L)$ sized ...
2
votes
0answers
70 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 ...
0
votes
0answers
50 views

Rules of thumb for hardness of integer programming and software for fixed parameter integer programming simulation?

I want to simulate a $20$ constraint $13$ variable ($6$ are free) linear integer programming problem. What is the best algorithm out there? Is there a readily available library anywhere? The notes ...
0
votes
0answers
140 views

Solving promise quadratic diophantine equation?

What is the best possible method to solve the quadratic diophantine equation/integer programming problem ($m,n,p,r>0$ known integers) $$mx^2 + n xy + py^2=r$$ with $x,y$ unknown integers which we ...
2
votes
1answer
73 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 ...
5
votes
1answer
241 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{...
3
votes
2answers
431 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
0answers
130 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 ...
1
vote
1answer
188 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,\...
3
votes
0answers
86 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-...
2
votes
1answer
95 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 ...
3
votes
2answers
221 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 ...
0
votes
2answers
244 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$ ...
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 ...
5
votes
0answers
98 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 ...
0
votes
0answers
88 views

Addition Chains meets Linear Diophantine Equations

I am trying to understand how I might be able to determine arithmetically if solutions exist or enumerate solutions (if there are a small number of solutions) to a linear Diophantine equation with ...
6
votes
1answer
277 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\...
1
vote
0answers
39 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 ...
2
votes
0answers
74 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]$...
0
votes
0answers
412 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 ...