LP-Relaxation

LP-Relaxation

Als LP-Relaxation (abgeleitet von Lineare Programmierung) wird bezeichnet, wenn bei einem Problem der ganzzahligen linearen Optimierung die Forderung der Ganzzahligkeit aufgegeben wird.

So ersetzt man z.B. Nebenbedingungen der Gestalt

x_i\in\{0,1\}

des originalen ganzzahligen Optimierungsproblems durch die relaxierten Nebenbedingungen

0 \le x_i \le 1..

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.

Beispiel

Ein ausführliches und illustratives Beispiel mit Skizze wird im Artikel Ganzzahlige Optimierung angegeben.

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:

  • RELAXATION — RELAXATI Détente psychosomatique contrôlée. Déjà en latin relaxatio signifiait relâchement d’un prisonnier et détente, repos. Le vieux français garda les deux sens, faisant de relaxation un doublet un peu pédant de relâchement (H. de Mondeville,… …   Encyclopédie Universelle

  • Relaxation time — is a general concept in physics for the characteristic time in which a system changes to an equilibrium condition from a non equilibrium condition. It can measure the time dependent response of a system to well defined external stimuli.… …   Wikipedia

  • Relaxation — may refer to: *Human relaxation is the art and science of doing nothing regardless of the outer activity including physical and/or mental tension. A human condition of flowing vital energy binging about a state of improved health and well being.… …   Wikipedia

  • Relaxation Dynamique — Sommaire 1 Relaxation dynamique 1.1 Principales équations utilisées 1.2 Étape de l itération 1.3 Amortissement …   Wikipédia en Français

  • Relaxation (Naturwissenschaft) — Relaxation bezeichnet im naturwissenschaftlichen Bereich den Übergang eines Systems über Relaxationsprozesse in seinen Grundzustand oder in einen Gleichgewichtszustand (häufig nach einer Anregung oder einer äußeren Störung). Die Relaxationszeit… …   Deutsch Wikipedia

  • Relaxation — Re lax*a tion (r? l?ks ? sh?n;277), n. [L. relaxatio; cf. F. relaxation.] 1. The act or process of relaxing, or the state of being relaxed; as, relaxation of the muscles; relaxation of a law. [1913 Webster] 2. Remission from attention and effort; …   The Collaborative International Dictionary of English

  • Relaxation — (zum Teil synonym auch Relaxierung) bezeichnet in den Naturwissenschaften (insbesondere in Physik, Chemie, Materialwissenschaften) den Übergang eines Systems in seinen Grundzustand oder in einen Gleichgewichtszustand (häufig nach einer Anregung) …   Deutsch Wikipedia

  • Relaxation dielectrique — Relaxation diélectrique Dans un semiconducteur, le temps de relaxation diélectrique mesure le temps nécessaire au rétablissement de la neutralité électrique. Pour un matériau de conductivité σ, la loi d Ohm donne la valeur du courant électrique… …   Wikipédia en Français

  • Relaxation — (Таланг,Таиланд) Категория отеля: 2 звездочный отель Адрес: 92/2 Moo 2 T. Srisoonthorn, A …   Каталог отелей

  • relaxation — Relaxation. s. f. Terme de Droit Canon, qui n a guere d usage que dans cette phrase. Relaxation des peines Canoniques, qui signifie Diminution, ou entiere remission des peines Canoniques. On appelle, Relaxation de nerfs, La foiblesse qui survient …   Dictionnaire de l'Académie française

  • Relaxation labelling — is an image treatment methodology. Its goal is to associate a label to the pixels of a given numerized image.The method relies on the fact that pixels which should be labelled in the same way tend to be near each other. Thus when a pixel is… …   Wikipedia

Share the article and excerpts

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