<p>Lenstra showed in the mentioned paper, that the <em>Integer
Linear Programm <strong>Feasibility</strong> Problem</em></p>

<blockquote>
  <p>Given integral matrix $A_{m,n}$ and $b \in \mathbb{Z}^m$. <br> Is there a $x \in \mathbb{Z}^n$ such that $Ax \le b$ ?</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2012-05-24T03:38:52.977Z
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
CC BY-SA 3.0
2012-05-23T22:19:37.857Z
2012-05-23T22:45:51.197Z
2012-05-23T22:45:51.197Z
muede
<p>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. </p>

CC BY-SA 3.0
2012-05-22T23:12:55.180Z
2012-05-22T23:12:55.180Z
user8477
<p>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.</p>

CC BY-SA 3.0
2012-05-23T16:27:40.877Z
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
CC BY-SA 3.0
2012-05-22T13:37:26.753Z
2012-05-22T13:37:26.753Z
Karan Sapra
<p>I'm assuming that by "0-1 programming with a constant number of constraints" you mean the following problem:</p>

<p>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.</p>

<p>This problem is NP-complete even with 1 additional constraint since 0-1 knapsack can be written in this form.</p>

CC BY-SA 3.0
2012-12-02T04:49:32.247Z
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
CC BY-SA 3.0
2012-05-22T22:51:20.923Z
2012-05-22T22:51:20.923Z
Robin Kothari
<p>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.</p>

<p>Does this hold for 0-1 programming?</p>

CC BY-SA 3.0
2012-05-22T12:40:06.810Z
Isn't 0-1 programming a special case of integer programming ?
Nathann Cohen
CC BY-SA 3.0
2012-05-22T13:09:55.963Z
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
CC BY-SA 3.0
2012-05-22T17:05:36.783Z
What is "a 0-1 program with a constant number of constraints"?  Do the constraints $0\le x_i \le 1$ not count?
Jeffε
<cc.complexity-theory><integer-programming>
Is 0-1 programming with constant number of constraints polynomially solvable?
Regularity
# Is 0-1 programming with constant number of constraints polynomially solvable?

(Asked by: username_0 on 2012-05-22)

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?

**Tags:** cc.complexity-theory, integer-programming
> **Comments:**
> **username_1**: Isn't 0-1 programming a special case of integer programming ?  
> **username_2**: 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$.  
> **username_3**: What is "a 0-1 program with a constant number of constraints"?  Do the constraints $0\le x_i \le 1$ not count?  

---

## 4 answers

### Answer by username_8 on 2012-05-22. Score: 21 | Accepted answer

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.

> **Comments:**
> **username_9**: 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 by username_4 on 2012-05-23. Score: 0

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.

> **Comments:**
> **username_5**: 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 by username_6 on 2012-05-22. Score: -1

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.


---

### Answer by username_7 on 2012-05-22. Score: -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.

> **Comments:**
> **username_8**: 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.  

---

