14
$\begingroup$

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

Improve this question
$\endgroup$
8
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ To add to this answer, there is also a lot of work that has been done with approximation algorithms for the set packing problem. $\endgroup$ – batwing Oct 10 '19 at 2:40
13
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You might also perhaps want to look into balanced and perfect matrices, which are generalizations of totally unimodular matrices. $\endgroup$ – Ryan Cory-Wright Oct 10 '19 at 3:13
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ it would be much faster if you solved this by dynamic programming $\endgroup$ – Marco Lübbecke Oct 9 '19 at 14:19
  • $\begingroup$ I suppose that a dynamic programming algorithm is $O(n \prod_{i=1}^{m} b_i)$ in this case. Thus, assuming $b_i \leq n$ it is $O(n^{m+1})$ yet. $\endgroup$ – Alexandre Frias Oct 9 '19 at 21:54
  • $\begingroup$ @MarcoLübbecke, AFAIK, to solve knapsack inequality efficiently, there are cover cuts families that could be applied. In the above specific problem, Cplex and Gurobi do not use any cover cuts families (they used Gomory cuts). Would you know the reasons for this behaviour? $\endgroup$ – A.Omidi Oct 10 '19 at 7:43
  • $\begingroup$ my bad; I was reading your answer as "this is a (binary) knapsack problem", not several at once; $\endgroup$ – Marco Lübbecke Oct 10 '19 at 7:46

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.