Files:DescriptionFile size FormatBrowse
Fulltext0.18 MBPDF (requires Acrobat Reader)Previous | Next
  
Authors:Elena V. Pachkova:
Publication title:Duality in MIP. Generating Dual Price Functions Using Branch-and-Cut
Conference:Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society
Publication type: Abstract and Fulltext
Issue:014
Article No.:005
Abstract: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.

Language:English
Year:2004
No. of pages:15
Pages:73-87
Series:Linköping Electronic Conference Proceedings
ISSN (print):1650-3686
ISSN (online):1650-3740
File:http://www.ep.liu.se/ecp/014/005/ecp014005.pdf
Available:2004-12-28
Publisher:Linköping University Electronic Press; Linköpings universitet

REFERENCE TO THIS PAGE
Elena V. Pachkova (2004). Duality in MIP. Generating Dual Price Functions Using Branch-and-Cut, Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society http://www.ep.liu.se/ecp_article/index.en.aspx?issue=014;article=005 (accessed 9/30/2014)