DISCRETE -- Optimization with discrete variables

Algorithms for mixed integer problems can be used for continuous and all-integer problems, too.




Mixed Integer Linear Programming (MILP)

SCIP Framework for Constraint Integer Programming, links to CPLEX, SOPLEX, or CLP as LP solver (C)
lp_solve C, procedural interface. Java wrapper
Pascal-MILP-solver Borland-Pascal sources, DOS/OS2 binaries
BonsaiG C, B&B, dynamic LP, partial arc consistency algorithm, binaries( Linux, Solaris)
MOMIP Win95 binary, other binaries ( HPUX, Linux, Solaris, SGI, ALPHA )
PICO (part of ACRO) B&C, using CPLEX, GLPK, or SOPLEX; AMPL interface
GLPK GNU LP library, B&B, dual/revised simplex, interior point, C, Win32-version, Matlab interface, Java interface
CBC Simple branch&cut solver, part of COIN-OR (C++)
COLIOP IDE to solve LP and MILP; uses GLPK as solver; uses modeling language CMPL (C++)
SYMPHONY callable library for solving mixed-integer linear programs, uses Clp as default LP solver (C)
MATLOG (MATLAB) The milp.m solver (needs lp.m from Matlab optimization toolbox)


Mixed Integer Quadratic Programming (MIQP)

MIQPBB branch&bound code
YALMIP Matlab toolbox for rapid prototyping of optimization problems, supports many solvers; B&B for mixed integer problems
MIQP 0-1 only, needs LP/QP solver, e.g. linprog/quadprog (Matlab)


SDP solvers for discrete optimization

COPL_SDP solves various cut problems, uses dual scaling method(C)
COPL_DSDP mixed integer linear semidefinite problems, enhanced COPL_SDP, MPS-like input (C)
YALMIP Matlab toolbox for rapid prototyping of optimization problems, supports 20 solvers; B&B for mixed integer problems
Max-AO solves SDP relaxations of maximum stable set and maximum clique problems, graph input (C)
SDPLR solves SDP relaxations of the maximum cut, minimum bisection, and Lovasz theta problems, graph input (C)


Mixed Integer Nonlinear Programming (MINLP)

BonMin hybrid code from COIN-OR
MINLP_BB branch&bound and QP/SQP
LaGO B&C, Linux binary, binary variables only, GAMS interface
BARON Branch And Reduce Optimization Navigator (avail. from AIMMS, GAMS)
BNB B&B, Matlab, needs optimization toolbox
FMINCONSET B&B, variables may be restricted to discrete sets, Matlab, needs optimization toolbox
AlphaEcp WinNt/95 binary, requires CPLEX and f90
LogMIP Logical Mixed-Integer Programming, general disjunctive programming (needs GAMS)
MINLP solvers Links to more solvers


Pure integer programming

LocalSolver G Local search heuristic for nonlinear 0-1 problems, free for academic use (C++, C#, Java, .NET)
OPBDP
binaries
0-1 variables, objective and constraints polynomial (C++) A Davis-Putnam Based Enumeration Algorithm for Linear Pseudo-Boolean Optimization
CSPLIB/CPlan C-library for binary constraint satisfaction problems, application to planning problems
CirCut GPL-licensed f90 code to approximately solve certain binary quadratic problems such as Max-Cut, Max-Bisection etc.


A list of problem specific solvers

Torsche Matlab scheduling toolbox
TSP software Commented list of exact and heuristic traveling salesman software
Concorde The ultimate Traveling Salesman code, includes LK, source in (C), Win/Unix executables
LKH An effective implementation of the Lin-Kernighan heuristic, symmetric and unsymmetric cases, C
TSPTW C++ code using ILOG Solver&Scheduler for TSP with time windows
Blossom IV Minimum weighted perfect matching solver (C); needs Concorde
SYMPHONY ILP, MILP, branch&cut library; also PVM, OpenMP parallel; TSP/VRP applications
Assignment Problems links in book by Burkard et al
STONY BROOK The Stony Brook Algorithm Repository mainly for combinatorial problems
LOLOLA a package for planar location and layout problems (solves discrete and continuous cases)
Hungarian method basic f77 code to solve the linear assignment problem
SKAP f77 code for the k-cardinality assignment problem
QAP three heuristic algorithms for the quadratic assignment problem
LEMON Library of Efficient Models and Optimization in Networks (C++)
Cliquer exact B&B code to solve various clique problems in weighted graphs (C, GPL)
QUALEX fast heuristic max-weight clique/independent set solver
Knapsack problem generators and solvers, bin-packing, container-loading
TOMS 864 Three-dimensional bin-packing algorithms
TSpack C-code for d-dimensional bin packing
MATLOG Facilities Planning and Logistics Matlab Toolbox
JOBSHOP a package to solve jobshop scheduling problems
SAT Live! up-to-date links for the satisfiability problem
WALKSAT Stochastic Local Search for Satisfiability, source, Linux binaries (C)
BG-DYN-WALKSAT Backbone Guided WalkSAT for SAT and Max-SAT with Dynamic Noise Ratio
GRASP the grasp algorithm for QAP, MAX-SAT and other problems
MAXSAT Borchers' exact algorithm and testproblems for (weighted) MAX-SAT
GEOSTEINER package to compute optimal Steiner and minimal spanning trees
BIOGEME package for discrete choice (GEV) models


For more information

ZIB Optimization for some discrete optimization problems: software and testcases
Operations Research and Related Sites mainly a list of useful URL's maintained by John Mitchell