×

SHOT

swMATH ID: 15630
Software Authors: Kronqvist, Jan; Lundell, Andreas; Westerlund, Tapio
Description: The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming. A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented.
Homepage: http://link.springer.com/article/10.1007/s10898-015-0322-3
Keywords: convex mixed integer nonlinear programming; extended supporting hyperplane algorithm; extended cutting plane algorithm; supporting hyperplanes; cutting planes; supporting hyperplane optimization toolkit
Related Software: Ipopt; MINLPLib; Bonmin; ANTIGONE; SCIP; Decogo; AlphaECP; Pyomo; MINLP; LINDO; BARON; Muriqui; MINOTAUR; DICOPT; FEASPUMP; Gurobi; LINDOGlobal; Juniper; JuMP; PAVER
Referenced in: 23 Publications

Referencing Publications by Year