Linear Programming Relaxation: Difference between revisions

From GM-RKB
Jump to navigation Jump to search
No edit summary
 
Line 1: Line 1:
'''See:''' [[Linear Programming Algorithm]].
#REDIRECT [[Linear Programming Relaxation Task]]
----
----
==References ==
 
=== 2009 ===
* http://en.wikipedia.org/wiki/Linear_programming_relaxation
** In mathematics, the '''linear programming relaxation''' 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].
** That is, for each constraint of the form
*** x_i\in\{0,1\}
** of the original integer program, one instead uses a pair of linear constraints
*** 0 \le x_i \le 1.
** 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|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.
 
----
 
__NOTOC__
[[Category:Malformed]]
 
A [[Linear Programming Relaxation]] is a [[0-1 Integer Programming]] that ...
* <B>See:</B> [[Interval (Mathematics)]], [[Polynomial Time]], [[0-1 Integer Programming]], [[Linear Program]], [[Relaxation Technique (Mathematics)]], [[NP-Hard]].
----
----
==References==
 
=== 2015 ===
* (Wikipedia, 2015) &rArr; http://en.wikipedia.org/wiki/linear_programming_relaxation Retrieved:2015-12-24.
** In mathematics, the '''linear programming relaxation''' 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]]
__NOTOC__

Latest revision as of 06:03, 25 December 2015

Redirect to:

Retrieved from "http://www.gabormelli.com/RKB/index.php?title=Linear_Programming_Relaxation&oldid=241712"