# Questions tagged [integer-programming]

The tag has no usage guidance.

78 questions
Filter by
Sorted by
Tagged with
1k views

### What is known about solutions to sparse integer linear programming problems?

If I have a set of linear constraints in which each constraint has at most (say) 4 variables (all nonnegative and with {0,1} coefficients except for one variable that can have a -1 coefficient), what ...
2k views

### How fast can we solve a totally unimodular integer linear program?

(This is a follow-up to this question and its answer.) I have the following totally unimodular (TU) integer linear program (ILP). Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ ...
266 views

### Any example of an unsatisfiable integer program with non constant Rank Lower bounds for LS+ cuts but with short LS+ refutations?

Assume we want to refute an unsatisfiable CNF. We can interpret it as an integer program, thus a refutation can be done by applying Lovasz-Schrijver semidefinite cuts ($LS_{+}$ cuts) to its linear ...
862 views

### Which Integer Linear Programs are easy?

While trying to solve a problem, I ended up expressing part of it as the following integer linear program. Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ are all positive ...
3k views

### Integer programming with a fixed number of variables

The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of ...
692 views

### Is 0-1 programming with constant number of constraints polynomially solvable?

It was shown in the paper "Integer Programming with a Fixed Number of Variables" that integer programmings with constant number of constraints (or variables) are polynomially solvable. Does this hold ...
597 views

### Exact exponential-time algorithms for 0-1 programming

Are there known algorithms for the following problem that beat the naive algorithm? Input: A system $Ax \le b$ of $m$ linear inequalities. Output: A feasible solution $x^*\in \{0,1 \}^n$ if one ...
391 views

### Exact exponential-time algorithms for 0-1 programs with nonnegative data

Are there known algorithms for the following problem that beat the naive algorithm? Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers. Output: an optimal ...
953 views

### Integer Factoring via Lattice Reduction?

I found a paper titled "Factoring integers and computing discrete logarithms via diophantine approximation" by C. P. Schnorr from 1993. It looks like a probabilistic method with expected polynomial ...
118 views

### Quanitifier Free Presburger Arithmetic: Upper bound on solution size?

DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question. According to this paper, if ...
298 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 ...
69 views

### Is there a name for this unimodilarity-related property?

Consider an arbitrary integer linear program of the form $\min f(x,y) \\ @ \ Ax + By \leq c\\ x,y \in \mathbb{Z}_+$ If you continuous-relax the integer constraint and still always get integer ...
123 views

372 views

### On integer programming

Integer programming is NP-hard. What is the status of integer programming problem that decides between existence of $\leq1$ solution and $>1$ solutions (note $0$ solutions falls in $\leq1$ ...
61 views

181 views

### On facets of 01-polytope

$0,1$-polytopse are fundamental objects in combinatorial geometry and comvex optimization. I am interested in the size of binary representation of hyperplanes to use in the framework of computational ...
145 views

### Anti bin packing

I have a (practically) unlimited amount of McDonald's coupons that I can use only if I shop for at least 1 money. Thus I want to partition my family's meal into as many parts as possible that all ...
182 views

### Have fixed parameter integer program algorithms ever been implemented for research use?

Have any fixed parameter integer programming algorithms described in Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?
261 views

### Lattice-based algorithms in practice

Are there any applications of lattice-based algorithms other than those in cryptography and integer programming? Could someone state a few papers where the primary algorithms use lattice-based LLL ...
457 views

### Minimum Union-Sum Cost Path

I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path ...
395 views

### FPT algorithm for mixed integer program

It is known that every integer linear program parameterized by the number of variables is FPT (fixed parameter tractable). Is every mixed integer program parameterized by the number of integer ...
84 views

### Fixed dimension Linear Integer Programming in $NC$

We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?
195 views

### What exactly did Lenstra prove on mixed integer linear program?

I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
275 views

### Are there integer programs with small coefficients that only have large solutions?

It is well-known that if an integer linear program has a feasible solution, then it has a feasible solution whose bit size is polynomially bounded. For example, here is Theorem 13.4 from Papadimitriou ...
853 views

### How to determine proper rounding in linear programming relaxations?

Recall that in the vertex cover problem we are given an undirected graph ${G=(V,E)}$ and we want to find a minimum-size set of vertices ${S}$ that “touches” all the edges of the graph, that is, such ...
186 views

### LP-type vs. Approximation

I'm interested in an computational geometry problem that's sensibly expressed as an infinite dimensional 0-1 integer program. I'm not worried about finding an actual minimum for the objective ...
132 views

398 views

### Facility location problem with a cost function

I'm struggling with a facility location problem. In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from ...
412 views

### Applications and benchmarks for binary quadratic program algorithms

I have an algorithm that on all examples I was running finds an arbitrary approximation of global minimum of binary quadratic program. The algorithm find the minimum in polynomial time. Binary ...
129 views

### Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?

I'm considering integer programming on an variation of Steiner Forest Problem: Given a graph $G=(V,E)$, a cost function: $c:E \rightarrow R^{+}$, a terminal set $T \subseteq V$, and a positive ...
252 views

### Space complexity of integer programming

Given $A\in\Bbb Z^{n\times k}$, $v\in\Bbb Z^n$ and variables $x_1,\dots,x_k$ given as a vector $x$ we know that solving $x\in\Bbb Z^k$ in $Ax\leq v$ is fixed parameter tractable. There is a ...
144 views

### Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K

I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known. The ...
104 views

### Fixed parameter Integer Programming circuit depth complexity

It is well known Lenstra's and Kannan's algorithm achieves $n$-variable parameter $L$-bit integer programming solvability in $O(n^nL)$ time and $O(L)$ space. If implemented as an arithmetic circuit ...
244 views

141 views

### Can Lenstra's algorithm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k?

It is well-known that Lenstra's famous algorithm (presented in the paper Integer programming with a fixed number of variables) can solve an ILP problem in $O^*(f(k))$ time where k is the number of ...
79 views

### Complexity of generating a pseudo-Boolean function

A pseudo-Boolean function is a mapping from $\mathcal{B}^n = \{0, 1\}^n$ to $\mathbb{R}$. Following is a pseudo-Boolean function. s_1 s_4 - s_2 s_3 - s_3 s_5 - s_2 s_5 + s_1 + s_4 - s_1 s_3 - ...
80 views

### Paper about the upper bound of the number of inequalities to describe the Integer hull of a polyhedron

I am interested in the upper bound of the number of inequalities to describe the integer hull of a polyhedron. That is, given an integer programming problem with n inequalities which construct a ...
Consider three distinct sets $A, B, C$ of $N$ elements respectively. For each pair of sets, say $A,B$, we introduce an variable for each combination of values $a,b$ as $x_{ab}$. Similarly, we ...