MINLP Strengthening for Separable Convex Quadratic Transportation-Cost UFL

Oktay Gunluk(gunlukus.ibm.com)
Jon Lee(jonleeus.ibm.com)
Robert Weismantel(weismantelimo.math.uni-magdeburg.de)

Abstract: In the context of a variation of the standard UFL (Uncapacitated Facility Location) problem, but with an objective function that is a separable convex quadratic function of the transportation costs, we present some techniques for improving relaxations of MINLP formulations. We use a disaggregation principle and a strategy of developing model-specific valid inequalities (some nonlinear), which enable us to significantly improve the quality of the NLP (Nonlinear Programming) relaxation of our MINLP model. Additionally, we describe some directions in which our methodology can be extended.

Keywords: facility location, mixed integer nonlinear programming, outer approximation

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

Citation: IBM Research Report RC24213

Download: [PDF]

Entry Submitted: 03/15/2007
Entry Accepted: 03/15/2007
Entry Last Modified: 03/15/2007

Modify/Update this entry