Linear programming

In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear.

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 the worst case undecidable, and in many practical situations (those with bounded variables) NP-hard. 0-1 integer programming is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This method is also classified as NP-hard, and in fact the decision version was one of Karp's 21 NP-complete problems.

Related Topics:
NP-hard - 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 integer.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Advanced algorithms for solving integer linear programs include:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• 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.