Linear Programming Relaxation

In mathematics, the linear programming relaxation of a 0-1 integer program is the problem that arises by replacing the constraint that each variable must be 0 or 1 by a weaker constraint, that each variable belong to the interval .

That is, for each constraint of the form

of the original integer program, one instead uses a pair of linear constraints

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.

Read more about Linear Programming RelaxationExample, Solution Quality of Relaxed and Original Programs, Approximation and Integrality Gap, Branch and Bound For Exact Solutions, Cutting Plane Method

Other articles related to "programming, linear programming relaxation, linear programming relaxations, relaxation, linear programming, relaxations":

Outline Of Computer Science - Subfields - Programming Languages and Compilers
... Programming language pragmatics – Taxonomy of programming languages, their strength and weaknesses ... Various programming paradigms, such as object-oriented programming ... Programming language theory Formal semantics – rigorous mathematical study of the meaning of programs ...
Direct Connect (file Sharing) - Other Software - Interface and Programming
... Other software GUI CLI Other Programming language Based on jDCbot No No No Java NetDirectConnect No No No Perl FlowLib No No No C# DC-hublink Yes No No Visual Basic Hub-L ...
Outline Of Computer Science - Programming Paradigms
... Imperative programming Functional programming Procedural programming Logic programming Object oriented programming Class Inheritance Object ...
Linear Programming Relaxation - Cutting Plane Method
... 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 ... 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 ... Typical relaxations, such as the relaxation of the set cover problem discussed earlier, form a polytope that strictly contains the convex hull and has ...

Famous quotes containing the words relaxation and/or programming:

    Worst of all, there is no sign of any relaxation of antisemitism. Logically it has nothing to do with Fascism. But the human race is imitative rather than logical; and as Fascism spreads antisemitism spreads.
    George Bernard Shaw (1856–1950)

    If there is a price to pay for the privilege of spending the early years of child rearing in the driver’s seat, it is our reluctance, our inability, to tolerate being demoted to the backseat. Spurred by our success in programming our children during the preschool years, we may find it difficult to forgo in later states the level of control that once afforded us so much satisfaction.
    Melinda M. Marshall (20th century)