Optimization software

This is a personal collection of pointers to tools for solving optimization problems.

Mixed integer linear programming.

Many solvers in this list can solve more general problems than mixed interger linear programming problems. For a broader collection see Hans D. Mittelmann’s decision tree guide, his benchmarks and his talks. A summary and visualization of the benchmarks is maintained by Matthias Miltenberger.

The MIPfeas Benchmark by Michael Bussieck and Steve Dirkse is focused on time to feasible solutions in MIP.

Tools for Solving

  • Gurobi: commercial. State-of-the-art in terms of performance. API in several languages and excellent documentation.

  • Cardinal Optimizer (COPT) by Shanshu. Free for public testing and evaluation for 180 days. For academic users for 365 days. There are interfaces from Python, PuLP, Pyomo. Highly performing. Other highly competitive solvers from the Chinese industry: MindOpt/Alibaba and OptVerse/Huawei.

  • Xpress commercial.

  • CPLEX commercial. Now owned by IBM previously by ILOG.

  • HiGHS Open Source. Free also for commercial purposes. Highly performing, C++, scarce documentation, used by Python in scipy. Under active development. [example on knapsack]

  • NVIDIA cuOpt and its github repository. GPU-accelerated optimization engine. Under active development. Core engine is written in C++ and wrapped with a C API, Python API and Server API.

  • SCIP: Open Source. Free also for commercial purposes. It is the most powerful research code. There is also a concurrent version. SCIP Parameters

  • NEOS server: upload a problem in mps format and solve remotely.

  • ortools. It uses Glop or SCIP for LP and MILP respectively, and a set of own techniques for constraint programming.

  • CBC from the COIN-OR repository. Open source. Not further developed.

  • GLPK limited performance above all for integer linear programs. Not further developed and deprecated because of errors.

  • lp_solve aka Clp: open source solver only for LP models. Not further developed.

  • https://github.com/ajenter/mipcl mysterious well performing solver in an one man project, intended to be open source (but the sources were never released). It is not supported by the modeling tools below but it has its own modeling enviroment in Python. Project not updated since 2019. The original web page by the author seems not acessible anymore at time of writing.

Tools for Modeling

  • Pyomo offers interfaces to several solvers but my tests showed inefficiencies. It needs more exploration.

  • Python-MIP see also package website integrates with CBC and Gurobi (scip claimed to come). It provides access to advanced solver features like cut generation, lazy constraints, MIPstarts and solution Pools. It claims to be more efficient than those below while having similar syntax to PuLP.

  • pyscipopt SCIP Python API. It has a tutorial.

  • gurobipy the Python API for Gurobi. Commercial but excellent documentation and clean syntax.

  • CyLP is a Python interface to COIN-OR’s CBC. It allows to alter the solution process of the solvers from within Python: you can define cut generators, branch-and-bound strategies, and primal/dual Simplex pivot rules completely in Python.

  • PuLP with interfaces to most of the high performing solvers listed above. Documentation. Article at Towards Data Science.

  • scipy for problems already in matrix form. See example on knapsack.

  • ortools for modeling in LP, MILP and CP. It includes interfaces to C++, Java and .Net.

  • CPMpy It handles Constraint Programming problems but beside ortools, sat, z3, it offers an interface also to gurobi.

  • JuliaOpt: in the Julia langage separates modeling from solving. Using the same modeling syntax it is possible to solve the problem with different free and commercial solvers.

Spreadsheet approach

Both Google Sheets and Microsoft Excel make it possible to solve mathematical programing problems with some add-ins.

Excel:

GoogleSheets:

More general problems

Hierarchy of convex optimization problems from least to most general: LP: linear program, QP: quadratic program, SOCP second-order cone program, SDP: semidefinite program, CP: cone program.

  • Gurobi and Cplex solve also convex programming problems

  • Mosek commercial solver with academic license to solve linear and non linear convex optimization problems like LP, QP, SOCP and SDP problems, and mixed integer programming problems.

  • pyomo can solve non linear problems with Ipopt.

  • Ipopt interiori point optimizer for linear or nonlinear and convex or non-convex objectives and constraints (but should be twice continuously differentiable).

  • OSQP highly performing solver for convex optimization problems. Free Apache 2.0.

  • CVXpy python modeling for convex optimization problems. Reading material