HOME

TheInfoList



OR:

An integer programming problem is a
mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
or feasibility program in which some or all of the variables are restricted to be
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
s. In many settings the term refers to integer
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
(ILP), in which the objective function and the constraints (other than the integer constraints) are
linear Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
. Integer programming is
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
. 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 In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the b ...
. If some decision variables are not discrete, the problem is known as a mixed-integer programming problem.


Canonical and standard form for ILPs

In integer linear programming, the ''canonical form'' is distinct from the ''standard form''. An integer linear program in canonical form is expressed thus (note that it is the \mathbf vector which is to be decided): : \begin & \text && \mathbf^\mathrm \mathbf\\ & \text && A \mathbf \le \mathbf, \\ & && \mathbf \ge \mathbf, \\ & \text && \mathbf \in \mathbb^n, \end and an ILP in standard form is expressed as : \begin & \text && \mathbf^\mathrm \mathbf\\ & \text && A \mathbf + \mathbf = \mathbf, \\ & && \mathbf \ge \mathbf, \\ & && \mathbf \ge \mathbf, \\ & \text && \mathbf \in \mathbb^n, \end where \mathbf\in \mathbb^n, \mathbf \in \mathbb^m are vectors and A \in \mathbb^ is a matrix. As with linear programs, ILPs not in standard form can be converted to standard form by eliminating inequalities, introducing slack variables (\mathbf) and replacing variables that are not sign-constrained with the difference of two sign-constrained variables


Example

The plot on the right shows the following problem. : \begin \max & \text y \\ -x +y & \leq 1 \\ 3x +2y & \leq 12 \\ 2x +3y & \leq 12 \\ x,y & \ge 0 \\ x,y & \in \mathbb \end The feasible integer points are shown in red, and the red dashed lines indicate their convex hull, which is the smallest convex polyhedron that contains all of these points. 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. The optimal solutions of the integer problem are the points (1,2) and (2,2) which both have an objective value of 2. The unique optimum of the relaxation is (1.8,2.8) with objective value of 2.8. If the solution of the relaxation is rounded to the nearest integers, it is not feasible for the ILP.


Proof of NP-hardness

The following is a reduction from minimum
vertex cover In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimi ...
to integer programming that will serve as the proof of NP-hardness. Let G = (V,E) be an undirected graph. Define a linear program as follows: : \begin \min \sum_ y_v \\ y_v + y_u & \ge 1 && \forall uv \in E\\ y_v & \ge 0 && \forall v \in V\\ y_v & \in \mathbb && \forall v \in V \end Given that the constraints limit y_v to either 0 or 1, any feasible solution to the integer program is a subset of vertices. The first constraint implies that at least one end point of every edge is included in this subset. Therefore, the solution describes a vertex cover. Additionally given some vertex cover C, y_v can be set to 1 for any v\in C and to 0 for any v\not\in C thus giving us a feasible solution to the integer program. Thus we can conclude that if we minimize the sum of y_v we have also found the minimum vertex cover.


Variants

Mixed-integer linear programming (MILP) involves problems in which only some of the variables, x_i, are constrained to be integers, while other variables are allowed to be non-integers. Zero-one linear programming (or binary integer programming) involves problems in which the variables are restricted to be either 0 or 1. Any bounded integer variable can be expressed as a combination of binary variables. For example, given an integer variable, 0\le x\le U, the variable can be expressed using \lfloor \log_2U\rfloor+1 binary variables: : x = x_1+2x_2+4x_3+\cdots+2^x_.


Applications

There are two main reasons for using integer variables when modeling problems as a linear program: #The integer variables represent quantities that can only be integer. For example, it is not possible to build 3.7 cars. #The integer variables represent decisions (e.g. whether to include an edge in a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...
) and so should only take on the value 0 or 1. 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.


Production planning

Mixed-integer programming has many applications in industrial productions, including job-shop modelling. One important example happens in agricultural
production planning Production planning is the planning of production and manufacturing modules in a company or industry. It utilizes the resource allocation of activities of employees, materials and production capacity, in order to serve different customers.Farg ...
involves determining production yield for several crops that can share resources (e.g. Land, labor, capital, seeds, fertilizer, etc.). A possible objective is to maximize the total production, without exceeding the available resources. In some cases, this can be expressed in terms of a linear program, but the variables must be constrained to be integer.


Scheduling

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. Here binary decision variables indicate whether a bus or subway is assigned to a route and whether a driver is assigned to a particular train or subway. The zero-one programming technique has been successfully applied to solve a project selection problem in which projects are mutually exclusive and/or technologically interdependent. It is used in a special case of integer programming, in which all the decision variables are integers. It can assume the values either as zero or one.


Territorial partitioning

Territorial partitioning or districting problem consists in partitioning a geographical region into districts in order to plan some operations while considering different criteria or constraints. Some requirements for this problem are: contiguity, compactness, balance or equity, respect of natural boundaries, and socio-economic homogeneity. Some applications for this type of problem include: political districting, school districting, health services districting and waste management districting.


Telecommunications networks

The goal of these problems is to design a network of lines to install so that a predefined set of communication requirements are met and the total cost of the network is minimal. This requires optimizing both the topology of the network along with the setting the capacities of the various lines. In many cases, the capacities are constrained to be integer quantities. Usually there are, depending on the technology used, additional restrictions that can be modeled as linear inequalities with integer or binary variables.


Cellular networks

The task of frequency planning in
GSM The Global System for Mobile Communications (GSM) is a standard developed by the European Telecommunications Standards Institute (ETSI) to describe the protocols for second-generation ( 2G) digital cellular networks used by mobile devices such as ...
mobile networks involves distributing available frequencies across the antennas so that users can be served and interference is minimized between the antennas. This problem can be formulated as an integer linear program in which binary variables indicate whether a frequency is assigned to an antenna.


Other applications

* Cash flow matching * Energy system optimization * UAV guidance


Algorithms

The naive way to solve an ILP is to simply remove the constraint that x is integer, 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; that is, it may violate some constraint.


Using total unimodularity

While in general the solution to LP relaxation will not be guaranteed to be integral, if the ILP has the form \max\mathbf^\mathrm \mathbf such that A\mathbf = \mathbf where A and \mathbf have all integer entries and A is totally unimodular, then every basic feasible solution is integral. Consequently, the solution returned by the
simplex algorithm In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are n ...
is guaranteed to be integral. To show that every basic feasible solution is integral, let \mathbf be an arbitrary basic feasible solution . Since \mathbf is feasible, we know that A\mathbf=\mathbf. Let \mathbf_0= _,x_,\cdots,x_/math> be the elements corresponding to the basis columns for the basic solution \mathbf. By definition of a basis, there is some square submatrix B of A with linearly independent columns such that B\mathbf_0=\mathbf. 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)=\pm1. Also, since B is nonsingular, it is invertible and therefore \mathbf_0=B^\mathbf. By definition, B^=\frac=\pm B^\mathrm. Here B^\mathrm denotes the adjugate of B and is integral because B is integral. Therefore, : \begin &\Rightarrow B^=\pm B^\mathrm \text \\ &\Rightarrow \mathbf_0=B^b \text \\ &\Rightarrow \text \end 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 Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch ...
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.


Exact algorithms for a small number of variables

Suppose A is an ''m''-by-''n'' integer matrix and \mathbf is an ''m''-by-1 integer vector. We focus on the feasibility problem, which is to decide whether there exists an ''n''-by-1 vector \mathbf satisfying A \mathbf \le \mathbf . Let ''V'' be the maximum absolute value of the coefficients in A and \mathbf. 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. The case ''n''=2 was solved in 1981 by
Herbert Scarf Herbert Eli "Herb" Scarf (July 25, 1930 – November 15, 2015) was an American mathematical economist and Sterling Professor of Economics at Yale University. Education and career Scarf was born in Philadelphia, the son of Jewish emigrants fro ...
. The general case was solved in 1983 by
Hendrik Lenstra Hendrik Willem Lenstra Jr. (born 16 April 1949, Zaandam) is a Dutch mathematician. Biography Lenstra received his doctorate from the University of Amsterdam in 1977 and became a professor there in 1978. In 1987 he was appointed to the faculty ...
, combining ideas by
László Lovász László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He wa ...
and
Peter van Emde Boas Peter van Emde Boas (born 3 April 1945, Amsterdam) is a Dutch computer scientist and professor at the University of Amsterdam. He gained his doctorate in 1974 under Adriaan van Wijngaarden. The Van Emde Boas tree A van Emde Boas tree (), also ...
. In the special case of 0-1 ILP, Lenstra's algorithm is equivalent to complete enumeration: the number of all possible solutions is fixed (2''n''), 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. Here, Lenstra's algorithm uses ideas from
Geometry of numbers Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice in \mathbb R^n, and the study of these lattices provides fundamental informati ...
. It transforms the original problem into an equivalent one with the following property: either the existence of a solution \mathbf is obvious, or the value of x_n (the ''n''-th variable) belongs to an interval whose length is bounded by a function of ''n''. In the latter case, the problem is reduced to a bounded number of lower-dimensional problems. The run-time complexity of the algorithm has been improved in several steps: * The original algorithm of Lenstra had run-time 2^\cdot (m\cdot \log V)^. * Kannan presented an improved algorithm with run-time n^\cdot (m\cdot \log V)^. * Frank and Tardos presented a different improved algorithm. The improved runtime is n^ \cdot \ell , where \ell is the number of input bits, which is in \text(m, \log).


Heuristic methods

Since integer linear programming is
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard p ...
, many problem instances are intractable and so heuristic methods must be used instead. For example,
tabu search Tabu search is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986 and formalized in 1989. Local (neighborhood) searches take a potential solution to a prob ...
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 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. Other heuristic methods that can be applied to ILPs include *
Hill climbing numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution ...
*
Simulated annealing Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. It ...
*Reactive search optimization *
Ant colony optimization In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for multi ...
* Hopfield neural networks There are also a variety of other problem-specific heuristics, such as the k-opt heuristic for the traveling salesman problem. A disadvantage of heuristic methods is that if they fail to find a solution, it cannot be determined whether it is because there is no feasible solution or whether the algorithm simply was unable to find one. Further, it is usually impossible to quantify how close to optimal a solution returned by these methods are.


Sparse integer programming

It is often the case that the matrix A which defines the integer program is ''sparse''. In particular, this occurs when the matrix has a block structure, which is the case in many applications. The sparsity of the matrix can be measured as follows. The ''graph'' of A has vertices corresponding to columns of A, and two columns form an edge if A has a row where both columns have nonzero entries. Equivalently, the vertices correspond to variables, and two variables form an edge if they share an inequality. The ''sparsity measure'' d of A is the minimum between the tree-depth of the graph of A and the tree-depth of the graph of the transpose of A. Let a be the ''numeric measure'' of A defined as the maximum absolute value of any entry of A. Let n be the number of variables of the integer program. Then it was shown in 2018 that integer programming can be solved in
strongly polynomial In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
and fixed-parameter tractable time parameterized by a and d. That is, for some computable function f and some constant k, integer programming can be solved in time f(a,d)n^k. In particular, the time is independent of the right-hand side b and objective function c. Moreover, in contrast to the classical result of Lenstra, where the number n of variables is a parameter, here the number n of variables is a variable part of the input.


See also

*
Constrained least squares In constrained least squares one solves a linear least squares problem with an additional constraint on the solution. I.e., the unconstrained equation \mathbf \boldsymbol = \mathbf must be fit as closely as possible (in the least squares sense ...


References


Further reading

* * * * * * * * *


External links


A Tutorial on Integer Programming
* Conferenc
Integer Programming and Combinatorial Optimization, IPCO

The Aussois Combinatorial Optimization Workshop
{{Optimization algorithms, combinatorial, state=expanded Combinatorial optimization