Does this $0-1$ integer program have any speciality?

Question

Given matrix $A \in \{0,1\}^{m \times n}$ and vector $b \in (\mathbb{Z^+})^m$, where $\mathbb{Z^+}$ is the set of positive integers,

$$\begin{array}{ll} \text{maximize} & c^\top x\\ \text{subject to} & Ax \leq b\\ & x \geq 0\\ & x \in \{0,1\}^n\end{array}$$

Notice the biggest difference from normal $0-1$ integer programming is that $A \in \{0,1\}^{m \times n}$ and $b \in (\mathbb{Z^+})^m$. Is there anything special about such integer programs? Is there an algorithm to solve them in polynomial time?

This question also exists at math.stackexchange

Answer 1

With binary $b$, it is called a set packing problem: https://en.m.wikipedia.org/wiki/Set_packing

With integer $b$, it is called a generalized set packing problem.

Answer 2

In general no, these problems are hard. BUT: You might want to look into totally unimodular matrices and total dual integrality but this requires additional assumptions on the matrix or the problem respectively. If you are lucky, then your problem has these properties and you can solve it efficiently.

Totally Unimodular Matrices

A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. Equivalently, every square submatrix has determinant 0, +1 or −1. From the definition it follows that any submatrix of a totally unimodular matrix is itself totally unimodular (TU). Furthermore it follows that any TU matrix has only 0, +1 or −1 entries (the opposite is not true).
Some notable examples are network matrices, or the coefficient matrices of maximum flow and minimum cost flow problems.
These types of matrices are very benevolent for integer problems because if $A$ is TU and $b$ is integral, then linear programs of forms like $\{\min c^Tx ∣ A x ≥ b , x ≥ 0\}$ or $\{\max c^Tx ∣ A x ≤ b\}$ have integral optima, for any $c$.

TU matrices are also balanced matrices for which you can also show that they yield integral solutions. For these the assumptions on the matrix a more relaxed compared to totally unimodularity but to get integral solutions the right-hand side or the objective must be an all one vector.

Total Dual Integrality

Also, for TDI problems you'll get an integer optimal solution, but here the definition is a bit tricky to prove.
A rational system of inequalities $Ax≤b$ is totally dual integral (TDI) if, for all integral $c$, $\{\min y^Tb ∣ y≥0,y^TA=c\}$ is attained by an integral vector $\hat{y}$ whenever the optimum exists and is finite.
You can show that if a matrix $A$ is TU, then $Ax\leq b$ is TDI for all rational $b$.

As some other folks have pointed out your problem might fall into a specific problem type, for example set packing. For those problems there could be specialized approximation algorithms which guarantee a certain optimality gap.

Answer 3

While this class of problems is still hard to solve (see the other answers for details), one speciality is that it has a trivial feasible solution $x=0$, which is not the case in general integer programming.

Answer 4

AFAIK, your model constraint is a special case of the 0,1-knapsack inequality with binary parameters. Even for a rather large problem (which A is a 1000*1000 matrix) the problem is solved resonably.

BLOCKS OF EQUATIONS           2     SINGLE EQUATIONS        1,001
BLOCKS OF VARIABLES           2     SINGLE VARIABLES        1,001
NON ZERO ELEMENTS       501,753     DISCRETE VARIABLES      1,000

Space for names approximately 0.03 Mb
Use option 'names no' to turn use of names off
MIP status(107): time limit exceeded
Cplex Time: 1000.02sec (det. 592962.48 ticks)
Fixing integer variables, and solving final LP...
Fixed MIP status(1): optimal
Cplex Time: 0.02sec (det. 26.90 ticks)
Resource limit exceeded.

Root node processing (before b&c):
  Real time             =   10.00 sec. (7157.25 ticks)
Parallel b&c, 4 threads:
  Real time             =  990.02 sec. (585805.23 ticks)
  Sync time (average)   =   35.25 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) = 1000.02 sec. (592962.48 ticks)

MIP Solution:          730.011130    (3528690 iterations, 74270 nodes)
Final Solve:           730.011130    (0 iterations)

Best possible:         785.426613
Absolute gap:           55.415484
Relative gap:            0.070555

Update: as @ Marco Lübbecke said, there are also other ways to solve such a problem like dynamic programming. I try to show that, it is possible to solve this problem using the static model by any MIP solver.