Content deleted Content added
→References: link fractional coloring |
cutting plane method |
||
Line 46:
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]] 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 {{harvtxt|Dantzig|Fulkerson|Johnson|1954}} and generalized to other integer programs by {{harvtxt|Gomory|1958}}, 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]] {{harv|Aardal|Weismantel|1997}}.
==See also==
* [[Fractional coloring]],
==References==
* {{citation | contribution=Polyhedral combinatorics: An annotated bibliography | first1 = Karen | last1 = 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}}.
* {{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 | url = http://www.jstor.org/view/00963984/ap010009/01a00030/0}}.
* {{citation | title = A threshhold of ln ''n'' for approximating set cover | journal = Journal of the ACM | year = 1998 | pages = 634–652 |volume = 45 | issue = 4 | last = Feige | first = U. | doi = 10.1145/285055.285059}}.
* {{citation | first = Ralph E. | last = Gomory | authorlink = Ralph E. Gomory | title = Outline of an algorithm for integer solutions to linear programs | journal = [[Bulletin of the American Mathematical Society]] | doi = 10.1090/S0002-9904-1958-10224-4 | volume = 64 | year = 1958 | pages = 275–278}}.
* {{citation | title = On the ratio of optimal integral and fractional covers | last = Lovász | first = Lászlo | journal = Discrete Mathematics | volume = 13 | pages = 383–390 | year = 1975 | doi = 10.1016/0012-365X(75)90058-8 }}.
* {{citation | title=The relaxation method for linear inequalities | last=Motzkin | first=TS | coauthors=IJ Schoenberg | journal=Canadian Journal of Mathematics | year=1954 | volume=6 | pages=393-404}}.
* {{citation | title= Randomized rounding: A technique for provably good algorithms and algorithmic proofs|first1=Prabhakar|last1=Raghavan|first2=Clark D. |last2=Tompson|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 | url = http://portal.acm.org/citation.cfm?id=313689 | pages = 170–178}}.
| |||