Article | Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society | Duality in MIP. Generating Dual Price Functions Using Branch-and-Cut

Title:
Duality in MIP. Generating Dual Price Functions Using Branch-and-Cut
Author:
Elena V. Pachkova:
Download:
Full text (pdf)
Year:
2004
Conference:
Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society
Issue:
014
Article no.:
005
Pages:
73-87
No. of pages:
15
Publication type:
Abstract and Fulltext
Published:
2004-12-28
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press; Linköpings universitet


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 non-decreasing 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.

Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Author:
Elena V. Pachkova
Title:
Duality in MIP. Generating Dual Price Functions Using Branch-and-Cut
References:

E. Balas; S. Ceria; G. Cornuejols; "A lift-and-project cutting plan algorithm for mixed 0-1 programs"; Mathematical Programming 58; pp. 295-324; 1993.


E. Balas; S. Ceria; G. Cornuejols; "Mixed 0-1 Programming by Lift-and-Project in Branch- and-Cut Framework"; Management Science 42; 1996.


C. Cordier; H. Marchand; R. Laundy; L.A. Wolsey; "A branch-and-cut code for mixed integer programming"; Mathematical Programming 86; pp. 335-353; 1999.


H. Crowder; E.L. Johnson; M.W. Padberg; "Solving Large Scale Zero-One Linear Pro- gramming Problems"; Operation Research 31; pp. 803-834; 1983.


S.I. Gass; "Linear Programming"; 5th ed.;McGraw-Hill; (1985).


R.E. Gomory; "An algorithm for the mixed integer problem"; RM-2597; The Rand Cor- poration; 1960.


S. Holm; J. Tind; " A Uni¬Įed Approach for Price Directive Decomposition Procedures in Integer Programming"; Discrete Applied Mathematics 20; pp. 205-219; 1988.


E. L. Johnson; Georg L. Nemhauser; Martin W. P. Savelsbergh; "Progress in linear Pro- gramming Based Branch-and-Bound Algorithms: An Exposition"; INFORMS Journal on Computing 12; 2000.


K.Klamroth; J. Tind; S. Zust; "Integer Programming Duality in Multiple Objective Pro- gramming"; University of Copenhagen; Department of Applied Mathematics and Statistics; 2002.


J.D.C. Little; K.G. Murty; D.W. Sweeney and C. Karel; "An Algorithm for the Travelling Salesman Problem"; Operation Research 11; pp. 972-989; 1963.


L. Lovasz and A. Schrijver; "Cones of matrices and set functions and 0-1 optimization"; SIAM Journal on Optimization 1(2); pp. 166-190; 1991


H. Marchand; A. Martin; R. Weismantel; L.A. Wolsey; "Cutting Planes in Integer and Mixed Integer Programming"; CORE Discussion Paper 9953; 1999.


H. Marchand; L.A. Wolsey; "Aggregation and Mixed Integer Rounding to Solve MIPs"; Operation Research; Vol. 49; No. 3; pp. 363-371; 2001.


G. L. Nemhauser; L. A. Wolsey; "A Recursive Procedure to Generate all Cuts for 0-1 Mixed Integer Programs"; Mathematical Programming 46; pp. 379-390; 1990.


G. L. Nemhauser; L. A. Wolsey; "Integer and Combinatorial Optimization"; John Wiley & Sons; Inc; 1999.


M. Padberg; G. Rinaldi; "Optimization of a 537-city TSP by branch and cut"; Operations Research Letters 6; pp. 1-8; 1987.


H.M. Salkin; K. Mathur; "Foundations of Integer Programming"; North-Holland; 1989.


W. White; "On Gomory’s Mixed Integer Algorithm"; Senior Thesis; Princeton University; May 1961.


L.A. Wolsey; "Integer Programming Duality: Price Functions and Sensitivity Analysis"; Mathematical Programming; 20; pp. 173-195; 1981.

Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Author:
Elena V. Pachkova
Title:
Duality in MIP. Generating Dual Price Functions Using Branch-and-Cut
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment