Linear optimization

In the case of linear optimization problems, the set of permissible points (brown) is restricted by linear inequalities (half spaces, defined by hyperplanes ).

The linear optimization or linear programming is one of the main methods of Operations Research and is concerned with the optimization of linear objective functions on an amount by linear equations and inequalities is limited. Often, linear programs (LPs) can be used to solve problems for which no specially developed solution methods are known, for example in the planning of traffic or telecommunications networks or in production planning. The linear optimization is a special case of the convex optimization and basis of several solution methods in the integer linear and the nonlinear optimization . Many properties of linear programs can be interpreted as properties of polyhedra and in this way geometrically modeled and proven.

The term “programming” should be understood in the sense of “planning” rather than in the sense of creating a computer program. It was coined in the mid-1940s by George Dantzig , one of the founders of linear optimization, before computers were used to solve linear optimization problems.

From the point of view of complexity theory , linear optimization is a simple problem because it can be solved in polynomial time with some interior point methods , for example . In practice, however, the simplex method has proven to be one of the fastest algorithms, although in the worst case it has exponential running time. In addition to the actual problem, it also always solves the so-called dual problem, which is used, among other things, in several methods for solving integer linear programs.

history

The method of linear optimization was introduced in 1939 by the Soviet mathematician Leonid Witaljewitsch Kantorowitsch in his essay " Mathematical methods for the organization and planning of production ". Shortly afterwards, the American Frank L. Hitchcock published a paper on a transport problem . At that time, the importance of this work was not yet recognized. Among other things, Kantorowitsch received the Nobel Prize in Economics in 1975 for his contribution to linear optimization .

In the mid-1940s, George Dantzig recognized that many practical limitations could be described by linear inequalities, and for the first time replaced the rules of thumb for solving planning problems with a (linear) objective function. In particular, he established a clear separation between the goal of optimization and the means to solve the planning problem.

Dantzig made the breakthrough for linear optimization in 1947 when he published a paper on the simplex method , which is one of the most widely used methods for solving linear programs today. The American military, especially the US Air Force , who wanted to optimize military operations , initially showed interest in this work . In the years that followed, Dantzig, John von Neumann , Oskar Morgenstern , Tjalling Koopmans and others further developed the method and the associated theory and established connections with game theory . With the advent of computers in the mid-1950s, bigger problems could be solved. From around 1950, the economy, particularly oil refineries, discovered the application possibilities of linear optimization. From the 1970s onwards, the simplex algorithm benefited from algorithmic advances in numerical linear algebra . In particular, the development of numerically stable LR decompositions for solving large linear systems of equations contributed significantly to the success and spread of the simplex method.

In 1979 Leonid Khachiyan published the ellipsoid method , with which linear programs could be solved for the first time - at least theoretically - in polynomial time. In 1984, Narendra Karmarkar and others began developing interior point methods for solving linear programs. These algorithms, which as the first polynomial solution methods also had the potential for practical use, were significantly improved within the following decade. At the same time, the importance of the simplex method for solving sub-problems in integer linear optimization grew. At the beginning of the 1990s, great progress was made here again through the development of new pivot strategies for the dual simplex algorithm, in particular through the dual steepest edge pricing by John Forrest and Donald Goldfarb.

Both the simplex method and various interior point methods are still the subject of current research. Linear optimization is used today in many areas to solve practical problems. Under the prerequisite, which is almost always fulfilled in practical applications, that the occurring LP matrices are sparsely populated ( i.e. have only a few non-zero entries), linear programs with several hundred thousand variables or inequalities can be optimally solved within a few minutes to hours. The actual solution time depends not only on the solution method used, but also heavily on the number and arrangement of the non-zero entries in the matrix involved and on the choice of the starting solution.

Problem definition

Mathematical formulation

In a linear program (LP) one matrix and two vectors and are given. A feasible solution is a vector with nonnegative entries that satisfies the linear conditions ${\ displaystyle A \ in \ mathbb {R} ^ {m, n}}$ ${\ displaystyle b \ in \ mathbb {R} ^ {m, 1}}$ ${\ displaystyle c \ in \ mathbb {R} ^ {1, n}}$ ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$

{\ displaystyle {\ begin {matrix} a_ {11} x_ {1} & + \ ldots & + a_ {1n} x_ {n} & \ leq b_ {1} \\ a_ {21} x_ {1} & + \ ldots & + a_ {2n} x_ {n} & \ leq b_ {2} \\\ vdots & \ vdots & \ vdots & \ vdots \\ a_ {m1} x_ {1} & + \ ldots & + a_ { mn} x_ {n} & \ leq b_ {m} \ end {matrix}}}

Fulfills. The aim is to find one among all admissible vectors that has the standard scalar product ${\ displaystyle x}$

{\ displaystyle cx = c_ {1} x_ {1} + \ ldots + c_ {n} x_ {n}}

maximized. This optimization problem in the so-called standard form is often abbreviated as

{\ displaystyle \ max \ {cx \; | \; Ax \ leq b, x \ geq 0 \}}

written, whereby the conditions and components are to be understood. ${\ displaystyle Ax \ leq b}$ ${\ displaystyle x \ geq 0}$

In addition, there are other equivalent formulations that can be converted into this standard form by simple operations:

Minimization problem instead of maximization problem: Multiplication of the objective function vector by ${\ displaystyle c}$ ${\ displaystyle -1}$
Greater than or equal to less than or equal to conditions: Multiplication of the corresponding inequalities by ${\ displaystyle -1}$
Equality constraints instead of inequality constraints: replacing by and ${\ displaystyle a_ {i} x = b_ {i}}$ ${\ displaystyle a_ {i} x \ leq b_ {i}}$ ${\ displaystyle -a_ {i} x \ leq -b_ {i}}$
Variables without non-negative: replace by with ${\ displaystyle x}$ ${\ displaystyle x'-x ''}$ ${\ displaystyle x ', x' '\ geq 0}$

The linear optimization only deals with problems in which the variables can take on any real numbers. A (mixed) integer linear program , in which some variables may only assume integer values, is not a special case , but - on the contrary - a generalization. Such optimization problems are generally NP-equivalent ; H. probably not solvable efficiently. This case is handled by the linear integer optimization .

Geometric interpretation

A linear program can be interpreted geometrically. If the i. Line of a linear program is in standard form, then the set of all points that satisfy the associated linear equation describes a hyperplane in -dimensional space. The set of points that satisfy the linear inequality consists of all points on one side of the hyperplane (including the hyperplane itself), i.e. it forms a half-space . Each line therefore divides the -dimensional space into two halves, with the points allowed in one half and not in the other. The amount ${\ displaystyle a_ {i} x \ leq b_ {i}}$ ${\ displaystyle \ {x \; | \; a_ {i} x = b_ {i} \}}$ ${\ displaystyle x}$ ${\ displaystyle a_ {i} x = b_ {i}}$ ${\ displaystyle n}$ ${\ displaystyle a_ {i} x \ leq b_ {i}}$ ${\ displaystyle a_ {i} x \ leq b_ {i}}$ ${\ displaystyle n}$

{\ displaystyle P: = \ {x \; | \; Ax \ leq b, \; x \ geq 0 \} = \ {x \; | \; a_ {i} x \ leq b_ {i}, \; i = 1, \ ldots, m, \; x \ geq 0 \}}

of the points that satisfy all inequalities of the LP is exactly the intersection of these half-spaces, i.e. the set of all points that lie in the respective permissible half of the space for each inequality. This set of solutions of the linear program forms a convex polyhedron , i.e. a -dimensional polygon in which the connecting line between any two points is completely contained in. The aim of the optimization is to find one among all points of the polyhedron that maximizes the linear function . Geometrically, this corresponds to the shifting of the hyperplane in the direction of the vector until the shifted hyperplane just touches the polyhedron . The set of all points of contact is exactly the set of optimal solutions of the linear program. ${\ displaystyle P}$ ${\ displaystyle n}$ ${\ displaystyle P}$ ${\ displaystyle P}$ ${\ displaystyle c \ colon \, x \ to c ^ {T} x}$ ${\ displaystyle \ {x \; | \; c ^ {T} x = 0 \}}$ ${\ displaystyle c}$

Permissible amount (blue) of an LP in standard form with restricting inequalities (green), objective function (red line) and an optimal solution (red point)

This arrangement is shown in the adjacent figure for the case of only two variables. A hyperplane in two-dimensional space is a straight line , shown in green in the picture. Each of these straight lines divides the space into a permissible and an impermissible half. The set of points that lie on the admissible side of every straight line form the polyhedron (polygon) shown in blue. The red straight line represents the objective function. The aim is to shift it as far as possible in the direction of the red vector without leaving the polyhedron. In the picture opposite, the red point of contact between the objective function line and the polyhedron is the only optimal solution. ${\ displaystyle c}$

Example from production planning (two-dimensional)

A company manufactures two different products, for the manufacture of which three machines A, B, C are available. These machines have a maximum monthly running time (capacity) of 170 hours (A), 150 hours (B) or 180 hours (C). A unit of measure (MU) of product 1 provides a contribution margin of 300 euros, whereas a unit of measure of product 2 delivers 500 euros. If you manufacture an ME of product 1, you need one hour machine A and one hour machine B. One unit of product 2 occupies machine A for two hours, machine B for one hour and machine C for three hours. Determine production volumes that maximize the company's contribution margin without exceeding machine capacities. Fixed costs can be ignored in the optimization problem and then added, since by definition they are independent of the production quantities to be determined.

Mathematical modeling

Illustration of the example (explanation see text)

Assume that the company produces MUs of product 1 and MUs of product 2. Then the total contribution margin is ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {2}}$

{\ displaystyle G (x_ {1}, x_ {2}) = 300x_ {1} + 500x_ {2}.}

The company wants to maximize this value. Since the machine capacities must be adhered to, the secondary conditions arise:

{\ displaystyle {\ begin {alignedat} {3} x_ {1} & + & 2x_ {2} & \ leq 170 && {\ text {(machine A, drawn in black on the right)}} \\ x_ {1} & + & x_ {2} & \ leq 150 && {\ text {(machine B, drawn in turquoise on the right)}} \\ && 3x_ {2} & \ leq 180 && {\ text {(machine C, drawn in purple on the right)}} \ end { alignedat}}}

Since no negative production quantities are possible, the following must apply (non-negativity condition). ${\ displaystyle x_ {1}, x_ {2} \ geq 0}$

Geometric interpretation as a polyhedron

In the picture opposite, the inequalities from the above example are shown as turquoise, black and purple constraints. Together they define the polyhedron (outlined in blue) of the admissible points. The red-dashed lines represent iso-gain functions; that is, all points on such a line have the same objective function value. Since the company wants to make as much profit as possible, the aim of the optimization is to move such a red dashed line to the top right that it just touches the polyhedron. All points of contact are then optimal. In this case, the point (130.20) is the unique optimal corner and the optimal objective function value is 49,000 euros.

In general, however, the optimal solution of a linear optimization problem is neither unique nor integer. For example, if both products had the same contribution margin, the red iso-profit functions would be parallel to the inequality . In this case, every point between (130.20) and (150.0) would be optimal, so there would be an infinite number of optimal solutions. ${\ displaystyle x_ {1} + x_ {2} \ leq 150}$

Applications

The linear optimization has many applications in practice, some of which are presented here as examples.

Production planning

As in the example above, a company can manufacture a number of products with known contribution margins . Manufacturing a unit of each of these products requires a known amount of limited resources (production capacity, raw materials, labor, etc.). The task is to create a production program , i.e. H. determining how much of each product to produce so that the company's bottom line is maximized without violating resource constraints. Another example is cutting problems .

Mixing problems

Mixing problems are a similar application, in which the aim is to combine ingredients into a final product, whereby the amount of the respective ingredients can be varied within a certain range. An example of this is the diet problem examined by George Dantzig in 1947 : A number of raw materials (e.g. oats, pork, sunflower oil, etc.) are given together with their content of certain nutritional values (e.g. protein, fat, vitamins A etc.) and their price per kilogram. The task is to mix one or more end products from the raw materials with minimal costs, subject to the secondary condition that certain minimum and maximum limits for the individual nutritional values are observed. Such mixing problems also occur during melting processes, such as B. in steel production.

Routing in telecommunications or transport networks

A classic area of application of linear optimization is the determination of a routing for traffic requirements in telecommunications or traffic networks, often in connection with capacity planning. Traffic flows must be routed through a network in such a way that all traffic requirements are met without violating the capacity conditions. These so-called multi-commodity flows (English multicommodity flow ) are an example of a problem that is easy to solve linear optimization, but in the general case, no exact algorithm is known for, is not based on LP-theory.

Game theory

Within mathematical game theory , linear optimization can be used to calculate optimal strategies in two-person zero-sum games . A probability distribution is calculated for each player , which is a random mix of his strategies. If a player randomly “rolls” his strategy according to this probability distribution, he is certain of the best possible profit expectation that he can have if he chooses his strategy independently of that of his opponent.

Nonlinear and integer optimization

Many application problems cannot be sensibly modeled with continuous variables, but require some variables to be integers. For example, 3.7 planes cannot be bought, only a whole number, and a bus can only run all or not at all, but not two-thirds. When using branch-and-cut to solve such an integral linear optimization problem , a large number of similar linear programs must be solved one after the other as sub-problems. Finding an optimal integer solution of a linear program is NP-complete , but can be parameterized in the number of variables. It is even NP-complete to find any integer solution to a linear program. An exception is here, if the restriction set is given by a totally unimodular matrix , then all vertices of the polyhedron are integral. There are also algorithms for solving non-linear optimization problems in which linear programs have to be solved as a sub-problem (e.g. sequential linear programming ).

Solvability from a theoretical point of view

A linear program does not always have an optimal solution. There are three different cases:

The LP is not allowed because inequalities contradict each other (e.g. and ). In this case there is no solution that satisfies all of the inequalities; H. the corresponding polyhedron is the empty set. ${\ displaystyle x \ leq 1}$ ${\ displaystyle x \ geq 2}$
The LP is unlimited, i.e. H. there are infinitely many feasible solutions with arbitrarily high objective function values (e.g. ). ${\ displaystyle \ max \ {x \; | \; x \ geq 0 \}}$
The LP has at least one optimal solution. This is the case, for example, if the associated polyhedron is restricted, i.e. a polytope , and is not empty.

The set of optimal solutions forms a side surface ( corner , edge, ...) of the polyhedron, so that there is either none, exactly one or an infinite number of optimal solutions. If the LP is solvable and limited, there is always an optimal corner, i.e. an optimal point that cannot be convexly combined from other points of the polyhedron . The primal simplex method makes use of this property .

Complexity and solution method

Finding an optimal solution or determining that an LP has no solution is possible with the help of interior point methods or the ellipsoid method in polynomial time, so that linear optimization is an easily solvable problem from the point of view of complexity theory . From a practical point of view, however, the simplex method is often faster, although theoretically it has exponential running time. It is still unknown whether there is a strictly polynomial algorithm for solving general linear programs, i.e. an algorithm whose running time does not depend on the size of the numbers that occur.

Simplex method

The simplex process runs through the corners of the polyhedron until an optimal solution is found.

The simplex method is a basic exchange method that was developed by George Dantzig in 1947 and has been improved considerably since then; it is the most important algorithm for solving linear programs in practice. The basic idea is to walk from one corner of the polyhedron to an adjacent corner with a better objective function value until this is no longer possible. Since the linear optimization is a convex optimization problem , the locally optimal corner thus achieved is also globally optimal. The procedure is illustrated in the picture on the right: The aim is to find a point on the polyhedron that is as high as possible. A possible path of the simplex method along the corners of the polyhedron is shown in red, with the objective function value improving with each step.

From the point of view of complexity theory, the simplex algorithm needs exponential running time in the worst case. For each variant of the algorithm an example could be constructed so far, in which the algorithm runs all corners of the polyhedron, mostly based on the Klee-Minty cube . From a practical point of view, however, such cases are very rare. In so-called degenerate linear programs, in which a corner is defined by more inequalities than absolutely necessary (for example by three inequalities in two-dimensional space), it can happen that the algorithm, as in this example , looks at the same corner over and over again instead of looking at to switch to the next corner. This problem is common with practical planning problems and can result in the algorithm not terminating or the objective function value not improving over many iterations. Good simplex implementations discover such cases and treat them, for example, by a slight perturbation (deliberate numerical disturbance) of the problem, which is later reversed.

Provided that the matrix is sparsely populated (i.e. contains only a few non-zero coefficients), which is almost always the case in practice, very large LPs can now be optimally solved with the simplex method in a reasonable time. A great advantage of the simplex method is that after adding an inequality or variable in the LP or after a slight change in the coefficients, it can perform a "warm start" from a previously reached corner, so that only a few iterations to find again an optimal solution are necessary. This is particularly important in connection with cutting plane methods or branch-and-cut for solving integer linear programs, where very many similar LPs have to be solved in series. ${\ displaystyle A}$

Inner point method

Inner point methods approach an optimal solution through the interior of the polyhedron.

Inner point methods , also known as barrier methods , approach an optimal corner through the inside of the polyhedron (see picture). The first such algorithm was described by Narendra Karmarkar in 1984 . Its importance lay primarily in the fact that it was the first polynomial algorithm for solving linear programs that had the potential to be practical. The decisive breakthroughs that made the inner point method competitive with the simplex algorithm were not achieved until the 1990s. One advantage of these methods is that, in contrast to the simplex method, they can also be used, in a slight modification, to solve quadratic or certain non-linear programs . Furthermore, they are often superior to the simplex method for large, sparse problems. One disadvantage is that after adding a secondary condition or variable in the LP, they cannot be “warm-started” as efficiently as the simplex method.

Ellipsoid method

Two iterations of the ellipsoid method

The ellipsoid method was originally developed in 1976 and 1977 by David Yudin and Arkadi Nemirovski and independently by Naum Schor to solve convex optimization problems . In 1979, the Soviet mathematician Leonid Khachiyan modified the method and thus developed the first polynomial algorithm for solving linear programs. However, it is not suitable for practical purposes. The ellipsoid method is used to find any point in a full-dimensional polyhedron or to determine that the polyhedron is empty. Since one can show that the solution of an LP is equivalent to finding a feasible point in a suitably defined auxiliary polyhedron, an LP can (theoretically) also be solved with the help of the ellipsoid method.

The basic idea of the procedure is to define an ellipsoid (red in the picture) that contains all corners of the polyhedron (blue). It is then determined whether the center of this ellipsoid is contained in the polyhedron. If so, you have found a point in the polyhedron and can stop. Otherwise you can determine the semi-ellipsoid in which the polyhedron must be contained and place a new, smaller ellipsoid around the polyhedron (green in the picture). After a number of steps, which depends polynomially on the coding length of the LP, you have either found a point in the polyhedron or you know that the polyhedron is empty, because otherwise it would have to be larger than the current ellipsoid.

Other methods

For some classes of linear programs there are special algorithms that theoretically or practically run faster than z. B. the simplex algorithm. An example of this is the Hungarian method , which can be applied to mapping problems. Linear programs with two variables can be solved approximately graphically (see example above ). However, this method is mainly of didactic value, since LPs occurring in practice can easily have several hundreds of thousands of variables.

duality

Upper bounds

In order to verify that a valid solution is optimal for a linear program, one tries to estimate the objective function value of the program upwards. For the above example, roughly applies ${\ displaystyle x ^ {*}}$

{\ displaystyle x_ {1} + x_ {2} \ leq 150 \; \ Rightarrow \; 500x_ {1} + 500x_ {2} \ leq 500 \ cdot 150 = 75000}

There and it follows that ${\ displaystyle x_ {1} \ geq 0}$ ${\ displaystyle x_ {2} \ geq 0}$

{\ displaystyle G (x_ {1}, x_ {2}) = 300x_ {1} + 500x_ {2} \ leq 500x_ {1} + 500x_ {2} \ leq 75000}

The optimal solution cannot therefore have an objective function value greater than . A better estimate can be obtained by adding times the second and times the third inequality: ${\ displaystyle 75000}$ ${\ displaystyle 300}$ ${\ displaystyle 100}$

{\ displaystyle G (x_ {1}, x_ {2}) = 300x_ {1} + 500x_ {2} \ leq 300 \ cdot (x_ {1} + x_ {2}) + 100 \ cdot (3x_ {2} ) = 300x_ {1} + 600x_ {2} \ leq 63000}

This procedure can easily be generalized: If one chooses multipliers in standard form for a given LP , then each vector is an upper bound, provided that . This corresponds to a conical combination of the columns of . The condition ensures that the coefficients of for against can be estimated. The objective function value of the upper bound given by is thus . To find the best upper bound, you can now set up another LP: ${\ displaystyle y \ in \ mathbb {R} _ {+} ^ {m}}$ ${\ displaystyle y ^ {T} A}$ ${\ displaystyle y ^ {T} A \ geq c ^ {T}}$ ${\ displaystyle A}$ ${\ displaystyle y ^ {T} A \ geq c ^ {T}}$ ${\ displaystyle c ^ {T}}$ ${\ displaystyle x \ geq 0}$ ${\ displaystyle y ^ {T} A}$ ${\ displaystyle y}$ ${\ displaystyle y ^ {T} b}$

{\ displaystyle \ min \; \ {y ^ {T} b \,: \, y ^ {T} A \ geq c ^ {T}, \; y \ geq 0 \}}

This LP is called the dual problem to the primal problem

{\ displaystyle \ max \; \ {c ^ {T} x \,: \, Ax \ leq b, \; x \ geq 0 \}}

The entries of the vector are called multipliers or dual variables . The duality of linear programs is a special case of the Lagrange duality . ${\ displaystyle y}$

If a linear program arises from a combinatorial optimization problem , the dual program often has a clear interpretation; the following theorems can then also be used to derive results such as the Max-Flow-Min-Cut theorem .

Dualization of any linear programs

For linear programs that are not in standard form, the following rules for dualization apply:

primal LP	dual LP
${\ displaystyle \ max \; \ {c ^ {T} x \,: \, Ax \ leq b, \; x \ geq 0 \}}$	${\ displaystyle \ min \; \ {y ^ {T} b \,: \, y ^ {T} A \ geq c ^ {T}, \; y \ geq 0 \}}$
${\ displaystyle \ max \; \ {c ^ {T} x \,: \, Ax = b, \; x \ geq 0 \}}$	${\ displaystyle \ min \; \ {y ^ {T} b \,: \, y ^ {T} A \ geq c ^ {T} \}}$
${\ displaystyle \ max \; \ {c ^ {T} x \,: \, Ax \ leq b \}}$	${\ displaystyle \ min \; \ {y ^ {T} b \,: \, y ^ {T} A = c ^ {T}, \; y \ geq 0 \}}$

The same applies to minimization problems:

primal LP	dual LP
${\ displaystyle \ min \; \ {c ^ {T} x \,: \, Ax \ geq b, \; x \ geq 0 \}}$	${\ displaystyle \ max \; \ {y ^ {T} b \,: \, y ^ {T} A \ leq c ^ {T}, \; y \ geq 0 \}}$
${\ displaystyle \ min \; \ {c ^ {T} x \,: \, Ax = b, \; x \ geq 0 \}}$	${\ displaystyle \ max \; \ {y ^ {T} b \,: \, y ^ {T} A \ leq c ^ {T} \}}$
${\ displaystyle \ min \; \ {c ^ {T} x \,: \, Ax \ geq b \}}$	${\ displaystyle \ max \; \ {y ^ {T} b \,: \, y ^ {T} A = c ^ {T}, \; y \ geq 0 \}}$

In general:

primal LP	dual LP
nonnegative variable	Inequality
unsigned variable	equation
Inequality	nonnegative variable
equation	unsigned variable

It should be noted that in the case of maximization problems the inequalities are always written in the form and in the case of minimization problems in the form . ${\ displaystyle Ax \ leq b}$ ${\ displaystyle Ax \ geq b}$

Features of the dual program

The primal and dual LP form a dual pair, so it is true that the primal LP emerges from the dualization of the dual LP.

Furthermore, the following applies to any feasible primal or dual solutions : ${\ displaystyle x, y}$

{\ displaystyle c ^ {T} x \ leq y ^ {T} Ax \ leq y ^ {T} b}

The first inequality applies, because and and the second, because and . This result is known as the weak duality principle . It corresponds to the weak duality in the Lagrange duality. ${\ displaystyle x \ geq 0}$ ${\ displaystyle y ^ {T} A \ geq c ^ {T}}$ ${\ displaystyle Ax \ leq b}$ ${\ displaystyle y \ geq 0}$

The strong duality principle

The strong duality theorem aggravates the above statement: If one of the two LPs has a restricted optimal solution, then so does the other, and the optimal objective function values are the same in this case. So for every optimal solution of the primal and every optimal solution of the dual problem ${\ displaystyle x ^ {*}}$ ${\ displaystyle y ^ {*}}$

{\ displaystyle c ^ {T} \; x ^ {*} = (y ^ {*}) ^ {T} b}

.

This corresponds to the strong duality in the Lagrange duality. It can be shown that the following relationships apply:

The dual problem has a bounded optimal solution if and only if the primal problem has a bounded optimal solution.
If the primal problem has no feasible solution, the dual problem is unbounded or has no feasible solution either.
If the primal problem is unbounded, the dual problem has no feasible solution.

These and other sentences form the basis for all procedures that work with primal and dual bounds for the value of an optimal solution, such as branch-and-cut and cutting plane procedures .

The theorem of complementary slip

In addition to the above relationships about the solvability of the primal or dual problem, the following statement applies:

If both the primal and the dual problem have feasible solutions, then there exists a pair of solutions with the property that ${\ displaystyle x ^ {*}, y ^ {*}}$

{\ displaystyle y_ {i} ^ {*} \ cdot (b_ {i} - (Ax ^ {*}) _ {i}) = 0 \; \; \; \ forall i = 1, \ ldots, m}

This means that and vice versa . The -th component of the vector denotes . ${\ displaystyle y_ {i} ^ {*}> 0 \; \ Rightarrow \; (Ax ^ {*}) _ {i} = b_ {i}}$ ${\ displaystyle (Ax ^ {*}) _ {i} <b_ {i} \; \ Rightarrow \; y_ {i} ^ {*} = 0}$ ${\ displaystyle (Ax ^ {*}) _ {i}}$ ${\ displaystyle i}$ ${\ displaystyle Ax ^ {*}}$

These solutions are also optimal, since in this case the above inequalities are satisfied with equality:

{\ displaystyle c ^ {T} x ^ {*} = (y ^ {*}) ^ {T} Ax ^ {*} = (y ^ {*}) ^ {T} b}

.

This additional property is used, for example, in primal-dual algorithms to verify the optimality of a solution.

Equivalence of optimization and admissibility problems

The strong duality theorem also makes it possible to reduce optimization problems to admissibility problems: Instead of solving the problem, one can just as easily find a pair of solutions that obey the following conditions: ${\ displaystyle \ max \; \ {c ^ {T} x \,: \, Ax \ leq b, \; x \ geq 0 \}}$

{\ displaystyle {\ begin {aligned} Ax & \ leq b, \; x \ geq 0 \\ y ^ {T} A & \ geq c ^ {T}, \; y \ geq 0 \\ c ^ {T} x & \ geq y ^ {T} b \\\ end {aligned}}}

The first two conditions ensure that there is a valid solution to the problem, while the next conditions ensure that is valid for the dual program. The last inequality is only fulfilled by those solution pairs whose objective function values match. This is precisely the case if and are the optimal solutions to the two problems. The above optimization problem thus has an optimal solution if and only if the above polyhedron is not empty. Obviously, one can also decide the admissibility of a problem by solving an optimization problem, for example one chooses the zero vector as the objective function. Thus linear optimization problems and admissibility problems of polyhedra are equivalent in terms of their time complexity . ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle x, y}$ ${\ displaystyle x}$ ${\ displaystyle y}$

literature

Robert Bixby : Solving real-world linear programs: A decade and more of progress. In: Operations Research. Volume 50, No. 1, 2002, pp. 3-15.
George B. Dantzig : Linear Programming and Extensions. Springer, 1966. (Original edition: Linear Programming and Extensions. Rand Corp., Santa Monica 1959)
Vašek Chvátal : Linear Programming. Freeman, New York 1983, ISBN 0-7167-1587-2 .
Alexander Schrijver : Theory of Linear and Integer Programming. Wiley, 1998, ISBN 0-471-98232-6 .
Peter Knabner , Wolf Barth : Lineare Algebra. Basics and Applications. Springer Spectrum, Berlin / Heidelberg 2013, ISBN 978-3-642-32185-6 .
FL Hitchcock: The distribution of a product from several sources to numerous localities. In: Journal of Mathematical Physics. Volume 20, 1941, pp. 224-230.
Leonid Kantorowitsch : Mathematical Methods of Organizing and Planning Production. In: Management Science. Vol. 6, No. 4, 1960, pp. 366-422. (online at: jstor.org )
Klaus Hagendorf: OpenOffice calc Solver solutions to the examples in Kantorowitsch's article from 1939. (online at: eurodos.free.fr , ZIP; 521 kB)
Wolfgang Domschke , Andreas Drexl, Robert Klein, Armin Scholl: Introduction to Operations Research. 9th edition. Springer, Berlin 2015, ISBN 978-3-662-48215-5 , chapter 2.

Web links

Comparison of non-commercial LP codes from Hans Mittelmann, Arizona State University, with links to the codes
The Diet Problem ( Memento from May 27, 2010 in the Internet Archive )
Lecture notes with German-language introduction to linear optimization (PDF; 1.9 MB)

Individual evidence

^ Mathematical Methods of Organizing and Planning Production. (PDF; 1.4 MB). In: Management Science. Volume 6, No. 4 (July 1960), pp. 366-422.
^ Heiner Müller-Merbach: Operations Research. 3. Edition. Verlag Franz Vahlen, Munich 1973, ISBN 3-8006-0388-8 , p. 89.
^ N. Karmarkar: A new polynomial-time algorithm for linear programming . Combinatorica 4 (1984), No. 4, 373-395.
↑ Harvey J. Greenberg: Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method. University of Colorado at Denver, 1997 ( PDF ).

[1] Mathematical Methods of Organizing and Planning Production. (PDF; 1.4 MB). In: Management Science. Volume 6, No. 4 (July 1960), pp. 366-422.

[2] Heiner Müller-Merbach: Operations Research. 3. Edition. Verlag Franz Vahlen, Munich 1973, ISBN 3-8006-0388-8 , p. 89.

[3] N. Karmarkar: A new polynomial-time algorithm for linear programming . Combinatorica 4 (1984), No. 4, 373-395.

[4] Harvey J. Greenberg: Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method. University of Colorado at Denver, 1997 ( PDF ).