Publicerad: 2004-12-28
ISBN:
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 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.
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.
