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 for 0-1 programming?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Isn't 0-1 programming a special case of integer programming ? $\endgroup$– Nathann CohenMay 22, 2012 at 12:40
-
3$\begingroup$ I guess the nontrivial part is this: if you have a black box algorithm A that is able to solve integer programs with a constant number of constraints (but arbitrarily many variables), it is not obvious how to use A to solve 0-1 programs with a constant number of constraints. You cannot simply add constraints of the form $0 \le x_i \le 1$ for each variable $x_i$. $\endgroup$– Jukka SuomelaMay 22, 2012 at 13:09
-
3$\begingroup$ What is "a 0-1 program with a constant number of constraints"? Do the constraints $0\le x_i \le 1$ not count? $\endgroup$– JeffεMay 22, 2012 at 17:05
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
I'm assuming that by "0-1 programming with a constant number of constraints" you mean the following problem:
Maximize some linear function of (x_1, x_2, ..., x_n) subject to the constraints that each x_i is in {0,1} and a constant number of additional linear constraints.
This problem is NP-complete even with 1 additional constraint since 0-1 knapsack can be written in this form.
answered May 22, 2012 at 22:51
-
1$\begingroup$ Also, "unbounded knapsack," where you have just the non-negativity bounds and integrality constraints without the upper bounds of 1, is still NP-hard. $\endgroup$– daveagpDec 2, 2012 at 4:49
$\begingroup$
$\endgroup$
1
Lenstra showed in the mentioned paper, that the Integer Linear Programm Feasibility Problem
Given integral matrix $A_{m,n}$ and $b \in \mathbb{Z}^m$.
Is there a $x \in \mathbb{Z}^n$ such that $Ax \le b$ ?
is polynomially solvable, if n or m is constant. (Note the absence of a goal function.) This result is commonly used in the analysis of parameterized problems, i.e. it can be used to prove fixed-parameter-tractability by a reduction.
-
4$\begingroup$ I am not sure why you posted this, but if you are implying that the difference between the feasibility version and the optimization version is important, then no, it is not important: a polynomial-time algorithm for the feasibility version can be used to solve the optimization version also in polynomial time by combining it with binary search. $\endgroup$ May 24, 2012 at 3:38
$\begingroup$
$\endgroup$
1
0-1 integer programming or binary integer programming (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version is NP-Complete.
-
3$\begingroup$ While both IP and BIP are NP-hard, this doesn't say much about whether IP and BIP with a constant number of constraints is NP-hard. Indeed, IP with a constant number of constraints is in P, whereas BIP with a constant number of constraints is still NP-hard. $\endgroup$ May 23, 2012 at 16:27
$\begingroup$
$\endgroup$
0
In addition to what Robin said, if I understood the question correctly, if we have a constant number of variables $k$ that can take only the values 0 or 1, a brute force algorithm that tries all $2^k$ possibilities for the variables and checks whether each possibility obeys the constraints would be a polynomial time algorithm.
