11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Isn't 0-1 programming a special case of integer programming ? $\endgroup$ – Nathann Cohen May 22 '12 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 Suomela May 22 '12 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 '12 at 17:05
20
$\begingroup$

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.

$\endgroup$
  • 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$ – daveagp Dec 2 '12 at 4:49
0
$\begingroup$

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.

$\endgroup$
  • 3
    $\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$ – Tsuyoshi Ito May 24 '12 at 3:38
-1
$\begingroup$

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.

$\endgroup$
  • 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$ – Robin Kothari May 23 '12 at 16:27
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.