User:Bmears11/mysandbox/Integer Linear Programming

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming when some but not all the variables are restricted to be integers.

Integer programming is NP-hard. A special case, 0-1 integer linear programming, in which unknowns are binary, is one of Karp's 21 NP-complete problems. However, integer programs with a constant number of variables may be solved in linear time as an LP-type problem.

Standard Form for ILPs

An integer linear program in standard form is expressed as:

${\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} {\text{integer}},\end{aligned}}$

where the entries of c, b and A are integer. Note that similar to linear programs, ILPs can be converted from canonical form (where the constraints are specified as inequalities) to standard form by introducing slack variables.

Example Problems that can be Formulated as ILPs

A large number of problems can be formulated as ILPs. These include

• Travelling Salesman
• Vertex Cover
• Covering problems
• Boolean satisfiability

Note that since the decision version of integer linear programming is in NP (solutions can be verified in polynomial time) and there are NP-complete problems that can be polynomial reduced to ILPs, the decision version of integer linear programming is NP-complete.

Algorithms

The naive way to solve an ILP is to simply remove the constraint that x is integral, solve the corresponding LP (called the LP relaxation of the ILP, and then round the entries of the solution to the LP relaxation. But, not only may this solution not be optimal, it may not even be feasible.

Exact Algorithms

• Branch and Cut

Local Search Algorithms

Since integer linear programming is NP-complete, many problem instances are intractable and so local search methods must be used instead. For example, tabu search can be used to search for solutions to ILPs. To use tabu search to solve ILPs, moves can be defined as incrementing or decrementing an integer constrained variable of a feasible solution, while keeping all other integer-constrained variables constant. The unrestricted variables are then solved for. Short term memory can consist of previous tried solutions while medium term memory can consist of values for the integer constrained variables that have resulted in high objective values (assuming the ILP is a maximization problem). Finally, long term meory can guide the search towards integer values that have not previously been tried.

Other local search algorithms that can applied to ILPs include

• Hill climbing
• Simulated annealing
• Reactive search optimization