Integer unknowns

If the unknown variables are all required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) NP-hard. 0-1 integer programming or binary integer programming (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version was one of Karp’s 21 NP-complete problems.

If only some of the unknown variables are required to be integers, then the problem is called a mixed integer programming (MIP) problem. These are generally also NP-hard.

There are however some important subclasses of IP and MIP problems that are efficiently solvable, most notably problems where the constraint matrix is totally unimodular and the right-hand sides of the constraints are integers.

Advanced algorithms for solving integer linear programs include:

Such integer-programming algorithms are discussed by Padberg and in Beasley.

Solvers and scripting (programming) languages

Free, opensource:

Name License Brief info
LP_Solve LGPL User-friendly linear and integer programming solver. Also provides DLL for program integration.
Cassowary constraint solver LGPL an incremental constraint solving toolkit that efficiently solves systems of linear equalities and inequalities.
Coopr BSD Python packages for modeling and solving optimization problems
CVXOPT GPL general purpose convex optimization solver written in Python, with a C API, and calls external routines (e.g. BLAS, LAPACK, FFTW) for numerical computations. Has its own solvers, but can also call glpk or MOSEK[10] if installed
glpk GPL GNU Linear Programming Kit, a free LP/MILP solver. Uses GNU MathProg modelling language.
OpenOpt BSD Universal cross-platform numerical optimization framework; see its LP page and other problems involved
pulp-or BSD Python module for modeling and solving linear programming problems
Pyomo BSD Python module for formulating linear programming problems with abstract models
Qoca GPL a library for incrementally solving systems of linear equations with various goal functions
CLP CPL an LP solver from COIN-OR project
R-Project GPL a programming language and software environment for statistical computing and graphics
CVX GPL MATLAB based modeling system for convex optimization, including linear programs; calls either SDPT3 or SeDuMi as a solver
CVXMOD GPL Python based modeling system, similar to CVX. It calls CVXOPT as its solver. It is still in in alpha release, as of 2009
SDPT3 GPL MATLAB based convex optimization solver
SeDuMi GPL MATLAB based convex optimization solver

MINTO| here [11] Mixed Integer Optimizer (an integer programming solver which uses branch and bound algorithm) has publicly available source code but not open source.