Optimization Online


Some lower bounds on sparse outer approximations of polytopes

Santanu S. Dey(santanu.dey***at***isye.gatech.edu )
Andres Iroume(airoume***at***gatech.edu)
Marco Molinaro(molinaro***at***isye.gatech.edu)

Abstract: Motivated by the need to better understand the properties of sparse cutting-planes used in mixed integer programming solvers, the paper [1] studied the idealized problem of how well a polytope is approximated by the use of sparse valid inequalities. As an extension to this work, we study the following “less idealized” questions in this pa- per: (1) Are there integer programs, such that sparse inequalities do not approximate the integer hull well even when added to a linear programming relaxation? (2) Are there polytopes, where the quality of approximation by sparse inequalities cannot be significantly improved by adding a budgeted number of arbitrary (possibly dense) valid in- equalities? (3) Are there polytopes that are difficult to approximate under every rotation? (4) Are there polytopes that are difficult to approximate in all directions using sparse inequalities? We answer each of the above questions in the positive.

Keywords: Sparse inequalities, approximations of polytopes

Category 1: Integer Programming

Citation: ISyE Georgia Tech, TU Delft, 12/2014

Download: [PDF]

Entry Submitted: 12/11/2014
Entry Accepted: 12/11/2014
Entry Last Modified: 12/11/2014

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