14
$\begingroup$

I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual problem and whether this extends to any integer program?

For example, an integer program with a totally unimodular coefficient matrix has integral extreme points. Does this property hold for the dual of such a linear program? What can be said about duality of integer programs in general?

$\endgroup$
13
$\begingroup$

It is a difference whether one can dualize (or not) or that a duality theory holds (or not). Formally, you can formulate a dual of any integer program, e.g., by considering the linear relaxation, dualizing it, and then enforcing integrality again on the dual variables. It is already trickier which variables to consider as integer in the dual when you dualize a mixed-integer program; but for integer programs, this formally works.

When you are lucky, as in the cases you mention, e.g., that the coefficient matrix is TU (and the cost and RHS are integral), then the dual possesses the same nice properties as the primal, essentially since transposing a matrix (what happens when you dualize) does not destroy TUness.

However, when you are unlucky, and this is what you usually are, the matrix does not have any such special property, neither the primal nor the dual are integer when only solving the linear relaxations. So, still, when you consider the two LP relaxations (the primal and the dual), of course they have the same objective function value (strong duality), after all, this is how you constructed the dual. Yet, when you impose integrality again, on the primal and the dual, you usually do not get the same objective function value, there remains a duality gap.

You may consider the maximum (cardinality) matching problem on a general undirected graph $G=(V,E)$. You have a variable $x_{ij}\in\{0,1\}$ whether edge $ij\in E$ is in the matching or not. The classic model reads $$\max\left.\left\{\sum_{ij\in E}x_{ij} \,\,\right\vert\,\, \sum_{ij\in E} x_{ij}\leq1 \;\forall i\in V,\; x_{ij}\in\{0,1\}\; \forall ij\in E\right\}\enspace.$$ If you relax this, dualize (with a dual variable $y_i$ per vertex $i\in V$), and impose integrality on the $y$-variables again, you obtain $$\min \left.\left\{\sum_{i\in V}y_i \,\,\right\vert\,\, y_i+y_j\geq1 \;\forall ij\in E,\; y_i\in\{0,1\}\; \forall i\in V\right\}\enspace,$$ which is the minimum vertex cover problem on $G$. If you consider a cycle of odd length, say length 5, you can match at most 2 pairs, but for covering all the edges you need at least 3 nodes, so the optima do not coincide. If $G$, however, is bipartite (like for a cycle of even length), the underlying node-edge incidence matrix is TU, and strong duality holds for the integer programs because they are, in fact, linear programs.

$\endgroup$
  • $\begingroup$ I like this answer. $\endgroup$ – independentvariable Oct 14 at 18:42
  • $\begingroup$ Thanks Marco. You mentioned integrality of the cost vector. Regarding TU matrices, integrality of extreme points is dependent on the integrality of the right-hand-sides but not the objective function. However, the objective function coefficients form the right-hand-side vector in the dual problem. So what happens when the objective function coefficients are not integral? I think in this case, there exists an optimal basic feasible solution for the dual that is integral, but this is not the case for any extreme point. Is that right? $\endgroup$ – Opt Oct 14 at 22:50
  • $\begingroup$ I believe that you can construct a small counter example, take the coefficient matrix 2x2 as identity matrix and fractional objcetive coefficients; isn't then in the dual only one basic solution and it is fractional? $\endgroup$ – Marco Lübbecke Oct 15 at 3:35
  • $\begingroup$ @MarcoLübbecke Yes, nice counterexample! $\endgroup$ – Opt Oct 15 at 5:26

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.