20
The current fastest algorithm is actually linear in the length of the integer linear program for every fixed value of $n$. In his PhD thesis, Lokshtanov (2009) nicely summarizes the results by Lenstra (1983), Kannan (1987), and Frank & Tardos (1987) by the following theorem.
Integer Linear Programming can be solved using $O(n^{2.5n+o(n)} \cdot L)$
...
20
Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first revisions, second revisions, new counter-examples, further revisions, further counter-examples, and so on.
It would be much better, if the authors were able to ...
14
If $m$ is superlinear, such an algorithm would disprove the Strong Exponential Time Hypothesis, since formulas in conjunctive normal form are a special case of 0-1 programming and the Sparsification Lemma allows us to reduce $k$-SAT to CNF-SAT on linearly many clauses.
However, there is an algorithm due to Impagliazzo, Paturi, and myself that can solve such ...
11
OptP-complete. Krentel showed that MAX-SAT, finding the lexicographically maximum satisfying assignment, is OptP-complete and the reduction above reduces Max-SAT to ILP. ILP sits in OptP pretty much by definition.
Note that you need n calls to an NP-oracle to solve ILP via binary search, O(log n) isn't sufficient.
There really isn't much of a connection ...
10
This problem is called bin covering. It's NP-hard and hard to approximate to better than a factor of two by an easy reduction from subset sum but has an asymptotic approximation scheme (i.e. one that fills $(1-\epsilon)\mathrm{OPT}-O(1)$ bins). See e.g. "Better approximation algorithms for bin covering", Csirik, Johnson, and Kenyon, SODA 2001, or "An ...
8
If you look at the original paper by Lenstra, Lenstra, and Lovasz, you will see the following applications:
factoring univariate polynomials over the rationals (the motivation for developing LLL basis reduction)
efficient version of Dirichlet's classical diophantine approximation theorem: for rationals $a_1, \ldots, a_n$ and $\epsilon$, find in polynomial ...
7
For your second question, the number of bits is $O(n^2 \log n)$ (i.e. $O(n\log n)$ per coefficient) and there are examples where it is $\Omega(n^2\log n)$, i.e. the bound is tight. See Corollary 26 here.
The ideas are standard, and anyone who has seen an analysis of the ellipsoid algorithm will be familiar with this. Say you have a facet in the hyperplane ...
7
Here are a few examples:
(Most Common) Cutting Stock Problem - determine patterns for which to cut boards in order to meet demand.
(Kinda same problem) - Knapsack with general integer variables - used for column generation in the cutting stock problem
Problems with modular constraints: $x \equiv 3 \pmod 5$ can be written as $x + 5y = 3$, $y \in \mathbb{Z}$....
7
NOTE: My original reduction didn't work. Fixed now.
Can't subset-sum be reduced to this problem fairly easily? Suppose all the profits $v_i$ are the same, say $v_i = 1$, and all the profits $p_i$ are proportional to the weights, so
$p_i = \beta w_i$ with $\beta < 1$.
Now, if there's a set of weights $S$ such that $\sum_{i\in S} w_i = W$, you can get a ...
7
An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally corresponds to a constraint $x_1 + x_3 + (1-x_4) + (1-x_6) \geq 1$, when all variables are forced to take values $0$ and $1$.
Hence if integer programming in $...
6
I think $S_n$ can be written in terms of inequalities in the obvious way. Let
$$
Q_n = \{(x, y): x = \sum_{i = 0}^{n-1}{2^i y_i}, \forall i: 0 \leq y_i \leq 1\}.
$$
I claim that $Q_n = S_n$. First, obviously all $(x, y) \in S_n$ are also in $Q_n$, so $S_n \subseteq Q_n$. Second, fix a point $(x^*, y^*) \in Q_n$. Consider the probability distribution over $\{...
6
You can find an answer in the following paper:
Joachim von zur Gathen, Malte Sieveking. A bound on solutions of integer linear equalities and inequalities.
Proc. AMS 72(1) (1978)
(pdf)
A simple corollary of their result follows.
Let's say we have two integer systems, $A x = b$ and $C x \ge d$,
where you want $x$ to be in $\mathbb Z^n$.
Consider ...
6
No. The number of feasible solutions cannot be upper bounded by $f(k)n^{O(1)}$.
Consider the integer program
$I_n: 1 \le x\le 2^n$
with the integer variable $x$. So, $k=1$ and the program can be described with $O(n)$ bits. But it has $2^n$ solutions, which is exponential in the instance size.
5
Here are a couple of points regarding the practical implications of Lenstra-type results, and possible implementations in CPLEX, Gurobi, etc. One of the key steps in most of such algos for IP is branching on "good" or "thin" directions, i.e., hyperplanes along which the width of the polytope is not too large (polynomial in variables and size of data). But ...
5
Consider the plane through the points $(1,0,0,0)$, $(0,1,0,0)$, $(0,0,1,0)$, $(1,1,1,1)$. If you add the origin to this set of points, the hyperplane is a facet of the convex hull. The equation is $x_1 + x_2 + x_3 - 2x_4 = 1$. The coefficient on $x_4$ is not $0$ or $\pm 1$.
5
Isn't this problem NP-complete?
Start with a graph $G$. Make $x_i = 1 \ \ \forall i$, where $i$ is a vertex of $G$. Now, for each edge $(i,j)$ of $G$, make $x_{i,j} = -3$. Otherwise, make $x_{i,j}=0$. Give weight 0 to all three- and four-level marbles. To maximize your objective function, you want to pick as many marbles as you can so long as you don't ...
5
if the number of non-zero coefficients in $A$ is linear in $n$, there is an algorithm that solves this problem in less than $2^n$ time.
Here's how it works. We use the standard connection between an optimization problem and its corresponding decision problem. To test whether there exists a solution $x$ where $Ax\le b$ and $c^T x \ge \alpha$, we will form ...
5
If I understood it well, (1) is also NP-complete, a possible reduction is from SUBSET SUM:
Given a set of $m$ positive integers $A = \{a_1, ..., a_m\}$, and a positive integer $B$, is there a subset of $A' \subseteq A$ a such that $\sum_{a_i \in A'} a_i$
You simply pick $n = (m+1)$ and build your set in this way:
add $ a_1, a_2, , ..., a_m$
add $m$ zeros
...
5
(1) As finding a second satisfying assignment to a 3SAT formula is still $\mathsf{FNP}$-complete (indeed, it is $\mathsf{ASP}$-complete, see Theorem 3.5 of [1]), and we can encode 3SAT as an integer program by a parsimonious reduction, finding a second integer point in an integer program is also $\mathsf{NP}$-hard.
(2) Barvinok [2] showed that in fixed ...
5
It's NP-hard. Given an integer programming problem $P$, add an irrelevant variable $z$ with no constraints; call the resulting problem $P'$. Now if $P$ has no solutions, then $P'$ has no solutions; if $P$ has a solution, then $P'$ has $> 1$ solutions. Consequently distinguishing between $\le 1$ solution vs $> 1 $ solution is at least as hard as ...
5
The original algorithm of Lenstra (from 1983) has not been implemented AFAIK. Certainly, no open-source code is known to be available.
Lovasz and Scarf proposed (in 1992) a generalized basis reduction algo that also solves IP in fixed dimensions, but avoids the ellipsoidal approximations required by Lenstra's algorithm. An implementation of this algo was ...
4
Kolloiopoulos and Young give an $O(\log m)$ approximation for general covering integer programs. See the paper below.
http://www.sciencedirect.com/science/article/pii/S0022000005000656
4
It seems that we can reduce Subset Sum to your problem (2). Hence, your problem (2) is NP-complete.
Consider the following formulation of Subset Sum.
Instance: A multi-set consisting of $n$ integers.
Question: Does there exist a subset of size at least $1$ that sums to zero?
Now, we reduce Subset Sum to your problem (2). Let a multi-set $X$ consisting ...
4
There's a straightforward way to construct a function $f_z:\{0,1\}^n \to \mathbb{R}$ that is zero at only a single point $z=(z_1,\dots,z_n)$ and strictly positive everywhere else: namely,
$$f_z(x_1,\dots,x_n) = (x_1-z_1)^2 + (x_2-z_2)^2 + \dots + (x_n-z_n)^2.$$
Based on this, we can easily construct a function $g : \{0,1\}^n \to \mathbb{R}$ that is zero at ...
4
If we consider the minimization problem $\min_y \{c^T y : Ay \ge b, y \in \{ 0,1\}^n \}$, then the following reduction shows that an algorithm running in time $O(2^{\delta n/2})$ for $\delta <1$ would disprove the SETH. A reformulation proves the same result for the intended problem (the maximization version).
Given an instance $\Phi = \wedge_{i=1}^m C_i$...
4
In a multiple knapsack problem you pack a set of items into several (one-dimensional) knapsacks, whereas in the multidimentional knapsack problem you pack d-dimensional items into one d-dimensional knapsack. The multiple knapsack problem $\max\{\sum_i p_i x_i \mid \sum_i w_{ij}x_i \leq d_j, j=1,2,\ldots,m\}$ is a general 0-1 integer program restricted to ...
4
You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^*$, whereas parameterized decision problems are often considered as subsets of $\Sigma^* \times \mathbb{N}$ (see [1, Chapter 2]). Classical complexity classes (such as NC, P and NP) are sets of classical ...
3
The problem you're asking to solve is a variant of the $k$-median problem on a metric space. You haven't mentioned anything about the various sizes involved, but as a formal matter, there are only $n$ choices for the magic number $k$ (the number of centers), and so after "guessing" the right value of $k$, you can run any of the standard approximation ...
3
Via Rubin:
There is a sequence of polytopes $\{ P_k\}_k$ each defined by two variables and one constraint (plus two nonnegativity constraints) such that the integer hull of $P_k$ has $k+3$ vertices and $k+3$ facets.
$P_k=\{ (x,y)\in \mathbb{R}^2_+ ~|~f_{2k} x + f_{2k+1}y \le f^2_{2k+1}-1\}$
Here, $f_j$ is the $j$-th Fibonacci number.
This shows that the ...
3
EDIT (Jan 2019): Lemma 2 as currently stated below is wrong. (Indeed, given any instance, adding a single edge with a single type of very large cost will not change the instance but will yield $N(I)=1$, in which case the lemma claims that the algorithm will give an optimal solution. The proof is wrong because the function $\Phi$ defined there is not ...
Only top voted, non community-wiki answers of a minimum length are eligible
