Optimization Online


Valid Inequalities for Separable Concave Constraints with Indicator Variables

Cong Han Lim (conghan***at***cs.wisc.edu)
Jeff Linderoth (linderoth***at***wisc.edu)
James Luedtke (jrluedt1***at***wisc.edu)

Abstract: We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MILP only. We propose a technique to obtain valid inequalities that are based on both the MILP constraints and the concave constraints. We begin by characterizing the convex hull of a four-dimensional set consisting of a single binary indicator variable, a single concave constraint, and two linear inequalities. Using this analysis, we demonstrate how valid inequalities for the single node flow set and for the lot-sizing polyhedron can be to ``tilted'' to give valid inequalities that also account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities for nonlinear transportation problems and for lot-sizing problems with concave costs. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed integer nonlinear programs.


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


Download: [PDF]

Entry Submitted: 11/25/2015
Entry Accepted: 11/25/2015
Entry Last Modified: 06/06/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