| 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) |
 | lp_solve | C, procedural interface, Matlab interface, Java source of version 2.0, AMPL interface | | Pascal-MILP-solver | Borland-Pascal sources, DOS/OS2 binaries | | BonsaiG | C, B&B, dynamic LP, partial arc consistency algorithm, binaries( HP-UX, Linux, Solaris) | | MOMIP | no_s, Win95 binary, other binaries( HPUX, Linux, Solaris, SGI, ALPHA) | | MINTO | B&B, primal heuristics, allows to use problem specific knowledge, needs CPLEX or OSL (Solaris version) | | GLPK | GNU LP library, B&B, dual/revised simplex, interior point, Concorde interface, C | | SBB | Simple branch&cut solver, part of COIN-OR (C++) | | MATLOG | (MATLAB) The milp.m solver (needs lp.m from Matlab optimization toolbox) |
| Mixed Integer Quadratic Programming (MIQP) |
| 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) | | Max-AO | solves SDP relaxations of maximum stable set and maximum clique problems, graph input (C) | | SDP-LR | solves SDP relaxations of the maximum cut, minimum bisection, and Lovasz theta problems, graph input (C) |
| Mixed Integer Nonlinear Programming (MINLP) |
| MINLP_BB | branch&bound and QP/SQP, nominal fee, contact S. Leyffer | | BARON | binaries for HP, IBM, Sun, modeling language, websubmission | | BNB | B&B, Matlab, needs optimization toolbox | | FMINCONSET | B&B, variables may be restricted to discrete sets, Matlab, needs optimization toolbox | | mittlp | C, requires CPLEX, extended cutting plane method | | AlphaEcp | WinNt/95 binary, requires CPLEX and f90 |
| Pure integer programming |
| 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 |
| Concorde | The ultimate Traveling Salesman code, requires CPLEX (C) | | LK | Chained Lin-Kernighan heuristic for TSP, Solaris(Intel,Sparc), DEC-Alpha binaries, for very large instances | | LK | David Neto's LK implementation, CWEB source, LGLP, for very large instances | | LKH | An effective implementation of the Lin-Kernighan heuristic, symmetric and unsymmetric cases, C | | TSPSOFT | More links to software for TSP and its variations | | Blossom IV | Minimum weighted perfect matching solver (C); needs Concorde | | SYMPHONY | ILP, MILP, branch&cut library; also PVM, OpenMP parallel; TSP/VRP applications | | SAL | wide selection of basic optimization and OR algorithms, in f77, C, Basic, Pascal, Java, or as DOS/Win binaries | | STONY BROOK | The Stony Brook Algorithm Repository mainly for combinatorial problems | | ECLiPSe | extensive Constraint Logic Programming System, binaries, interfaces to CPLEX and XPRESS-MP | | LOLA | a package for planar location problems (solves discrete and continuous cases) | | Lin Assign | several codes to solve the linear assignment problem, dense&sparse | | SKAP | f77 code for the k-cardinality assignment problem | | QAPP | an exact (parallel) algorithm for the quadratic assignment problem | | QAP | three heuristic algorithms for the quadratic assignment problem | | QUALEX | fast heuristic max-weight clique/independent set solver | | Knapsack | problem generators and solvers, bin-packing, container-loading | | TSpack | C-code for d-dimensional bin packing | | MATLOG | Facilities Planning and Logistics Matlab Toolbox | | JOBSHOP | a package to solve jobshop scheduling problems | | AKRAEMER_MPM | another package for jobshop scheduling with multiple machines | | SAT solvers | links to stochastic and systematic search algorithms for satisfiability problems | | SAT Live! | up-to-date links for the satisfiability problem | | 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; needs CFSQP |
| For more information |
|
