# Duality in mixed integer linear programs

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?

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.