Optimization Online


Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools

Joey Huchette (huchette***at***mit.edu)
Juan Pablo Vielma (jvielma***at***mit.edu)

Abstract: We present novel mixed-integer programming (MIP) formulations for (nonconvex) piecewise linear functions. Leveraging recent advances in the systematic construction of MIP formulations for disjunctive sets, we derive new formulations for univariate functions using a geometric approach, and for bivariate functions using a combinatorial approach. All formulations derived are small (logarithmic in the number of piecewise segments of the function domain) and strong, and we present extensive computational experiments in which they offer substantial computational performance gains over existing approaches. We characterize the connection between our geometric and combinatorial formulation approaches, and explore the benefits and drawbacks of both. Finally, we present PiecewiseLinearOpt, an extension of the JuMP modeling language in Julia that implements our models (alongside other formulations from the literature) through a high-level interface, hiding the complexity of the formulations from the end-user.

Keywords: Piecewise linear, Integer programming

Category 1: Integer Programming


Download: [PDF]

Entry Submitted: 07/31/2017
Entry Accepted: 07/31/2017
Entry Last Modified: 10/08/2019

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