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

Question

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?

• Nathann Cohen: Isn't 0-1 programming a special case of integer programming ?
• Jukka Suomela: 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$.
• Jeffε: What is "a 0-1 program with a constant number of constraints"? Do the constraints 0ドル\le x_i \le 1$ not count?

Answer 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.

• daveagp: Also, "unbounded knapsack," where you have just the non-negativity bounds and integrality constraints without the upper bounds of 1, is still NP-hard.

Answer 2

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.

• Tsuyoshi Ito: 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.

Answer 3

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.

• Robin Kothari: 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.

Answer 4

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.