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 (ILP).

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.

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} =\mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} {\text{ integer}},\end{aligned}}$

where the entries of $\mathbf {c} ,\mathbf {b}$ and $A$ are integer. Note that similar to linear programs, ILPs not in standard form can be converted to standard form by eliminating inequalities by introducing slack variables and replacing variables that are not sign-constrained with the difference of two sign-constrained variables

Mixed Integer and Zero-one Linear Programs

Mixed integer linear programming (MILP) involve problems in which only some of the variables, $x_{i}$, are constrained to be integers. Zero-one linear programming involve problems in which the variables are restricted to be either 0 or 1. Note that any bounded integer variable can be expressed as a combination of binary variables. For example, given an integer variable, $0\leq x\leq U$, the variable can be expressed using $\lfloor \log _{2}U\rfloor +1$ binary variables:

$x=x_{1}+2x_{2}+4x_{3}+\ldots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.$

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.

Using total unimodularity

While in general the solution to LP relaxation will not be guaranteed to be optimal, if the ILP has the form $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ such that $A\mathbf {x} =\mathbf {b}$ where $A,\mathbf {b} ,$ and $\mathbf {c}$ have all integer entries and $A$ is totally unimodular, then every basic feasible solution is integral. Consequently, the solution returned by the simplex algorithm is guaranteed to be integer. To show that every basic feasible solution is integral, let $\mathbf {x}$ be an arbitrary basic feasible solution . Since $\mathbf {x}$ is feasible, we know that $A\mathbf {x} =\mathbf {b}$. Let $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ be the elements corresponding to the basis columns for the basic solution $\mathbf {x}$. By definition of a basis, there is some square submatrix $B$ of $A$ with linearly independent columns such that $B\mathbf {x} _{0}=\mathbf {b}$.

Since the columns of $B$ are linearly independent and $B$ is square, $B$ is nonsingular, and therefore by assumption, $B$ is unimodular and so $\det(B)=\pm 1$. Also, since $B$ is nonsingular, it is invertible and therefore $\mathbf {x} _{0}=B^{-1}\mathbf {b}$. By definition, $B^{-1}={\frac {B^{adj}}{\det(B)}}=\pm B^{adj}$. Note that $B^{adj}$ denotes the adjugate of $B$ and is integral because $B$ is integer. Therefore,

${\begin{aligned}&\Rightarrow B^{-1}=\pm B^{adj}{\text{ is integral.}}\\&\Rightarrow x_{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}$

Thus, if the matrix $A$ of an ILP is totally unimodular, rather than use an ILP algorithm, the simplex method can be used to solve the LP relaxation and the solution will be integer.

Exact Algorithms

When the matrix $A$ is not totally unimodular, there are a variety of algorithms that can be used to solve integer linear programs exactly. One class of algorithms are cutting plane methods which work by solving the LP relaxation and then adding linear constraints that drive the solution towards being integer without excluding any integer feasible points. Another class of algorithms are variants of the branch and bound method. For example, the branch and cut method that combines both branch and bound and cutting plane methods. Branch and bound algorithms have a number of advantages over algorithms that only use cutting planes. One advantage is that the algorithms can be terminated early and as long as at least one integral solution has been found, a feasible, although not necessarily optimal , solution can be returned. Further, the solutions of the LP relaxations can be used to provide a worst-case estimate of how far from optimality the returned solution is. Finally, branch and bound methods can be used to return multiple optimal solutions.

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