Optimization Online


Polyhedral Approximation Strategies in Nonconvex Mixed-Integer Nonlinear Programming

Andreas Lundell(andreas.lundell***at***abo.fi)
Jan Kronqvist(j.kronqvist***at***imperial.ac.uk)

Abstract: Different versions of polyhedral outer approximation is used by many algorithms for mixed-integer nonlinear programming (MINLP). While it has been demonstrated that such methods work well for convex MINLP, extending them to solve also nonconvex problems has been challenging. One solver based on outer linearization of the nonlinear feasible set of MINLP problems is the Supporting Hyperplane Optimization Toolkit (SHOT). SHOT is an open source COIN-OR project, and is currently one of the most efficient global solvers for convex MINLP. In this paper, we discuss some extensions to SHOT that significantly extend its applicability to nonconvex problems. The functionality include utilizing convexity detection for selecting the nonlinearities to linearize, lifting reformulations for special classes of functions, feasibility relaxations for infeasible subproblems and adding objective cuts to force the search for better feasible solutions. This functionality is not unique to SHOT, but can be implemented in other similar methods as well. In addition to discussing the new nonconvex functionality of SHOT, an extensive benchmark of deterministic solvers for nonconvex MINLP is performed that provides a snapshot of the current state of nonconvex MINLP.

Keywords: Nonconvex MINLP; Supporting Hyperplane Optimization Toolkit (SHOT); Reformulation techniques; Local MINLP techniques; Feasibility relaxation

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

Category 2: Optimization Software and Modeling Systems (Optimization Software Design Principles )

Category 3: Optimization Software and Modeling Systems (Optimization Software Benchmark )


Download: [PDF]

Entry Submitted: 03/20/2020
Entry Accepted: 03/20/2020
Entry Last Modified: 03/20/2020

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