Linear Programming Relaxation Task

A Linear Programming Relaxation Task is a 0-1 Integer Programming Task that ...

• See: Linear Programming Algorithm, Interval (Mathematics), Polynomial Time, 0-1 Integer Programming, Linear Program, Relaxation Technique (Mathematics), NP-Hard.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/linear_programming_relaxation Retrieved:2015-12-24.
  • 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 [0,1].

    That is, for each constraint of the form : [math]\displaystyle{ x_i\in\{0,1\} }[/math] of the original integer program, one instead uses a pair of linear constraints : [math]\displaystyle{ 0 \le x_i \le 1. }[/math] 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.

---