Open-source MINLP solver
SHOT combines polyhedral outer approximation with primal heuristics. Use it from GAMSPy, Pyomo, JuMP, AMPL, C++ or Python.
pip install SHOTpy
01 — Overview
SHOT, the Supporting Hyperplane Optimization Toolkit, is an open-source solver for mixed-integer nonlinear programming (MINLP), written in C++. It is global for convex MINLP, and mainly a heuristic for nonconvex MINLP, where the bounds on the objective value are still guaranteed.
A reformulation engine rewrites each problem into a form that suits the method, and some nonconvex problem types are reformulated into convex ones and solved to global optimality.
Problems
MINLP and its subclasses: NLP, MIQP and MIQCQP
Method
Polyhedral outer approximation (ESH and ECP) combined with primal heuristics
Subsolvers
MIP: CPLEX, Gurobi, Cbc or HiGHS. NLP: Ipopt, Uno, or any NLP solver in GAMS
Interfaces
GAMSPy, GAMS, Python (SHOTpy), C++, the command line, and AMPL, Pyomo and JuMP through ASL
Problem formats
OSiL, AMPL .nl and GAMS .gms
Community
A COIN-OR project, winner of the COIN-OR Cup 2018, licensed under EPL-2.0
02 — Method
The outer approximation gives a lower bound on the objective, feasible solutions an upper bound. SHOT terminates when the gap between them is within tolerance.
Try it
minimize −0.94x₁ + 0.34x₂
subject to g₁(x) ≤ 0, g₂(x) ≤ 0
where 0 ≤ x ≤ 10, x₁ integer
Computed in your browser with the same steps as SHOT's dual and primal strategies, on a problem small enough to draw. Termination at an objective gap of 0.01 %.
Dual strategy
Primal strategy
03 — Capability
It depends on the MIP subsolver. Nonconvex problems are always solved with valid bounds, but the gap may not close. If all nonconvexities can be reformulated into convex form, for example bilinear terms with a discrete variable, the solution is global.
More in Lundell and Kronqvist (2022).
| Problem type | CPLEX | Gurobi | Cbc | HiGHSnew |
|---|---|---|---|---|
| Convex MIQP | ||||
| Convex MIQCQP | ||||
| Convex MINLP | ||||
| Nonconvex MIQP | ? | ? | ||
| Nonconvex MIQCQP | ? | ? | ? | |
| Nonconvex MINLP | ? | ? | ? | ? |
New version
A Python interface, HiGHS as MIP subsolver, and callbacks that let you take part in the solution process.
.nl, .gms and OSiL files04 — News
SHOT 2.0 adds a Python interface, HiGHS as MIP subsolver and extended callbacks. Install it with pip install SHOTpy.
Andreas Lundell presented the new features of SHOT 2.0 at the SIAM Conference on Optimization in Edinburgh.
A new preprint describes the eigenvalue and LDLᵀ decomposition-based reformulations of convex quadratic expressions in SHOT 2.0.
05 — Cite
Please cite the SHOT paper. If you use SHOT on nonconvex problems, please also cite the paper on its nonconvex features.
The SHOT paper
A. Lundell, J. Kronqvist, T. Westerlund. The supporting hyperplane optimization toolkit for convex MINLP. Journal of Global Optimization, 84(1), 1–41, 2022. doi:10.1007/s10898-022-01128-0
Nonconvex MINLP
A. Lundell, J. Kronqvist. Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT. Journal of Global Optimization, 82(4), 863–896, 2022. doi:10.1007/s10898-021-01006-1