Transcription of 10.1 Integer Programming and LP relaxation
{{id}} {{{paragraph}}}
Example: confidence
10.1 Integer Programming and LP relaxation
CS787: Advanced AlgorithmsLecture 10: lp relaxation and RoundingIn this lecture we will design approximation algorithms using linear Programming . The key insightbehind this approach is that the closely related Integer Programming problem is NP-hard (a proofis left to the reader). We can therefore reduce any NP-complete optimization problem to an integerprogram, relax it to a linear program by removing the integrality constraints, solve the linearprogram, and then round the LP solution to a solution to the original problem. We first describethe Integer Programming problem in more Integer Programming and LP relaxationDefinition Integer program is a linear program in which all variables must be in a linear program, the constraints in an Integer program form a polytope. However, thefeasible set is given by the set of all Integer -valued points within the polytope, and not the entirepolytope. Therefore, the feasible region is not a convex set.
the integer programming problem in more detail. De nition 10.1.1 An integer program is a linear program in which all variables must be integers. As in a linear program, the constraints in an integer program form a polytope.
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: