| dbo:abstract
|
- Als LP-Relaxation (abgeleitet von Lineare Programmierung) wird bezeichnet, wenn bei einem Problem derganzzahligen linearen Optimierung die Forderung der Ganzzahligkeit aufgegeben wird. So ersetzt man z. B. Nebenbedingungen der Gestalt des originalen ganzzahligen Optimierungsproblems durch die relaxierten Nebenbedingungen Das Problem („Programm“) lässt sich in der relaxierten Form mit Hilfe der linearen Optimierung lösen. Die so entstandene reelle Lösung erfüllt nur in Ausnahmefällen die Ganzzahligkeitsbedingungen des ursprünglichen Problems, mit ihrer Hilfe können jedoch Schlüsse über die Lösung des ursprünglichen Problems gezogen werden. Die Lösung des relaxierten Problems kann auch als Näherungslösung für einen Algorithmus zur ganzzahligen Optimierung verwendet werden. Dies ist von Interesse, da durch die LP-Relaxation ein NP-schweres (ganzzahliges) Optimierungsproblem in ein verwandtes (reelles) Problem transferiert wird, welches in polynomialer Zeit gelöst werden kann. Die Methode wurde von Shmuel Agmon im Jahr 1954 beschrieben. Von einer Relaxation im Kontext eines Optimierungsproblems (z. B. Maximierung einer Zielfunktion) wird allgemein dann gesprochen, wenn die Menge zulässiger Lösungen vergrößert wird. Hierdurch wird der maximale Zielfunktionswert nicht verkleinert. (de)
- In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are of the form . The relaxation of the original integer program instead uses a collection 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. (en)
- En informatique théorique et en recherche opérationnelle, la relaxation continue est une méthode qui consiste à interpréter de façon continue un problème combinatoire ou discret. Cette méthode est utilisée afin d'obtenir des informations sur le problème discret initial et parfois même pour obtenir sa solution. Les problèmes discrets ou combinatoires sont en effet très difficiles à traiter en raison de l'explosion combinatoire et il est courant de les traiter par une méthode de séparation et évaluation (branch and bound en anglais) : la relaxation continue fait partie des algorithmes d'évaluation nécessaire à la mise en œuvre de cette méthode. Lors d'une optimisation linéaire en nombres entiers, la relaxation continue s'avère à la fois efficace et facile à mettre en œuvre. Dans un problème de minimisation, la relaxation continue fournit une borne inférieure de la solution du problème initial discret. En effet, la minimisation continue se fait sur un ensemble contenant l'ensemble des points admissibles du problème discret. Le ratio entre la solution optimale de la relaxation et du problème initial est appelé integrality gap.
* Portail de l'analyse
* Portail de l'informatique théorique (fr)
- In de wiskunde is LP-relaxatie de verandering van een lineaire- programmeringsprobleem met geheeltallige beperkingen door de eis van geheeltalligheid van de variabelen te laten vallen. Het toegelaten gebied kan hierdoor groter worden, waardoor het mogelijk gemakkelijker opgelost kan worden. Er moet dan later wel gecontroleerd worden of de verkregen optimale oplossing aan de oorspronkelijke eisen van geheeltalligheid voldoet, wat waarschijnlijk niet het geval zal zijn. Wel zal de gevonden oplossing gebruikt kunnen worden als een benaderende oplossing voor het oorspronkelijke geheeltallige probleem. Men vervangt bijvoorbeeld nevenvoorwaarden van de vorm in het oorspronkelijke geheeltallige programmeringsprobleem door de 'gerelaxeerde' beperkingen . De methode is beschreven door in 1954. (nl)
- 在数学中，的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： 我们转而使用一对线性约束来代替： 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种把NP难的最优化问题（整数规划）转化为一个相关的多项式时间可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 17161 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- 在数学中，的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： 我们转而使用一对线性约束来代替： 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种把NP难的最优化问题（整数规划）转化为一个相关的多项式时间可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。 (zh)
- Als LP-Relaxation (abgeleitet von Lineare Programmierung) wird bezeichnet, wenn bei einem Problem derganzzahligen linearen Optimierung die Forderung der Ganzzahligkeit aufgegeben wird. So ersetzt man z. B. Nebenbedingungen der Gestalt des originalen ganzzahligen Optimierungsproblems durch die relaxierten Nebenbedingungen Dies ist von Interesse, da durch die LP-Relaxation ein NP-schweres (ganzzahliges) Optimierungsproblem in ein verwandtes (reelles) Problem transferiert wird, welches in polynomialer Zeit gelöst werden kann. Die Methode wurde von Shmuel Agmon im Jahr 1954 beschrieben. (de)
- In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are of the form . The relaxation of the original integer program instead uses a collection of linear constraints (en)
- En informatique théorique et en recherche opérationnelle, la relaxation continue est une méthode qui consiste à interpréter de façon continue un problème combinatoire ou discret. Cette méthode est utilisée afin d'obtenir des informations sur le problème discret initial et parfois même pour obtenir sa solution. Lors d'une optimisation linéaire en nombres entiers, la relaxation continue s'avère à la fois efficace et facile à mettre en œuvre.
* Portail de l'analyse
* Portail de l'informatique théorique (fr)
- In de wiskunde is LP-relaxatie de verandering van een lineaire- programmeringsprobleem met geheeltallige beperkingen door de eis van geheeltalligheid van de variabelen te laten vallen. Het toegelaten gebied kan hierdoor groter worden, waardoor het mogelijk gemakkelijker opgelost kan worden. Er moet dan later wel gecontroleerd worden of de verkregen optimale oplossing aan de oorspronkelijke eisen van geheeltalligheid voldoet, wat waarschijnlijk niet het geval zal zijn. Wel zal de gevonden oplossing gebruikt kunnen worden als een benaderende oplossing voor het oorspronkelijke geheeltallige probleem. (nl)
|
| rdfs:label
|
- LP-Relaxation (de)
- Relaxation continue (fr)
- Linear programming relaxation (en)
- LP-relaxatie (nl)
- 线性规划的松弛 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
