Linear Programming Relaxation Task: Difference between revisions
Jump to navigation
Jump to search
(Created page with "A Linear Programming Relaxation Task is a 0-1 Integer Programming Task that ... * <B>See:</B> Linear Programming Algorithm, Interval (Mathematics), Polynomia...") |
m (Text replacement - "n''' " to "n</B> ") |
||
| Line 7: | Line 7: | ||
=== 2015 === | === 2015 === | ||
* (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/linear_programming_relaxation Retrieved:2015-12-24. | * (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/linear_programming_relaxation Retrieved:2015-12-24. | ||
** In mathematics, the '''linear programming relaxation | ** In mathematics, the '''linear programming relaxation</B> of a [[0-1 integer programming|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 (mathematics)|interval]] [0,1]. <P> That is, for each constraint of the form : <math> x_i\in\{0,1\} </math> of the original integer program, one instead uses a pair of linear constraints : <math> 0 \le x_i \le 1. </math> The resulting relaxation is a [[linear program]], hence the name. This [[Relaxation technique (mathematics)|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. | ||
---- | ---- | ||
[[Category:Concept]] | [[Category:Concept]] | ||
__NOTOC__ | __NOTOC__ | ||
Revision as of 06:42, 26 December 2015
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.
- 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].