Linear programming relaxation: Difference between revisions

Revision as of 16:04, 29 January 2023

Latest revision as of 17:52, 10 January 2025

(7 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|Concept in integral mathematics}}

[[File:IP_polytope_with_LP_relaxation.svg|right|thumb|300px|A (general) [[integer program]] and its LP-relaxation]]

[[File:IntLinPgmRelax svg.svg|thumb|400px|A (general) [[integer program]] and its LP-relaxation. The solution set of the former (depicted in red) is strictly smaller than that of the latter (in blue), leading to different optimal solutions.]]

In mathematics, the '''relaxation''' of a [[Mixed integer linear programming|(mixed) integer linear program]] is the problem that arises by removing the integrality constraint of each variable.

Line 12 ⟶ 13:

==Example==

Consider the [[set cover problem]], the linear programming relaxation of which was first considered by Lovász in 1975.<ref>{{harvtxt|Lovász|1975}}.</ref> In this problem, one is given as input a family of [[set (mathematics)|set]]s ''F'' = {''S''₀, ''S''₁, ...}; the task is to find a subfamily, with as few sets as possible, having the same [[union (set theory)|union]] as ''F''.

To formulate this as a 0–1 integer program, form an [[indicator variable]] ''x_i'' for each set ''S_i'', that takes the value 1 when ''S_i'' 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

Line 25 ⟶ 26:

==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 theit optimalhappens solutionthat, toin the linearoptimal program happens to havesolution, all variables eitherhave 0integer or 1values, then 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.)

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.

Line 40:

Typically, the integrality gap translates into the [[approximation ratio]] of an approximation algorithm. This is because an approximation algorithm relies on some rounding strategy that finds, for every relaxed solution of size <math>M_\text{frac}</math>, an integer solution of size at most <math>RR\cdot M_\text{frac}</math> (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 <math>M_\text{int} = IG\cdot M_\text{frac}</math>. Therefore necessarily <math>RR \geq IG</math>. 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 ''H_n'', 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]] .<ref>{{harv|Raghavan|TompsonThompson|1987}}.</ref> Given a fractional cover, in which each set ''S_i'' has weight ''w_i'', choose randomly the value of each 0–1 indicator variable ''x_i'' to be 1 with probability ''w_i''&nbsp;×&nbsp;(ln&nbsp;''n''&nbsp;+1), and 0 otherwise. Then any element ''e_j'' 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&nbsp;''n'')''W'', where ''W'' is the total weight of the fractional solution. Thus, this technique leads to a [[Randomized algorithm|randomized]] approximation algorithm that finds a set cover within a logarithmic factor of the optimum. As Young showed in 1995<ref>{{harvtxt|Young|1995}} showed,</ref> 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 ''H_n'' 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 .<ref>{{harv|Feige|1998}}.</ref>

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.

Line 58:

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]] 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]] 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 [[Facet (mathematics)|facet]]s 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 Dantzig, Fulkerson, and Johnson in 1954<ref>{{harvtxt|Dantzig|Fulkerson|Johnson|1954}}</ref> and generalized to other integer programs by Gomory in 1958,<ref>{{harvtxt|Gomory|1958}},</ref> 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]] .<ref>{{harv|Aardal|Weismantel|1997}}.</ref>

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.

Line 69:

==References==

{{reflist}}

* {{citation | contribution=Polyhedral combinatorics: An annotated bibliography | first1 = Karen | last1 = Aardal | author1-link = Karen Aardal | first2 = Robert | last2 = Weismantel | title = Annotated Bibliographies in Combinatorial Optimization | publisher = Wiley | year = 1997 | url = http://www.cs.uu.nl/research/techreps/repo/CS-1996/1996-27.pdf}}.

* {{citation | title=The relaxation method for linear inequalities | last=Agmon | first=Shmuel | journal=Canadian Journal of Mathematics | year=1954 | volume=6 | pages=382–392 | url = http://www.math.ca/cjm/v6/p382 | doi=10.4153/CJM-1954-037-2| doi-access=free }}.

* {{citation | title = Solution of a large-scale traveling-salesman problem | first1 = George | last1 = Dantzig | authorlink1 = George Dantzig | first2 = D. R. | last2 = Fulkerson | authorlink2 = D. R. Fulkerson | first3 = Selmer | last3 = Johnson | journal = Journal of the Operations Research Society of America | volume = 2 | issue = 4 | year = 1954 | pages = 393–410 | doi = 10.1287/opre.2.4.393 }}.

* {{citation | title = A threshold of ln ''n'' for approximating set cover | journal = Journal of the ACM | year = 1998 | pages = 634–652 |volume = 45 | issue = 4 | last = Feige | first = Uriel | authorlink = Uriel Feige | doi = 10.1145/285055.285059| citeseerx = 10.1.1.70.5014 }}.

Line 77 ⟶ 78:

* {{citation | title=The relaxation method for linear inequalities | last1=Motzkin | first1=T. S. | author1-link = Theodore Motzkin | first2=I. J. | last2 = Schoenberg | author2-link = Isaac Jacob Schoenberg | journal=Canadian Journal of Mathematics | year=1954 | volume=6 | pages=393–404 | url = http://www.math.ca/cjm/v6/p393 | doi=10.4153/CJM-1954-038-x| doi-access=free }}.

* {{citation | title= Randomized rounding: A technique for provably good algorithms and algorithmic proofs|first1=Prabhakar|last1=Raghavan|first2=Clark D. |last2=Thompson|journal=Combinatorica|volume=7|issue=4|year=1987|pages=365–374|doi=10.1007/BF02579324}}.

* {{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 | contribution-url = http://portal.acm.org/citation.cfm?id=313689 | pages = 170–178| isbn = 9780898713497 | series = Soda '95 }}.

[[Category:Linear programming]]