SHOT

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.


References in zbMATH (referenced in 20 articles , 1 standard article )

Showing results 1 to 20 of 20.
Sorted by year (citations)

  1. Le Thi, Hoai An (ed.); Pham Dinh, Tao (ed.); Sergeyev, Yaroslav D. (ed.): Preface to the special issue dedicated to the 6th world congress on global optimization held in Metz, France, July 8--10, 2019 (2022)
  2. Lundell, Andreas; Kronqvist, Jan: Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT (2022)
  3. Sharma, Meenarli; Palkar, Prashant; Mahajan, Ashutosh: Linearization and parallelization schemes for convex mixed-integer nonlinear optimization (2022)
  4. Allman, Andrew; Zhang, Qi: Branch-and-price for a class of nonconvex mixed-integer nonlinear programs (2021)
  5. Berthold, Timo; Witzig, Jakob: Conflict analysis for MINLP (2021)
  6. Brito, Samuel Souza; Santos, Haroldo Gambini: Preprocessing and cutting planes with conflict graphs (2021)
  7. Davarnia, Danial; van Hoeve, Willem-Jan: Outer approximation for integer nonlinear programs via decision diagrams (2021)
  8. Kronqvist, Jan; Misener, Ruth: A disjunctive cut strengthening technique for convex MINLP (2021)
  9. Muts, Pavlo; Nowak, Ivo; Hendrix, Eligius M. T.: On decomposition and multiobjective-based column and disjunctive cut generation for MINLP (2021)
  10. Neumann, Christoph; Stein, Oliver: Generating feasible points for mixed-integer convex optimization problems by inner parallel cuts (2021)
  11. De Mauri, Massimo; Gillis, Joris; Swevers, Jan; Pipeleers, Goele: A proximal-point outer approximation algorithm (2020)
  12. Kronqvist, Jan; Bernal, David E.; Grossmann, Ignacio E.: Using regularization and second order information in outer approximation for convex MINLP (2020)
  13. Melo, Wendel; Fampa, Marcia; Raupp, Fernanda: An overview of MINLP algorithms and their implementation in Muriqui optimizer (2020)
  14. Muts, Pavlo; Nowak, Ivo; Hendrix, Eligius M. T.: The decomposition-based outer approximation algorithm for convex mixed-integer nonlinear programming (2020)
  15. Serrano, Felipe; Schwarz, Robert; Gleixner, Ambros: On the relation between the extended supporting hyperplane algorithm and Kelley’s cutting plane algorithm (2020)
  16. Serra, Thiago: Reformulating the disjunctive cut generating linear program (2020)
  17. Nowak, Ivo; Muts, Pavlo; Hendrix, Eligius M. T.: Multi-tree decomposition methods for large-scale mixed integer nonlinear optimization (2019)
  18. Kronqvist, Jan; Lundell, Andreas; Westerlund, Tapio: Reformulations for utilizing separability when solving convex MINLP problems (2018)
  19. Westerlund, Tapio; Eronen, Ville-Pekka; Mäkelä, Marko M.: On solving generalized convex MINLP problems using supporting hyperplane techniques (2018)
  20. Kronqvist, Jan; Lundell, Andreas; Westerlund, Tapio: The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming (2016)