Skip to content

Python-CasADi-based package containing several algorithms for solving mixed-integer nonlinear programs (MINLPs)

License

Notifications You must be signed in to change notification settings

minlp-toolbox/CAMINO

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

CAMINO: Collection of Algorithms for Mixed-Integer Nonlinear Optimization

This software package provides a Python/CasADi-based implementation of several algorithms for solving mixed-integer nonlinear programs (MINLPs).

Installation and usage

Set up and activate a fresh Python virtual environment (required Python >= 3.8)

virtualenv env --python=python3
source env/bin/activate

Option 1: from PyPi

pip install caminopy
python -m camino <mode> <solver> <problem>

Example: running outer approximation solver (oa) on the example dummy

python -m camino run oa dummy

More info by running

python -m camino -h

Option 2: from GitHub

From the root of the repository

pip install caminopy
python camino <mode> <solver> <problem>

More info by running

python camino -h

Setting environment variables

You can enable or change options using environment variables ([default]):

Environment variable Value Description
DEBUG True/[False] Toggle debugging output
LOG_DATA True/[False] Toggle saving statistics
MIP_SOLVER [gurobi]/highs Configure MIP solver

Example: To enable DEBUG mode type in your terminal

export DEBUG=True

Available MINLP solvers/algorithms

New?: the algorithm is novel and created by the authors of this software.
CVX guarantee?: the algorithm converges to the global optimum when a convex MINLP is given.

Solvers Description New? CVX guarantee?
gbd Generalized Benders Decomposition (Geoffrion, 1972) x
gbd-qp Adaptation of the Generalized Benders Decomposition with an hessian to the cost function x
oa Outer approximation (Fletcher, Leyffer, 1994) x
oa-qp Quadratic outer approximation (Fletcher, Leyffer, 1994)
oa-i Outer approximation improved with safeguard for nonlinear constraints x x
oa-qp-i Quadratic outer approximation improved with safeguard for nonlinear constraints x
s-v-miqp Sequential Voronoi-based MIQP with exact or Gauss-Newton Hessian (Ghezzi et al, 2023)
s-b-miqp Sequential Benders-based MIQP (Ghezzi, Van Roy, et al, 2024) x x
s-tr-milp Sequential MILP trust region approach (De Marchi, 2023) Accept only linear constraints!
fp Feasibility Pump for MINLP (Bertacco, et al, 2007)
ofp Objective Feasibility Pump for MINLP (Sharma, et al, 2016)
rofp Random Objective Feasibility Pump x
bonmin (Bonami, et al, 2006) -- Same as bonmin-bb x
bonmin-bb A nonlinear branch-and-bound algorithm based on solving a continuous nonlinear program at each node of the search tree and branching on variables (Gupta, Ravindran, 1980) x
bonmin-hyb A hybrid outer-approximation / nonlinear programming based branch-and-cut algorithm (Bonami et al. 2008) x
bonmin-oa An outer-approximation based decomposition algorithm (Duran, Grossmann, 1986), (Fletcher, Leyffer, 1994) x
bonmin-qg An outer-approximation based branch-and-cut algorithm (Quesada, Grossmann, 1994) x
bonmin-ifp An iterated feasibility pump algorithm (Bonami, et al, 2009)
cia Combinatorial Integral Approximation (Sager, et al, 2011) using pycombina (Buerger, et al, 2020) -- installation instructions below
nlp Solve the canonical relaxation of the MINLP (integers are relaxed to continuous variables)
nlp-fxd Fix the integer variables of the MINLP and solve the corresponding NLP
mip Solve the given MILP/MIQP (x)

Warm starting

It is possible to warm start every solver with the solution of another one by concatenating with a + the desired solvers when executing python3 camino or python3 -m camino. For instance, to use the solution of the feasibility pump as a warm start to sequential Benders-based MIQP, execute the following:

python camino run fp+s-b-miqp <problem>

Issues with CasADi function eval

Some examples we provided make use of CasADi subroutines (e.g., bspline) which only accept casadi MX symbolics.
If you experience the following error (or similar)

.../casadi/core/function_internal.cpp:2013: 'eval_sx' not defined for BSplineInterpolant

Please goto settings.py and update the default value for _CASADI_VAR to ca.MX.

Install pycombina

Docs

In the folder docs/ we provide two python scripts example.py and stats_analysis.py.

  • example.py shows how to a user can define its own MINLP and call one of the algorithm implemented in this library to solve it.
  • stats_analysis.py shows how one can retrieve the statistics stored by running the algorithms. More advanced statistics analysis is left to the user.
    Note that: to save stats set the env variable LOG_DATA=1 by runnning export LOG_DATA=1 from a terminal console.

Citing

If you find this project useful, please consider giving it a ⭐ or citing it if your work is scientific:

@software{camino,
  author = {Ghezzi, Andrea and Van Roy, Wim},
  license = {GPL-3.0},
  month = oct,
  title = {CAMINO: Collection of Algorithms for Mixed-Integer Nonlinear Optimization},
  url = {https://github.com/minlp-toolbox/CAMINO},
  version = {0.1.1},
  year = {2024}
}

Contributing

Contributions and feedback are welcomed via GitHub PR and issues!

License

This software is under GPL-3.0 license, please check LICENSE for more details.

About

Python-CasADi-based package containing several algorithms for solving mixed-integer nonlinear programs (MINLPs)

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages