Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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?
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.
