## 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:

- cutting-plane method
- branch and bound
- branch and cut
- branch and price
- if the problem has some extra structure, it may be possible to apply delayed column generation.

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

## Solvers and scripting (programming) languages

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.