HOME

TheInfoList



OR:

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are of the form :x_i\in\. The relaxation of the original integer program instead uses a collection of linear constraints :0 \le x_i \le 1. The resulting relaxation is a linear program, hence the name. This relaxation technique transforms an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming); the solution to the relaxed linear program can be used to gain information about the solution to the original integer program.


Example

Consider the
set cover problem The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. Given a set of elements (called the uni ...
, the linear programming relaxation of which was first considered by . In this problem, one is given as input a family of
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
s ''F'' = ; the task is to find a subfamily, with as few sets as possible, having the same
union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''U ...
as ''F''. To formulate this as a 0–1 integer program, form an
indicator variable In regression analysis, a dummy variable (also known as indicator variable or just dummy) is one that takes the values 0 or 1 to indicate the absence or presence of some categorical effect that may be expected to shift the outcome. For example, i ...
''xi'' for each set ''Si'', that takes the value 1 when ''Si'' belongs to the chosen subfamily and 0 when it does not. Then a valid cover can be described by an assignment of values to the indicator variables satisfying the constraints :\textstyle x_i\in\ (that is, only the specified indicator variable values are allowed) and, for each element ''ej'' of the union of ''F'', :\textstyle \sum_ x_i \ge 1 (that is, each element is covered). The minimum set cover corresponds to the assignment of indicator variables satisfying these constraints and minimizing the linear objective function :\textstyle \min \sum_i x_i. The linear programming relaxation of the set cover problem describes a ''fractional cover'' in which the input sets are assigned weights such that the total weight of the sets containing each element is at least one and the total weight of all sets is minimized. As a specific example of the set cover problem, consider the instance ''F'' = . There are three optimal set covers, each of which includes two of the three given sets. Thus, the optimal value of the objective function of the corresponding 0–1 integer program is 2, the number of sets in the optimal covers. However, there is a fractional solution in which each set is assigned the weight 1/2, and for which the total value of the objective function is 3/2. Thus, in this example, the linear programming relaxation has a value differing from that of the unrelaxed 0–1 integer program.


Solution quality of relaxed and original programs

The linear programming relaxation of an integer program may be solved using any standard linear programming technique. If the optimal solution to the linear program happens to have all variables either 0 or 1, it will also be an optimal solution to the original integer program. However, this is generally not true, except for some special cases (e.g., problems with totally unimodular matrix specifications.) In all cases, though, the solution quality of the linear program is at least as good as that of the integer program, because any integer program solution would also be a valid linear program solution. That is, in a maximization problem, the relaxed program has a value greater than or equal to that of the original program, while in a minimization problem such as the set cover problem the relaxed program has a value smaller than or equal to that of the original program. Thus, the relaxation provides an optimistic bound on the integer program's solution. In the example instance of the set cover problem described above, in which the relaxation has an optimal solution value of 3/2, we can deduce that the optimal solution value of the unrelaxed integer program is at least as large. Since the set cover problem has solution values that are integers (the numbers of sets chosen in the subfamily), the optimal solution quality must be at least as large as the next larger integer, 2. Thus, in this instance, despite having a different value from the unrelaxed problem, the linear programming relaxation gives us a tight lower bound on the solution quality of the original problem.


Approximation and integrality gap

Linear programming relaxation is a standard technique for designing
approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned so ...
s for hard optimization problems. In this application, an important concept is the integrality gap, the maximum ratio between the solution quality of the integer program and of its relaxation. In an instance of a minimization problem, if the real minimum (the minimum of the integer problem) is M_\text, and the relaxed minimum (the minimum of the linear programming relaxation) is M_\text, then the integrality gap of that instance is IG = \frac. In a maximization problem the fraction is reversed. The integrality gap is always at least 1. In the example above, the instance ''F'' = shows an integrality gap of 4/3. Typically, the integrality gap translates into the
approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix '' ...
of an approximation algorithm. This is because an approximation algorithm relies on some rounding strategy that finds, for every relaxed solution of size M_\text, an integer solution of size at most RR\cdot M_\text (where ''RR'' is the rounding ratio). If there is an instance with integrality gap ''IG'', then ''every'' rounding strategy will return, on that instance, a rounded solution of size at least M_\text = IG\cdot M_\text. Therefore necessarily RR \geq IG. The rounding ratio ''RR'' is only an upper bound on the approximation ratio, so in theory the actual approximation ratio may be lower than ''IG'', but this may be hard to prove. In practice, a large ''IG'' usually implies that the approximation ratio in the linear programming relaxation might be bad, and it may be better to look for other approximation schemes for that problem. For the set cover problem, Lovász proved that the integrality gap for an instance with ''n'' elements is ''Hn'', the ''n''th harmonic number. One can turn the linear programming relaxation for this problem into an approximate solution of the original unrelaxed set cover instance via the technique of randomized rounding . Given a fractional cover, in which each set ''Si'' has weight ''wi'', choose randomly the value of each 0–1 indicator variable ''xi'' to be 1 with probability ''wi'' × (ln ''n'' +1), and 0 otherwise. Then any element ''ej'' has probability less than 1/(''e''×''n'') of remaining uncovered, so with constant probability all elements are covered. The cover generated by this technique has total size, with high probability, (1+o(1))(ln ''n'')''W'', where ''W'' is the total weight of the fractional solution. Thus, this technique leads to a randomized approximation algorithm that finds a set cover within a logarithmic factor of the optimum. As showed, both the random part of this algorithm and the need to construct an explicit solution to the linear programming relaxation may be eliminated using the method of conditional probabilities, leading to a deterministic greedy algorithm for set cover, known already to Lovász, that repeatedly selects the set that covers the largest possible number of remaining uncovered elements. This greedy algorithm approximates the set cover to within the same ''Hn'' factor that Lovász proved as the integrality gap for set cover. There are strong complexity-theoretic reasons for believing that no polynomial time approximation algorithm can achieve a significantly better approximation ratio . Similar randomized rounding techniques, and derandomized approximation algorithms, may be used in conjunction with linear programming relaxation to develop approximation algorithms for many other problems, as described by Raghavan, Tompson, and Young.


Branch and bound for exact solutions

As well as its uses in approximation, linear programming plays an important role in
branch and bound Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutio ...
algorithms for computing the true optimum solution to hard optimization problems. If some variables in the optimal solution have fractional values, we may start a
branch and bound Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutio ...
type process, in which we recursively solve subproblems in which some of the fractional variables have their values fixed to either zero or one. In each step of an algorithm of this type, we consider a subproblem of the original 0–1 integer program in which some of the variables have values assigned to them, either 0 or 1, and the remaining variables are still free to take on either value. In subproblem ''i'', let ''Vi'' denote the set of remaining variables. The process begins by considering a subproblem in which no variable values have been assigned, and in which ''V0'' is the whole set of variables of the original problem. Then, for each subproblem ''i'', it performs the following steps. # Compute the optimal solution to the linear programming relaxation of the current subproblem. That is, for each variable ''xj'' in ''Vi'', we replace the constraint that ''xj'' be 0 or 1 by the relaxed constraint that it be in the interval ,1 however, variables that have already been assigned values are not relaxed. # If the current subproblem's relaxed solution is worse than the best integer solution found so far, backtrack from this branch of the recursive search. # If the relaxed solution has all variables set to 0 or 1, test it against the best integer solution found so far and keep whichever of the two solutions is best. # Otherwise, let ''xj'' be any variable that is set to a fractional value in the relaxed solution. Form two subproblems, one in which ''xj'' is set to 0 and the other in which ''xj'' is set to 1; in both subproblems, the existing assignments of values to some of the variables are still used, so the set of remaining variables becomes ''Vi'' \ . Recursively search both subproblems. Although it is difficult to prove theoretical bounds on the performance of algorithms of this type, they can be very effective in practice.


Cutting plane method

Two 0–1 integer programs that are equivalent, in that they have the same objective function and the same set of feasible solutions, may have quite different linear programming relaxations: a linear programming relaxation can be viewed geometrically, as a
convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the w ...
that includes all feasible solutions and excludes all other 0–1 vectors, and infinitely many different polytopes have this property. Ideally, one would like to use as a relaxation the
convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean spac ...
of the feasible solutions; linear programming on this polytope would automatically yield the correct solution to the original integer program. However, in general, this polytope will have exponentially many facets and be difficult to construct. Typical relaxations, such as the relaxation of the set cover problem discussed earlier, form a polytope that strictly contains the convex hull and has vertices other than the 0–1 vectors that solve the unrelaxed problem. The cutting-plane method for solving 0–1 integer programs, first introduced for the traveling salesman problem by and generalized to other integer programs by , takes advantage of this multiplicity of possible relaxations by finding a sequence of relaxations that more tightly constrain the solution space until eventually an integer solution is obtained. This method starts from any relaxation of the given program, and finds an optimal solution using a linear programming solver. If the solution assigns integer values to all variables, it is also the optimal solution to the unrelaxed problem. Otherwise, an additional linear constraint (a ''cutting plane'' or ''cut'') is found that separates the resulting fractional solution from the convex hull of the integer solutions, and the method repeats on this new more tightly constrained problem. Problem-specific methods are needed to find the cuts used by this method. It is especially desirable to find cutting planes that form facets of the convex hull of the integer solutions, as these planes are the ones that most tightly constrain the solution space; there always exists a cutting plane of this type that separates any fractional solution from the integer solutions. Much research has been performed on methods for finding these facets for different types of combinatorial optimization problems, under the framework of polyhedral combinatorics . The related branch and cut method combines the cutting plane and branch and bound methods. In any subproblem, it runs the cutting plane method until no more cutting planes can be found, and then branches on one of the remaining fractional variables.


See also

*
Fractional coloring Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent ve ...
, a linear programming relaxation of graph coloring. * Randomized rounding, for obtaining a solution to the original problem from a solution to the relaxation.


References

* . * . * . * . * . * . * . * . * {{citation , contribution = Randomized rounding without solving the linear program , first = Neal E. , last = Young , title = Proc. 6th ACM-SIAM Symp. Discrete Algorithms (SODA) , year = 1995 , url = http://portal.acm.org/citation.cfm?id=313689 , pages = 170–178, isbn = 9780898713497 , series = Soda '95 . Linear programming Combinatorial optimization Polyhedral combinatorics Relaxation (approximation)