3

In a mixed integer programming question how one may find the dual of the equality constraint? As example:

$min \quad C^T X$

$s.t. \quad aX\leq b$

$\qquad eX=d$

$\qquad X\in integers$

How to find the duals of constraints $eX=d$

Morry
  • 131

1 Answers1

3

The traditional definition of duality as applied to linear programming cannot be directly applied to integer programs. Lagrangian duality is, after all, a continuous concept. A dual cost $\lambda$ associated with the equality constraints $eX=d$ measures the change in the objective given a small perturbation in $d$. But since the values of $X$ are integers, there is no guarantee that such a perturbation would even maintain feasibility.

That is not to say, however, that researchers have not attempted to extend the notion of duality to integer programs, providing useful analogues of dual variables for integer problems. A quick perusal of Google search results led me to two promising references:

  • Laurence A. Wolsey, Integer programming duality: price functions and sensitivity analysis, Mathematical Programming, Vol. 20, pp. 173-195, 1981.
  • M. Güzelsoy and T. K. Ralphs, "Integer Programming Duality," in Encyclopedia of Operations Research and Management Science, Cochran, J., Ed., Wiley, 2010. PDF download

Certainly a perusal of these bibliographies, particularly in the second case, will yield even more useful information.

Michael Grant
  • 19,450