|Fulltext||0.18 MB||PDF (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|
|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.
|No. of pages:||15|
|Series:||Linköping Electronic Conference Proceedings|
|Publisher:||Linköping University Electronic Press; Linköpings universitet|
|REFERENCE TO THIS PAGE |