Integer programming

In particular, the special case of 0–1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.

An integer linear program in canonical form is expressed thus (note that it is the

The blue lines together with the coordinate axes define the polyhedron of the LP relaxation, which is given by the inequalities without the integrality constraint.

The goal of the optimization is to move the black dashed line as far upward while still touching the polyhedron.

If the solution of the relaxation is rounded to the nearest integers, it is not feasible for the ILP.

The following is a reduction from minimum vertex cover to integer programming that will serve as the proof of NP-hardness.

[4] Mixed-integer linear programming (MILP) involves problems in which only some of the variables,

binary variables: There are two main reasons for using integer variables when modeling problems as a linear program: These considerations occur frequently in practice and so integer linear programming can be used in many applications areas, some of which are briefly described below.

Mixed-integer programming has many applications in industrial productions, including job-shop modelling.

In some cases, this can be expressed in terms of a linear program, but the variables must be constrained to be integer.

These problems involve service and vehicle scheduling in transportation networks.

For example, a problem may involve assigning buses or subways to individual routes so that a timetable can be met, and also to equip them with drivers.

Some requirements for this problem are: contiguity, compactness, balance or equity, respect of natural boundaries, and socio-economic homogeneity.

Usually there are, depending on the technology used, additional restrictions that can be modeled as linear inequalities with integer or binary variables.

[7] This problem can be formulated as an integer linear program in which binary variables indicate whether a frequency is assigned to an antenna.

While in general the solution to LP relaxation will not be guaranteed to be integral, if the ILP has the form

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.

Finally, branch and bound methods can be used to return multiple optimal solutions.

If n (the number of variables) is a fixed constant, then the feasibility problem can be solved in time polynomial in m and log V. This is trivial for the case n=1.

[13] The general case was solved in 1983 by Hendrik Lenstra, combining ideas by László Lovász and Peter van Emde Boas.

[14] Doignon's theorem asserts that an integer program is feasible whenever every subset of

constraints is feasible; a method combining this result with algorithms for LP-type problems can be used to solve integer programs in time that is linear in

[15] In the special case of 0-1 ILP, Lenstra's algorithm is equivalent to complete enumeration: the number of all possible solutions is fixed (2n), and checking the feasibility of each solution can be done in time poly(m, log V).

In the general case, where each variable can be an arbitrary integer, complete enumeration is impossible.

The run-time complexity of the algorithm has been improved in several steps: These algorithms can also be used for mixed integer linear programs (MILP) - programs in which some variables are integer and some variables are real.

[23] Since integer linear programming is NP-hard, many problem instances are intractable and so heuristic methods must be used instead.

Short-term memory can consist of previously 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 memory can guide the search towards integer values that have not previously been tried.

Then it was shown in 2018[25] that integer programming can be solved in strongly polynomial and fixed-parameter tractable time parameterized by