Integer programming

From Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/Integer_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), in which the objective function and the constraints (other than the integer constraints) are linear.

Integer programming is NP-complete. 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.

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 ${\displaystyle \mathbf{x}}$ vector which is to be decided):

${\displaystyle \begin{array}{rlrl}& \text{maximize}& & {\mathbf{c}}^{\mathrm{T}}\mathbf{x}\\ & \text{subject to}& & A\mathbf{x}\le \mathbf{b},\\ & & & \mathbf{x}\ge \mathbf{0},\\ & \text{and}& & \mathbf{x}\in {\mathbb{Z}}^n,\end{array}}$

and an ILP in standard form is expressed as

${\displaystyle \begin{array}{rlrl}& \text{maximize}& & {\mathbf{c}}^{\mathrm{T}}\mathbf{x}\\ & \text{subject to}& & A\mathbf{x}+\mathbf{s}=\mathbf{b},\\ & & & \mathbf{s}\ge \mathbf{0},\\ & & & \mathbf{x}\ge \mathbf{0},\\ & \text{and}& & \mathbf{x}\in {\mathbb{Z}}^n,\end{array}}$

where ${\displaystyle \mathbf{c}\in {\mathbb{R}}^n,\mathbf{b}\in {\mathbb{R}}^m}$ are vectors and ${\displaystyle A\in {\mathbb{R}}^{m\times n}}$ is a matrix. As with linear programs, ILPs not in standard form can be converted to standard form by eliminating inequalities, introducing slack variables (${\displaystyle \mathbf{s}}$) and replacing variables that are not sign-constrained with the difference of two sign-constrained variables

Example

IP polytope with LP relaxation

The plot above shows the following problem.

${\displaystyle \begin{array}{rl}max& y\\ -x+y& \le 1\\ 3x+2y& \le 12\\ 2x+3y& \le 12\\ x,y& \ge 0\\ x,y& \in \mathbb{Z}\end{array}}$

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 ${\displaystyle (1,2)}$ and ${\displaystyle (2,2)}$ which both have an objective value of 2. The unique optimum of the relaxation is ${\displaystyle (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 to integer programming that will serve as the proof of NP-hardness.

Let ${\displaystyle G=(V,E)}$ be an undirected graph. Define a linear program as follows:

${\displaystyle \begin{array}{r}min\sum _{v\in V}{y}_v\\ y_v+y_u& \ge 1& & \mathrm{\forall }uv\in E\\ y_v& \ge 0& & \mathrm{\forall }v\in V\\ y_v& \in \mathbb{Z}& & \mathrm{\forall }v\in V\end{array}}$

Given that the constraints limit ${\displaystyle 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, ${\displaystyle y_v}$ can be set to 1 for any ${\displaystyle v\in C}$ and to 0 for any ${\displaystyle v\notin C}$ thus giving us a feasible solution to the integer program. Thus we can conclude that if we minimize the sum of ${\displaystyle 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, ${\displaystyle 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, ${\displaystyle 0\le x\le U}$, the variable can be expressed using ${\displaystyle \lfloor {\log }_{2}U\rfloor +1}$ binary variables:

${\displaystyle x=x_1+2x_2+4x_3+\cdots +2^{\lfloor {\log }_{2}U\rfloor }{x}_{\lfloor {\log }_{2}U\rfloor +1}.}$

Applications

There are two main reasons for using integer variables when modeling problems as a linear program:

1. The integer variables represent quantities that can only be integer. For example, it is not possible to build 3.7 cars.
2. The integer variables represent decisions (e.g. whether to include an edge in a graph) 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 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 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 ${\displaystyle max{\mathbf{c}}^{\mathrm{T}}\mathbf{x}}$ such that ${\displaystyle A\mathbf{x}=\mathbf{b}}$ where ${\displaystyle A}$ and ${\displaystyle \mathbf{b}}$ have all integer entries and ${\displaystyle A}$ is totally unimodular, then every basic feasible solution is integral. Consequently, the solution returned by the simplex algorithm is guaranteed to be integral. To show that every basic feasible solution is integral, let ${\displaystyle \mathbf{x}}$ be an arbitrary basic feasible solution . Since ${\displaystyle \mathbf{x}}$ is feasible, we know that ${\displaystyle A\mathbf{x}=\mathbf{b}}$. Let ${\displaystyle {\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 ${\displaystyle \mathbf{x}}$. By definition of a basis, there is some square submatrix ${\displaystyle B}$ of ${\displaystyle A}$ with linearly independent columns such that ${\displaystyle B{\mathbf{x}}_0=\mathbf{b}}$.

Since the columns of ${\displaystyle B}$ are linearly independent and ${\displaystyle B}$ is square, ${\displaystyle B}$ is nonsingular, and therefore by assumption, ${\displaystyle B}$ is unimodular and so ${\displaystyle det(B)=\pm 1}$. Also, since ${\displaystyle B}$ is nonsingular, it is invertible and therefore ${\displaystyle {\mathbf{x}}_0=B^{-1}\mathbf{b}}$. By definition, ${\displaystyle B^{-1}=\frac{B^{\mathrm{a}\mathrm{d}\mathrm{j}}}{det(B)}=\pm B^{\mathrm{a}\mathrm{d}\mathrm{j}}}$. Here ${\displaystyle B^{\mathrm{a}\mathrm{d}\mathrm{j}}}$ denotes the adjugate of ${\displaystyle B}$ and is integral because ${\displaystyle B}$ is integral. Therefore,

${\displaystyle \begin{array}{rl}& \Rightarrow B^{-1}=\pm B^{\mathrm{a}\mathrm{d}\mathrm{j}}\text{ is integral.}\\ & \Rightarrow x_0=B^{-1}b\text{ is integral.}\\ & \Rightarrow \text{Every basic feasible solution is integral.}\end{array}}$

Thus, if the matrix ${\displaystyle 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 ${\displaystyle 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.

Exact algorithms for a small number of variables

Suppose ${\displaystyle A}$ is an m-by-n integer matrix and ${\displaystyle \mathbf{b}}$ 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 ${\displaystyle \mathbf{x}}$ satisfying ${\displaystyle A\mathbf{x}\le \mathbf{b}}$.

Let V be the maximum absolute value of the coefficients in ${\displaystyle A}$ and ${\displaystyle \mathbf{b}}$. 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.^[11] The general case was solved in 1983 by Hendrik Lenstra, combining ideas by László Lovász and Peter van Emde Boas.^[12]

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ⁿ), 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. It transforms the original problem into an equivalent one with the following property: either the existence of a solution ${\displaystyle \mathbf{x}}$ is obvious, or the value of ${\displaystyle 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 ${\displaystyle 2^{O(n^3)}\cdot (m\cdot \log V{)}^{O(1)}}$.
• Kannan presented an improved algorithm with run-time ${\displaystyle n^{O(n)}\cdot (m\cdot \log V{)}^{O(1)}}$.
• Frank and Tardos presented a different improved algorithm. The improved runtime is ${\displaystyle n^{2.5n}\cdot \ell }$ , where ${\displaystyle \ell }$ is the number of input bits, which is in ${\displaystyle \text{poly}(m,\log V)}$ in which n is varying but m (the number of constraints) is constant.

Heuristic methods

Since integer linear programming is NP-hard, many problem instances are intractable and so heuristic 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 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
• Simulated annealing
• Reactive search optimization
• Ant colony optimization
• 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 ${\displaystyle 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 ${\displaystyle A}$ has vertices corresponding to columns of ${\displaystyle A}$, and two columns form an edge if ${\displaystyle 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 ${\displaystyle d}$ of ${\displaystyle A}$ is the minimum between the tree-depth of the graph of ${\displaystyle A}$ and the tree-depth of the graph of the transpose of ${\displaystyle A}$. Let ${\displaystyle a}$ be the numeric measure of ${\displaystyle A}$ defined as the maximum absolute value of any entry of ${\displaystyle A}$. Let ${\displaystyle 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 and fixed-parameter tractable time parameterized by ${\displaystyle a}$ and ${\displaystyle d}$. That is, for some computable function ${\displaystyle f}$ and some constant ${\displaystyle k}$, integer programming can be solved in time ${\displaystyle f(a,d)n^k}$. In particular, the time is independent of the right-hand side ${\displaystyle b}$ and objective function ${\displaystyle c}$. Moreover, in contrast to the classical result of Lenstra, where the number ${\displaystyle n}$ of variables is a parameter, here the number ${\displaystyle n}$ of variables is a variable part of the input.

Greedy algorithm

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Greedy_algorithm 

 

Greedy algorithms determine the minimum number of coins to give while making change. These are the steps most people would take to emulate a greedy algorithm to represent 36 cents using only coins with values {1, 5, 10, 20}. The coin of the highest value, less than the remaining change owed, is the local optimum. (In general, the change-making problem requires dynamic programming to find an optimal solution; however, most currency systems are special cases where the greedy strategy does find an optimal solution.)

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

For example, a greedy strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find the best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids and give constant-factor approximations to optimization problems with the submodular structure.

Specifics

Greedy algorithms produce good solutions on some mathematical problems, but not on others. Most problems for which they work will have two properties:

Greedy choice property

We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution.

Optimal substructure

"A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems."

Cases of failure

Examples on how a greedy algorithm may fail to achieve the optimal solution.

Starting from A, a greedy algorithm that tries to find the maximum by following the greatest slope will find the local maximum at "m", oblivious to the global maximum at "M".

 

To reach the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step, and will not reach the best solution, which contains 99.

Greedy algorithms fail to produce the optimal solution for many other problems and may even produce the unique worst possible solution. One example is the travelling salesman problem mentioned above: for each number of cities, there is an assignment of distances between the cities for which the nearest-neighbour heuristic produces the unique worst possible tour. For other possible examples, see horizon effect.

Types

Greedy algorithms can be characterized as being 'short sighted', and also as 'non-recoverable'. They are ideal only for problems that have an 'optimal substructure'. Despite this, for many simple problems, the best-suited algorithms are greedy. It is important, however, to note that the greedy algorithm can be used as a selection algorithm to prioritize options within a search, or branch-and-bound algorithm. There are a few variations to the greedy algorithm:

• Pure greedy algorithms
• Orthogonal greedy algorithms
• Relaxed greedy algorithms

Theory

Greedy algorithms have a long history of study in combinatorial optimization and theoretical computer science. Greedy heuristics are known to produce suboptimal results on many problems, and so natural questions are:

• For which problems do greedy algorithms perform optimally?
• For which problems do greedy algorithms guarantee an approximately optimal solution?
• For which problems are the greedy algorithm guaranteed not to produce an optimal solution?

A large body of literature exists answering these questions for general classes of problems, such as matroids, as well as for specific problems, such as set cover.

Matroids

Main article: Matroid

A matroid is a mathematical structure that generalizes the notion of linear independence from vector spaces to arbitrary sets. If an optimization problem has the structure of a matroid, then the appropriate greedy algorithm will solve it optimally.

Submodular functions

Main article: Submodular set function § Optimization problems

A function ${\displaystyle f}$ defined on subsets of a set ${\displaystyle \mathrm{\Omega }}$ is called submodular if for every ${\displaystyle S,T\subseteq \mathrm{\Omega }}$ we have that ${\displaystyle f(S)+f(T)\ge f(S\cup T)+f(S\cap T)}$.

Suppose one wants to find a set ${\displaystyle S}$ which maximizes ${\displaystyle f}$. The greedy algorithm, which builds up a set ${\displaystyle S}$ by incrementally adding the element which increases ${\displaystyle f}$ the most at each step, produces as output a set that is at least ${\displaystyle (1-1/e)\underset{X\subseteq \mathrm{\Omega }}{max}f(X)}$. That is, greedy performs within a constant factor of ${\displaystyle (1-1/e)\approx 0.63}$ as good as the optimal solution.

Similar guarantees are provable when additional constraints, such as cardinality constraints, are imposed on the output, though often slight variations on the greedy algorithm are required. See  for an overview.

Other problems with guarantees

Other problems for which the greedy algorithm gives a strong guarantee, but not an optimal solution, include

• Set cover
• The Steiner tree problem
• Load balancing
• Independent set

Many of these problems have matching lower bounds; i.e., the greedy algorithm does not perform better than the guarantee in the worst case.

Applications

Greedy algorithms typically (but not always) fail to find the globally optimal solution because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early, preventing them from finding the best overall solution later. For example, all known greedy coloring algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.

If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like dynamic programming. Examples of such greedy algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees and the algorithm for finding optimum Huffman trees.

Greedy algorithms appear in the network routing as well. Using greedy routing, a message is forwarded to the neighbouring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in geographic routing used by ad hoc networks. Location may also be an entirely artificial construct as in small world routing and distributed hash table.

Examples

• The activity selection problem is characteristic of this class of problems, where the goal is to pick the maximum number of activities that do not clash with each other.
• In the Macintosh computer game Crystal Quest the objective is to collect crystals, in a fashion similar to the travelling salesman problem. The game has a demo mode, where the game uses a greedy algorithm to go to every crystal. The artificial intelligence does not account for obstacles, so the demo mode often ends quickly.
• The matching pursuit is an example of a greedy algorithm applied on signal approximation.
• A greedy algorithm finds the optimal solution to Malfatti's problem of finding three disjoint circles within a given triangle that maximize the total area of the circles; it is conjectured that the same greedy algorithm is optimal for any number of circles.
• A greedy algorithm is used to construct a Huffman tree during Huffman coding where it finds an optimal solution.
• In decision tree learning, greedy algorithms are commonly used, however they are not guaranteed to find the optimal solution.
  • One popular such algorithm is the ID3 algorithm for decision tree construction.
• Dijkstra's algorithm and the related A* search algorithm are verifiably optimal greedy algorithms for graph search and shortest path finding.
  • A* search is conditionally optimal, requiring an "admissible heuristic" that will not overestimate path costs.
• Kruskal's algorithm and Prim's algorithm are greedy algorithms for constructing minimum spanning trees of a given connected graph. They always find an optimal solution, which may not be unique in general.