Optimization Online


Analysis of Sparse Cutting-plane for Sparse MILPs with Applications to Stochastic MILPs

Santanu Dey(santanu.dey***at***isye.gatech.edu)
Marco Molinaro(molinaro.marco***at***gmail.edu)
Qianyi Wang(qwang32***at***gatech.edu)

Abstract: In this paper, we present an analysis of the strength of sparse cutting-planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is non-negative. Given a MILP instance of one of these three types, assume that we decide on the support of cutting-planes to be used and the strongest inequalities on these supports are added to the linear programming relaxation. Call the optimal objective function value of the linear programming relaxation together with these cuts as zcut. We present bounds on the ratio of zcut and the optimal objective function value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. These results also shed light on the strength of scenario-specific cuts for two stage stochastic MILPs.

Keywords: Cutting-planes, Sparsity

Category 1: Integer Programming (Cutting Plane Approaches )

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


Download: [PDF]

Entry Submitted: 01/02/2016
Entry Accepted: 01/02/2016
Entry Last Modified: 01/02/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