Optimization Online


A new lift-and-project operator

Merve Bodur (merve.bodur***at***gatech.edu)
Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Oktay Gunluk (gunluk***at***us.ibm.com)

Abstract: In this paper, we analyze the strength of split cuts in a lift-and-project framework. We first observe that the Lovasz-Schrijver and Sherali-Adams lift-and-project operator hierarchies can be viewed as applying specific 0-1 split cuts to an appropriate extended formulation and demonstrate how to strengthen these hierarchies using additional split cuts. More precisely, we define a new operator that adds all 0-1 split cuts to the extended formulation. For 0-1 mixed-integer sets with k binary variables, this new operator is guaranteed to obtain the integer hull in k/2 steps compared to k steps for the Lovasz-Schrijver or the Sherali-Adams operator. We also present computational results on the stable set problem with our new operator.

Keywords: Lift-and-project, extended formulations, cutting planes

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: IBM Research Report

Download: [PDF]

Entry Submitted: 09/30/2015
Entry Accepted: 09/30/2015
Entry Last Modified: 03/03/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society