LP-Relaxierung

LP-Relaxierung
QS-Informatik

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen und beteilige dich an der Diskussion! (+)

Als LP-Relaxation (abgeleitet von Lineare Programmierung) wird bezeichnet, wenn bei einem Problem der ganzzahligen linearen Optimierung die Forderung der Ganzzahligkeit aufgegeben wird. 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. Dies ist von Interesse, da durch die LP-Relaxation ein NP-schweres (ganzzahliges) Optimierungsproblem in verwandtes (reelles) Problem transferiert wird, welches in polynomialer Zeit gelöst werden kann.

Die Methode wurde von Agmon Shmuel 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, ohne dabei den Zielfunktionswert für jede zulässige Lösung zu verkleinern.

Literatur

Shmuel Agmon: The relaxation method for linear inequalities. In: Canadian Journal of Mathematics, Nr. 6, S. 382-392 (1954).


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Relaxierung — Relaxation bezeichnet die Entspannung nach einer Anspannung. Stabile physikalische Systeme kehren nach einer äußeren Störung über Relaxationsprozesse in ihren Grundzustand zurück. Als Relaxationszeit bezeichnet man eine Zeitkonstante, die für… …   Deutsch Wikipedia

  • Lagrange-Relaxierung — Visualisierung der Lagrange Multiplikatorenregel. Die rote Linie stellt die Menge dar, auf der g(x,y) = c erfüllt ist. Die blauen Linien sind Höhenlinien f(x,y …   Deutsch Wikipedia

  • Diskrete Optimierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Ganzzahlige Optimierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Ganzzahlige Programmierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Ganzzahlige lineare Programmierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Ganzzahlige lineare Optimierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Schnittebenenverfahren — Ein Schnittebenenverfahren (engl. cutting plane algorithm) ist in der angewandten Mathematik ein Algorithmus zur Lösung ganzzahliger linearer Optimierungsprobleme. Die Grundidee besteht darin, statt eines ganzzahligen linearen Programms seine LP… …   Deutsch Wikipedia

  • Neuromuskuläres Monitoring — handelsübliches Relaxometer handelsübliches Relaxometer Als Relaxometrie oder Neuromuskuläres Monitoring (NMM) bezeichnet man die Überwachung der neuromuskulären Reizübertragung an der motorische …   Deutsch Wikipedia

  • Relaxometer — handelsübliches Relaxometer handelsübliches Relaxometer Als Relaxometrie oder Neuromuskuläres Monitoring (NMM) bezeichnet man die Überwachung der neuromuskulären Reizübertragung an der motorisc …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”