Paper Info
Title
Valid Inequalities for Separable Concave Constraints with Indicator Variables.
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 “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.
Year
DOI
Venue
2018
10.1007/s10107-017-1197-5
IPCO
Keywords
DocType
Volume
90C11,90C26
Journal
172
Issue
ISSN
Citations 
1-2
0025-5610
0
PageRank 
References 
Authors
0.34
13
3
Name
Order
Citations
PageRank
Cong Han Lim192.17
Jeff Linderoth265450.26
James Luedtke343925.95