Integer programming

The integer linear programming (also Integer Programming ) is a branch of applied mathematics. As the linear optimization it deals with the optimization of linear objective functions by an amount which is limited by linear equations and inequalities. The difference is that in the integer programming some or all variables can assume only integer values ​​and not any real values ​​as in the linear optimization. The integer optimization can be geometrically as an optimization over a convex polyhedron ( a higher-dimensional polygon ) interpret and is therefore a special case of convex optimization. In contrast to linear programming, however, the underlying polyhedron is usually not known exactly what makes the problem from a complexity theory perspective NP-hard.

Since at least one discrete variable, so is not continuous, is the term commonly used discrete optimization. Another common name is integer (linear) programming (of English. Integer ( linear) programming ), where the term program is to be understood in the sense of planning and not in the sense of a computer program. It was coined back in the 1940s by George Dantzig, before computers were used to solve optimization problems.

Even more than the linear, the integer optimization has evolved since its beginnings in the 1950s to a modeling and optimization tool for many practical problems for which there are no known specific algorithms. Due to significant advances in the development of solution methods in the 1980s and 1990s, the integer optimization today many applications, for example in the production, in the planning of telecommunications and transport networks, and tour assistance.

To solve integer optimization problems there either exact solution methods such as branch- and-bound and cutting plane methods based on the solution of many similar linear programs, and on the other hand, a variety of heuristics. Nevertheless, the solution of integer linear programs in practice is still a difficult task that requires a skillful modeling and algorithms more or less specifically developed or adapted depending on the size and structure of the problem to be solved. This often several solution methods are combined.

• 3.1 Production Planning
• 3.2 Public transport
• 3.3 telecommunications networks
• 3.4 Mobile networks
• 3.5 tour
• 3.6 0/1-Programmierung

• 5.1 Exact and heuristic methods
• 5.2 Dual bounds and optimality proof
• 5.3 Cutting plane method
• 5.4 Branch -and-bound or branch-and -cut
• 5.5 Lagrangian relaxation
• 5.6 heuristics

Problem definition

Mathematical formulation

An integer linear programming ( engl. integer program, IP) has the same shape as a linear program (LP), with the difference that the variables must be integers:

It is a real matrix, and vectors suitable dimension. The condition is component-wise to understand, so as

For all rows of the matrix. Just means the condition that all the entries of the vector must be non-negative. Are the integrality constraints only for a subset of variables, one also speaks of a mixed integer program (English mixed- integer program MIP). The precise integer linear program (german integer linear program ILP ) is commonly used. As in linear programming, there are several equivalent formulations, which can be transformed into each other (see Linear Programming: Problem definition).

Geometric interpretation

The integer optimization can be, as the linear variant, geometric interpretation to a large extent. The amount

Produced by omitting the integrality forms a convex polyhedron in -dimensional space, the restrictive hyperplanes corresponding to the lines of the inequality system. contains, inter alia, all feasible points of the original system, so all integer points that satisfy the conditions, but in contrast to linear optimization, not all points in admissible. The linear program

Is referred to as LP relaxation problem of the integer, and plays an important role in some solution processes ( see below).

How linear programs can be unsolvable or unlimited even integer programs. In all other cases, there is at least one optimal solution if the inequality system has only rational entries. It is in contrast to the real linear optimization possible to construct problems that have no optimal solution, although solutions exist and the objective function is limited. In contrast to LPs the amount of optimal solutions of IPs is not a side face of the polyhedron, so that there can be in addition to exactly one or infinitely many optimal solutions also another finite number ( greater than 1) thereof.

Examples

The picture to the integer linear program

Shown. The permissible integer points are shown in red, and the red dashed lines indicate its convex hull, ie, the smallest polyhedron that contains all these points. About this polyhedron is supposed to be optimized, but it usually is not precisely known. The blue lines together with the coordinate axes define the polyhedra of the LP- relaxation, which is given by the inequality without integrality. The aim of the optimization is to move the black dotted line so far parallel upward ( in the direction of the vector ) that it just touches the respective polyhedron. The optimum solutions of the problem is thus the integral points, and the objective function value. The - in this case unique - optimal solution of the LP relaxation with the objective function value of 2.8 is the blue marked point, which is not an integer, and thus not allowed for the IP.

The following IP is an example of the above-mentioned special case:

The feasible solutions such as make rational approximations for the form dar. Since is irrational and therefore can be approximated arbitrarily closely, there is no optimal solution, even though the objective function by the first condition to the top is limited.

Applications

The integrality extend the modeling capabilities for practical problems with respect to the linear optimization considerably. There are two main reasons for integer variables:

Often both cases occur together. The integer optimization can be used in many practical application fields, of which some are briefly described below.

Production Planning

In production planning, often there is the problem of determining production quantities for multiple products that share common resources (machines, working, storage capacity, ...). The goal is for example to maximize the total contribution margin, without exceeding the available resources. In some cases, this can be expressed using a linear program, but often the variables must for practical reasons be an integer (see above).

Public transport

In the service and vehicle scheduling in public transport it comes, for example as to distribute buses or subways to the individual lines that the schedule can be met and to provide it with drivers. Here binary decision variables play a major role, which express, for example, whether a certain type of bus is running on a line or not, or whether a metro driver is assigned to a specific train or not.

Telecommunications networks

The aim of the capacity and routing planning in national telecommunications networks is on the nodes and lines of a network to install capacity so and to route communication needs in such a way that all requirements are met and the total cost of the network are minimal. The capacity can not be installed in any proportions, but only in certain integer units in the rule. There is usually, depending on the technology used, additional restrictions that can be modeled as linear inequalities with integer or binary variables.

Mobile networks

The task of frequency planning in GSM mobile networks is so to distribute the available frequencies to the antennas that users can be served, and the disturbing interference is minimized between the antennas. This problem can be formulated as an integer linear program, in which, inter alia, binary variables representing whether a frequency of an antenna which is assigned or not.

Tour

The tour, especially the problem of the traveling salesman, is a classic example of integer programming, whose research has contributed much to the development of general solution methods. Clearly it comes to finding a shortest round trip between a given set of cities. This problem can be modeled as an integer linear program with exponentially many inequalities. Various Advanced variants tour dive in practice, for example when drilling on printed circuit boards, or even when planning routes for field staff (eg a technical service company or an insurance company) who want to serve all their customers with the shortest possible distance.

0/1-Programmierung

A particularly important special case of integer programming is the optimization in which the variables can assume non-integer values, but are limited to the values ​​0 or 1. This allows the search for solutions transferred for Boolean functions in the geometry: Finding an assignment of such a function is equivalent to finding 0/1-Punkten cut and the union of high-dimensional polytopes. This method is called disjunctive programming and was developed in the late 1960s by Egon Balas.

History

The start of the integer programming is closely linked with the development of linear programming mid-1940s. In 1947, George Dantzig published several critical works on linear programming and the simplex method, which he. During the following years, along with John von Neumann, and other advanced

As with the advent of computers in the 1950s, the first practical purpose computer programs have been developed for solving linear programs, also moved the solvability of integer optimization problems within reach. Mid-1950s, DR Fulkerson, G. Dantzig, and S. Johnson worked on first cutting planes for the traveling salesman problem ends. Without knowledge of this work and motivated by former colleagues of the U.S. Navy who were interested in integer solutions, Ralph Gomory developed in 1958 during his stay in Princeton, the first general-purpose cutting plane method which ( at least theoretically) permitted the complete solvability of arbitrary integer programs. Even though this was practically implemented only partially, This marked one of the crucial algorithmic progress

Shortly thereafter, in 1960, presented AH country and AG Doig before the branch- and-bound method based on a clever enumeration of the search space. 1965, RJ Dakin to a simply implementable algorithm it. It was later instrumental combined by Egon Balas Branch -and-bound with cutting planes for branch-and -cut, which allowed the solution significantly larger integer linear programs.

In the late 1960s, developed among others Egon Balas, a general method to find linear descriptions that include from the outset only integer vertices. This so-called lift- and-project based on the idea to transfer the optimization in a high-dimensional space and for projecting the solution found in lower dimensions.

In the 1980s, worked Manfred Padberg and others cutting planes for frequently appearing substructures such as backpack problems that can often be used in a more general context. The enormous algorithmic advances in linear programming in the 1990s were also reflected in a significantly improved solubility integer programs, as for example in the use of cutting plane algorithms and branch-and- bound algorithms very many linear programs must be solved. In addition to better modeling and solution techniques for frequently arising sub-problems, such as network flows, were parallel, many heuristics, so approximate methods developed that calculate the most feasible solutions in a short time. It can be, inter alia, also be used as part of a branch and cut method, in order to accelerate it. All of these methods are still the subject of current research.

Complexity and solution methods

In contrast to linear programs that can be optimally solved in polynomial time, for example, interior-point method, finding a provable optimal solution for integer programs is an NP- hard problem. This is also noticeable in practice. While even large linear programs can be largely solved by standard methods today, the solvability of integer programs depends much more on the specific characteristics of each planning problem and the selected modeling. An optimization problem with a hundred integer variable may be unsolvable, while other problems with thousands of integer variables to be solved within a few seconds from a practical perspective. There are even in integer programming standard methods by which by large algorithmic progress within the last ten years, many practical planning problems can be solved as an IP now, but just in solving large integer programs in a reasonable time often requires a skillful modeling and a combination of several solution method with problem-specific adaptations.

Exact and heuristic methods

In the classification of algorithms to distinguish between exact and heuristic solution methods.

Heuristic methods typically provide feasible solutions in a relatively short time, but no information about how good they are in comparison to an optimal solution. If a heuristic is not a solution, it is not known whether this is due to the algorithm, or if the optimization problem under consideration is basically insoluble. Heuristic methods are usually adapted to the problem to be solved, such as the k -Opt heuristics for the traveling salesman problem ends. In metaheuristics such as tabu search, although the basic approach is generic, but each step of the algorithm must be defined depending on the problem under consideration.

Exact methods provably always find an optimal solution or determine that the problem is unsolvable or unlimited, provided one makes the algorithm run indefinitely. Examples of this are branch- and-bound, cutting plane methods and their combination Branch-and -Cut. In practice, you can often significantly speed up this process by adapting to the problem to be solved and by combining them with heuristics. An elegant way to quickly find an exact solution, is the search space - the convex polyhedron in n-dimensional space that contains all possible solutions - to model from the outset so that it contains only integer extreme points. The polyhedron is therefore not reduced subsequently with cutting planes. Failing that - for example, by lift- and-project - then can be solved for example by running the simplex algorithm, the optimization task easy.

Dual bounds and optimality proof

All practically relevant exact method based on the iterative solution, and modification of a relaxation, so a simpler problem whose solution set contains all solutions of the original problem. For example, use branch- and-bound and cutting plane methods, the LP relaxation, so let the first away integrality. This can also be interpreted geometrically: Actually, the best corner of the IP polyhedron ( broken red line in the image ) is searched, which is spanned by all admissible integer points. Since this polyhedron is not exactly known mostly, an optimal vertex of the polyhedron of the LP relaxation is instead searched that contains ( in the above example outlined in blue ). This is relatively simple, such as the simplex method.

As in the relaxation of more solutions are approved as the initial problem, her optimal value is at least as high (for a maximization problem ) as the - unknown - optimum value of the IPs, so this provides an upper (generally dual ) barrier. At the same time, the value defined any valid integer solution has a lower (in general primal ) bound on the value of an optimal solution, since these, by definition, at least as good as. By comparing the upper and lower bounds on the maximum relative distance, the so-called Optimalitätsgap, between the value of the solution found and the optimal value can be specified without knowing exactly this.

In the above example, the optimal value of the LP relaxation 2.8. The optimal value of the integer problem can not be higher because there are fewer solutions are admitted as in the LP relaxation. The point (which can be found, for example, by installments or via a heuristic ) is a feasible solution of the integer problem and has the objective function value 1 An optimal solution is at least as good as the solution found by definition. The optimal value of the integer problem therefore must be between 1 and about 2.8. The absolute Optimalitätsgap is the difference between the upper and lower bound, in this case, the more likely given relative Optimalitätsgap obtained by normalizing this value by the lower bound, in this case, when He says that the optimal value of the integer program increased by more than 180 % is as the value of the solution. This allows for a (not particularly good in this case) quality assessment of the solution. The actual difference is, that is, the optimum value is twice as high as the value of the solution found.

In the course of the algorithm, the relaxation will be gradually increased (for example by adding additional inequalities ), so that the resulting upper limit is smaller. At the same time trying to find better solutions allowed to raise the lower bound. This is illustrated in the adjacent figure. If the value of the solution found and the dual barrier equal to (in this example a value of 2 ), this is the proof that the solution found is optimal.

The following are some important exact and heuristic solution methods are presented in more detail.

Cutting plane method

Cutting plane method ( engl. cutting plane algorithm ) first compute a solution to the LP relaxation. This is usually not an integer, but provides a dual bound for the optimal value of the IPs. This dual barrier is then exacerbated by stepwise adding so-called cutting planes. A cross-sectional plane, an additional inequality which is satisfied by all permissible points of the IP, but not from the current LP solution. Is added to the LP inequality, therefore a different solution has to come out when re- solving. This is continued until an integer solution is found ( which automatically also optimal for the integer program is then ) or no suitable inequalities are found.

Geometrically, this approach adding a hyperplane that cuts the optimal corner of the LP polyhedron of the (unknown ) polyhedron that is spanned by the integer solutions. When re- solving an optimal corner of the cropped polyhedron is determined. If this integer, then one has found a feasible and optimal solution of the integer linear program. Otherwise it will go on a new cutting plane.

The picture to the cutting plane (green) is shown, which separates the current LP optimum ( blue) from the IP polyhedron ( separated). All feasible points lie on one side of the hyperplane, the LP solution on the other side. Re- release of the LPs with this additional inequality provides the green marked point (4/3, 7 /3). This point is still not permitted, but has the smaller objective function value 7/3, which, for example, the relative Optimalitätsgap for the solution (1, 1) is reduced from 180 % to.

In the practical application of cutting-plane methods are an important tool, but alone are usually not sufficient and may lead to numerical problems with improper application. Instead, they are often combined with branch- and-bound. How well this works depends greatly on the structure of the problem to be solved. The best cutting planes that can be found, are facets of IP polyhedron. In the above example these are the inequalities and which correspond to the red dotted lines. To identify such inequalities, a more precise mathematical investigation of the underlying polyhedron is usually necessary.

Branch -and-bound or branch-and -cut

And branch- and-bound begins with the release of the LP relaxation. Is not an integer, the resulting solution, the problem is decomposed as in two or more sub-problems that every feasible solution is contained in one of these sub-problems. In this way, a branching tree is built with the LP relaxation as the root node. At each branching (English branch ) the range of values ​​of one or more variables is restricted. This is continued until a best integer solution has been found.

In this pure form, the process of a complete enumeration of all possible solutions corresponds. With the help of the dual bounds obtained at each node of the branching tree by solving the relaxations, but subtrees can be cut off (german bound), if it turns out that they can not contain an optimal solution. As a sole algorithm Branch-and - Bound is not enough usually because too little can be cut off from the search tree. Good IP solvers combine this method, therefore, to improve the dual bound with cutting planes. This approach is then called branch-and -cut.

In the adjacent example, starting from the fractional LP solution, consider the two sub- problems that occur by adding the additional condition or. Each feasible solution is contained in exactly one of the two Teilpolyeder ( green border ). Solving the LP relaxation with the additional conditions gives the right part of the problem, the fractional solution to the objective function value and in the left part of the problem, the integer solution with value 2 Thus, the lower bound on the optimal IP value improved to 2 (the value of best known feasible solution ) while the upper bound on reduced (the higher SP value of the two problems). The Optimalitätsgap thus reduces to, that is, the optimal value is at most times as high as the value of the solution. In fact, this solution is already optimal, because it is an integer solution of a relaxation of the original problem.

Lagrangian relaxation

The Lagrangian relaxation, a method of nonlinear optimization which can be applied to the integer optimization. The basic idea is to " disturbing " inequalities omit, so that the remaining problem ( with integrality constraints ) is easily solved, and instead to punish the violation of these inequalities, weighted by the so-called Lagrange multipliers, in the objective function.

A solution to this simpler problem is not fulfilled in most cases, the relaxed conditions in the objective function. To change this, the Lagrange multipliers solution be adjusted by means of a Subgradientenverfahrens depending on the current ( illegal ) solution so that a re-dissolving with the new weights a little " zulässigere " generated which less strongly violates the relaxed inequalities. This process is iteratively repeated until all conditions are met. One can show that any solution of a Lagrangian relaxation provides a dual barrier for the original IP, and that this method converges in a suitable adaptation of the multipliers.

Heuristics

For almost any optimization problem can easily find a variety of heuristics that can quickly find feasible solutions for this particular problem. In contrast, the development of heuristic procedures to reliably find good solutions, and possible even for a whole class of related optimization problems, and not just for a specific problem, a non-trivial task.

Examples of problem-specific heuristics in the problem of the traveling salesman are the Minimum Spanning Tree heuristic for the construction of an admissible tour with the help of a minimum spanning tree and the k- opt heuristics to improve a tour already found. This optimization problem is also one of the few examples in which can be easily specify heuristic dual bounds. For example, each tour by node exactly edges so that a shortest tour must be at least as long as the sum of the shortest edge lengths. In general, it is much more difficult to provide good dual bounds.

In addition to these specially developed for a problem method, there are so-called metaheuristics that describe strategies for search admissible solutions on problem- independent way. The individual steps of these algorithms, however, must be tailored to the problem to be solved. Examples include rounding of LP solutions, local search, tabu search, evolutionary algorithms, simulated annealing, variable neighborhood search and ant algorithms. Some of these methods have processes such as natural selection or the behavior of ants looking for food for example; what extent is this the solution quality and solution times in the practice of advantage is controversial.

As the sole solution process all these algorithms have the drawback that they firstly do not always find a solution, and second, mostly known nothing about the quality of found solutions compared to an optimal solution. You can be a very useful role as part of a Branch and Cut approach but, for example, to generate at different nodes of the search tree example from the current LP solution good feasible solutions and to be able to perform so perhaps parts of the tree.