• Stars
    star
    118
  • Rank 299,923 (Top 6 %)
  • Language
    C++
  • License
    Eclipse Public Li...
  • Created over 6 years ago
  • Updated about 2 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

A solver for mixed-integer nonlinear optimization problems

CMake License

The Supporting Hyperplane Optimization Toolkit

SHOT is a software for solving mathematical optimization problems of the mixed-integer nonlinear programming (MINLP) class. In addition to MINLP problems, SHOT can also be used for subclasses such as NLP and MI(QC)QP.

Originally SHOT was intended for convex MINLP problems only, but as of version 1.0 it also has functionality to solve nonconvex MINLP problems as a heuristic method without providing any guarantees of global optimality. SHOT can solve certain nonconvex problem types to global optimality as well, and the bounds for the objective function value are guaranteed for nonconvex problems as well.

SHOT can be used

SHOT requires a MILP solver: Cplex, Gurobi or Cbc. In addition an NLP solver is required; currently only Ipopt is supported. If SHOT is interfaced with GAMS, any licensed NLP solver can be used.

The documentation is provided at the project website at https://www.shotsolver.dev.

SHOT is a COIN-OR project, and won the COIN-OR Cup 2018. Project manager is Andreas Lundell. A full list of contributors is available on the project website.

Dual bound through polyhedral (outer) approximation

SHOT is based on iteratively creating a tighter polyhedral approximation of the nonlinear feasible set by generating supporting hyperplanes or cutting planes. These linearized problems are then solved with an mixed-integer linear programming (MILP) solver such as CPLEX, Gurobi or Cbc. If CPLEX or Gurobi is used, the subproblems can also include quadratic and bilinear nonlinearities directly; then MIQP or MIQCQP subproblems are solved.

Primal bound using heuristics

The solution to the outer approximation problem provides a lower (dual) bound (when solving a minimization problem) to the original problem if the problem is convex. If the problem is nonconvex, convergence to the global optimal solution cannot be guaranteed (but might be achieved for certain classes of problems, cf. this paper.

To get an upper (primal) bound (when solving a minimization problem) on the optimal solution SHOT utilizes the following heuristics:

  • Solving nonlinear programming (NLP) problems where the integer variables have been fixed to valid values. This is done by calling an external NLP solver (e.g. Ipopt).
  • By checking solutions from the MIP solver's solution pool for points that fulfill also the nonlinearities in the original MINLP problem.
  • By performing root searches.

Termination

When the relative or absolute difference (objective gap) between the primal and dual bounds is less than a user-specified value, SHOT terminates with the current primal solution. If the original problem is convex, this is a global solution to the problem. If it is nonconvex, there is normally no guarantee that such a solution can be found, however SHOT will always in addition to the primal solution give a valid lower bound on the solution.

Compilation instructions

Instructions for compiling SHOT is available at the project website.

Solver manual

Instructions for how to use SHOT, e.g. call it from different environments, are provided on the project website.

Publications

SHOT is best described in the paper:

Lundell, A. Kronqvist, J. and Westerlund, T. The supporting hyperplane optimization toolkit for convex MINLP. Journal of Global Optimization (2022). https://link.springer.com/article/10.1007/s10898-022-01128-0

The features for solving nonconvex MINLP problems are described in the papers:

Lundell, A. and Kronqvist, J., Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT. Journal of Global Optimization (2021). https://doi.org/10.1007/s10898-021-01006-1

Lundell, A. and Kronqvist, J. On Solving Nonconvex MINLP Problems with SHOT (2019). In: Le Thi H., Le H., Pham Dinh T. (editors) Optimization of Complex Systems: Theory, Models, Algorithms and Applications. WCGO 2019. Advances in Intelligent Systems and Computing, vol 991. Springer, Cham.

More Repositories

1

pulp

A python Linear Programming API
Python
2,058
star
2

Ipopt

COIN-OR Interior Point Optimizer IPOPT
C++
1,082
star
3

Cbc

COIN-OR Branch-and-Cut solver
C++
620
star
4

python-mip

Python-MIP: collection of Python tools for the modeling and solution of Mixed-Integer Linear programs
Python
520
star
5

CppAD

A C++ Algorithmic Differentiation Package: Home Page
C++
375
star
6

Clp

COIN-OR Linear Programming Solver
C++
321
star
7

qpOASES

Open-source C++ implementation of the recently proposed online active set strategy
C++
261
star
8

rbfopt

RBFOpt library for black-box optimization
Python
181
star
9

CyLP

A Python interface to CLP, CBC, and CGL to solve LPs and MIPs.
JetBrains MPS
175
star
10

Gravity

Mathematical Modeling for Optimization and Machine Learning
C++
149
star
11

COIN-OR-OptimizationSuite

A harness for building the bundled suite of interoperable optimization tools available in the COIN-OR repository.
Shell
105
star
12

Bonmin

Basic Open-source Nonlinear Mixed INteger programming
C++
103
star
13

ADOL-C

A Package for Automatic Differentiation of Algorithms Written in C/C++
C++
94
star
14

Cbc.old

This is a mirror of the subversion repository on COIN-OR
C++
88
star
15

minotaur

Minotaur Toolkit for Mixed-Integer Nonlinear Optimization
C++
68
star
16

GrUMPy

A Python library for visualizing algorithms for solving mathematical optimization problems.
Shell
60
star
17

SYMPHONY

SYMPHONY is an open-source solver, callable library, and development framework for mixed-integer linear programs (MILPs) written in C with a number of unique features
C
59
star
18

Couenne

Convex Over and Under Envelopes for Nonlinear Estimation
C++
55
star
19

jorlib

Java Operations Research Library
Java
54
star
20

Csdp

This is the working repository for the CSDP project. CSDP is a solver for semidefinite programming problems. It is a COIN-OR project.
C
52
star
21

MibS

A solver for mixed integer bilevel programs
JetBrains MPS
50
star
22

Osi

Open Solver Interface
C++
48
star
23

CoinUtils

COIN-OR Utilities
C++
44
star
24

Rehearse

Algebraic modeling library in C++ for linear optimization solvers
M4
42
star
25

prtpy

Number partitioning in Python
Python
42
star
26

Clp.old

This a mirror of the subversion repository on COIN-OR.
C++
36
star
27

GiMPy

A graph library containing pure Python implementations of a variety of graph algorithms
Python
33
star
28

coinbrew

COIN-OR build and installation script
Shell
26
star
29

metslib

An Open Source Tabu Search Metaheuristic framework in C++
C++
25
star
30

Bcp

Branch-Cut-Price Framework
C++
24
star
31

Cgl

Cut Generator Library
C++
21
star
32

VRPH

VRPH is an open source library of heuristics for the capacitated Vehicle Routing Problem (VRP).
C++
19
star
33

SYMPHONY.old

This a mirror of the subversion repository on COIN-OR.
C
16
star
34

Dip

DIP is a decomposition-based solver framework for mixed integer linear programs.
C++
15
star
35

Osi.old

This a mirror of the subversion repository on COIN-OR.
C++
11
star
36

Sonnet

A wrapper for COIN-OR mixed integer linear programming via OSI to Microsoft .NET
C#
10
star
37

Dip.old

This a mirror of the subversion repository on COIN-OR.
C++
10
star
38

CoinMP

C-API library for CLP, CBC, and CGL
Shell
9
star
39

Cmpl

<Coliop|Coin> Mathematical Programming Language
C++
9
star
40

CHiPPS-ALPS

This is the Abstract Library for Parallel Search (ALPS), the abstract base layer of the COIN-OR High Performance Parallel Search framework.
C++
8
star
41

FlopCpp

An open source algebraic modelling language implemented as a C++ class library
Shell
8
star
42

oBB

Overlapping Branch and Bound Algorithm
C++
8
star
43

GAMSlinks

Links between GAMS (General Algebraic Modeling System) and solvers
C++
8
star
44

DisCO

Discrete Conic Optimization Solver
C++
7
star
45

filterSD

a library for nonlinear optimization written in Fortran
Fortran
7
star
46

CoinUtils.old

This a mirror of the subversion repository on COIN-OR.
C++
7
star
47

Paver

Python scripts to do comparisons on solver performance
Python
7
star
48

Vol

A C++ implementation of the volume algorithm for linear programming
Shell
7
star
49

Couenne.old

This a mirror of the subversion repository on COIN-OR. For bugtracking and wiki, see website.
C++
7
star
50

CHiPPS-BLIS

This is the BiCePS Linear Integer Solver (BLIS), a parallel solver for mixed integer linear programs that is implemented on top of the BiCePS layer of the CHiPPS framework.
C++
6
star
51

jMarkov

Java framework for Markov-chain (MC) modelling
Java
5
star
52

yaposib

Python binding to coin-osi
C++
5
star
53

Cgl.old

This a mirror of the subversion repository on COIN-OR.
C++
4
star
54

metslib-examples

Examples for METSLib
C++
4
star
55

ROSE

Reformulation-Optimization Software Engine
C++
3
star
56

Smi

An API for stochastic programming problems.
Shell
3
star
57

DyLP

Dynamic Simplex solver
C
2
star
58

CoinMP.old

Mirror of the CoinMP project from https://projects.coin-or.org/svn/CoinMP
Shell
2
star
59

coin-or.github.io

COIN-OR General Documentation
HTML
2
star
60

Osi2

Open Solver Interface Version 2
C++
1
star
61

MOCHA

Algorithms and heuristics to solve multicriteria matroid optimization problems
M4
1
star
62

Cgc

Cgc is a collection of network representations to facilitate the development and implementation of network algorithms.
C++
1
star
63

OS

Optimization Services
C++
1
star
64

PFunc

Generic task-parallel library for C/C++
C++
1
star
65

NLPAPI

NLPAPI is a set of subroutines and data structures for defining nonlinear programming problems. It includes an interface to call LANCELOT to solve the problem (you need to get your own copy of LANCELOT), and an interface to IPOPT.
C
1
star