Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

New Variants of Lift-and-Project Cut Generation from the LP Tableau: Open Source Implementation and Testing

Egon BalasContact Information and Pierre BonamiContact Information

(1)  Tepper School of Business, Carnegie Mellon University, Pittsburgh PA, .,  
(2)  T.J. Watson Research Center, IBM, Yorktown Heights, NY,  
Abstract
We discuss an open source implementation and preliminary computational testing of three variants of the Balas-Perregaard procedure for generating lift-and-project cuts from the original simplex tableau, two of which are new. Variant 1 is the original procedure of [6] with minor modifications. Variant 2 uses a new procedure for choosing the pivot element: After identifying the set of row candidates for an improving pivot, the pivot element (and column) is chosen by optimizing over the entries of all candidate rows. Finally, Variant 3 replaces the source row with its disjunctive modularization, and after each pivot it again modularizes the resulting source row. We report on computational results with the above three variants and their combinations on 65 MIPLIB.3 instances.

Keywords  integer programming - branch and cut algorithms


Contact Information Egon Balas
Email: eb17@andrew.cmu.edu

Contact Information Pierre Bonami
Email: pbonami@us.ibm.com
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
1 newer article

  1. Dash, Sanjeeb (2008) MIR closures of polyhedral sets. Mathematical Programming
    [CrossRef]
Remote Address: 38.107.191.84 • Server: mpweb22
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)