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 Relaxation:  Example, Solution Quality of Relaxed and Original Programs, Approximation and Integrality Gap, Branch and Bound For Exact Solutions, Cutting Plane Method

Famous quotes containing the words programming and/or relaxation:

    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)

    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)