# 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 for 0-1 programming?

• Isn't 0-1 programming a special case of integer programming ? – Nathann Cohen May 22 '12 at 12:40
• 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$. – Jukka Suomela May 22 '12 at 13:09
• What is "a 0-1 program with a constant number of constraints"? Do the constraints $0\le x_i \le 1$ not count? – Jeffε May 22 '12 at 17:05

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.

• Also, "unbounded knapsack," where you have just the non-negativity bounds and integrality constraints without the upper bounds of 1, is still NP-hard. – daveagp Dec 2 '12 at 4:49

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.

• 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. – Tsuyoshi Ito May 24 '12 at 3:38

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.

• 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. – Robin Kothari May 23 '12 at 16:27

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.