Duality in MIP

Elena V. Pachkova
Copenhagen University, Denmark

Ladda ner artikel

Ingår i: Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Linköping Electronic Conference Proceedings 14:20, s.

Visa mer +

Publicerad: 2004-12-28


ISSN: 1650-3686 (tryckt), 1650-3740 (online)


This presentation treats duality in Mixed Integer Programming (MIP in short). A dual of a MIP problem includes a dual price function F; that plays the same role as the dual variables in Linear Programming (LP in the following).

The price function is generated while solving the primal problem. However; different to the LP dual variables; the characteristics of the dual price function depend on the algorithmic approach used to solve the MIP problem. Thus; the cutting plane approach provides nondecreasing and superadditive price functions while branch and bound algorithm generates piecewise linear; nondecreasing and convex price functions. Here a hybrid algorithm based on branch and cut is investigated; and a price function for that algorithm is established. This price function presents a generalization of the dual price functions obtained by either the cutting plane or the branch and bound method.


Inga nyckelord är tillgängliga


Inga referenser tillgängliga

Citeringar i Crossref