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 4/16/2014)