Benutzer:Chi-Vinh/Testgelände/Lineare Algebra Sätze

Lineare Programmierung

Lineare Ugleichungssysteme

Wie man eine Textaufgabe in ein Lineares Ungleichungssystem notiert ?

Ein allgemeines Rezept kann ich nicht angeben. Ich kann aber einige Tipps zusammenstellen, um die Textaufgabe zu formalisieren.

1. Veranschauliche das Problem durch eine Skizze

1. Benenne die gesuchten Grössen mit Namen ( z.B. Transportmengen auf den Wegen 1...n )

1. Benenne die Grössen mit Variablen

1. Benenne die zu optimierende Größe ( z.B. Transportkosten )

1. Liste die Einschränkungen auf

1. Entscheide Dich für die Entscheidungsvariablen

Entscheidungsvariablen beeinflussen die zu optimierende Grösse

1. Verstaue alle Informationen in eine Tabelle

1. Überprüfe die Nichtnegativität

1. Aufstellung der Zielfunktion

1. Schreibe die Einschränkungen auf mit " $\leq$ " oder " >= "

Fragen beantworten, wie eine der gesuchten Grössen auf eine Einschränkung wirkt. Diese Aussage wird dann verallgemeinert.

Beispiel

Hier Beispielname einsetzen /Beispiel

Auf einem Weg der Länge 20 Meilen bewirkt jede Fahrt eine Vergrösserung der gesamten Fahrtstrecke um 20 Meilen. Also aus

• x_1 = 1 folgt: Fahrstrecke b = 1 \cross 20 Meilen
• x_2 = 2 folgt: Fahrtstrecke b = 2 \* 20 Meilen

Verallgemeinerung: also aus x_1 folgt: Fahrstrecke b = x_1 \ 20 Meilen

Analog folgert man für einen Weg der Länge 50 Meilen und der Anzahl der Fahrten x_2 : b = x_2 * 50 Meilen 20x_1 + 50x_2+... = b

Linearen Gleichungen eines linearen Ungleichungssystems (U) werden in einem Gleichungssystem (G) zusammengefasst.

a) Hat (G) keine Lösung, dann ist auch (U) unlösbar.

b) Hat (G) Lösungen, so benutzt man sie, um in (U) möglichst viele Unbestimmte zu eliminieren. Nach der Elimination soll eine nichtnegative in der Variablenzahl reduzierte Gleichung entstehen. Sonst verletzt ein negativer Koeffizient die Nichtnegativität. Die Gleichung ist dann als Ungleichung mit dem "≥" zu formulieren. Die Formulierung mit ">" verletzt die Nichtnegativität.

c)

Das hierdurch entstandene lineare Ungleichungssystem enthält nur lineare Ungleichungen. Durch eventuelle Multiplikationen mit −1 können sie alle gleichsinning “≥“ gemacht werden.

d) Man kann dieses gleichsinnige lineare Ungleichungssystem als Matrixungleichung

(N) A · x ≥ b

schreiben, wobei die m×n - Matrix A die Koeffizientenmatrix, x = ( $x_{1},...,x_{n}$ )

der Unbestimmtenvektor und b = ($b_{1},...,b_{m}$) ∈ $F^{m}$ der Konstantenvektor ist. Das lineare Ungleichungssystem (N) bezeichnet man als die Normalform von (U).

Die Normalform ist verletzt, wenn statt "≥" irgendwo ">" steht. Es wird auch gesagt die Nichtnegativitätsbedingung ist verletzt ! Was kann man dagegen tun ? Jede Ungleichung ist in Gleichungen zu überführen, indem man die Gleichheit mit Schlupfvariablen herstellt. Die Nichtnegativitätsbedingung gibt auch den Hinweis, welche Startwerte man einen eventuellen Algortihmus setzen soll.

Lemma: Folgerung aus der Nichtnegativität

Da alle Variablen nichtnegativ sein, sollen können überall 0 als Startwert angenommen werden. Dann ist auch der Startwert für die Zielvariable 0. Wenn durch die elementaren Umformungen des Gaußschen Algorithmus die Variablen vergrössert werden, heißt das mit der Nichtnegativitätsfunktion auch eine wachsende Zielvariable.

Das Maximum-Problem

Bei einem linearen Programm (LP) sind eine Matrix $A\in \mathbb {R} ^{m,n}$ und zwei Vektoren $b\in \mathbb {R} ^{m}$ und $c\in \mathbb {R} ^{n}$ gegeben. Eine zulässige Lösung ist ein Vektor $x\in \mathbb {R} ^{n}$ mit nichtnegativen Einträgen, der die linearen Bedingungen

${\begin{matrix}a_{11}x_{1}&+\ldots &+a_{1n}x_{n}&\leq b_{1}\\a_{21}x_{1}&+\ldots &+a_{2n}x_{n}&\leq b_{2}\\\vdots &\vdots &\vdots &\vdots \\a_{m1}x_{1}&+\ldots &+a_{mn}x_{n}&\leq b_{m}\end{matrix}}$

erfüllt. Ziel ist es, unter allen zulässigen Vektoren $x$ einen zu finden, der das Skalarprodukt

$c^{T}x=c_{1}x_{1}+\ldots +c_{n}x_{n}$

maximiert. Dieses Optimierungsproblem in der sogenannten Standardform wird oft abkürzend als

$\max\{c^{T}x\;|\;Ax\leq b,x\geq 0\}$

geschrieben, wobei die Bedingungen $Ax\leq b$ und $x\geq 0$ komponentenweise zu verstehen sind.

Beispiel

Produktionsplanung /Beispiel

Beispiel aus der Produktionsplanung (zweidimensional)

Eine Firma stellt zwei verschiedene Produkte her, für deren Fertigung drei Maschinen A, B, C zur Verfügung stehen. Diese Maschinen haben eine maximale monatliche Laufzeit (Kapazität) von 170 Stunden (A), 150 Stunden (B) bzw. 180 Stunden (C). Eine Mengeneinheit (ME) von Produkt 1 liefert einen Deckungsbeitrag von 300 Euro, eine ME von Produkt 2 dagegen 500 Euro. Fertigt man eine ME von Produkt 1, dann benötigt man dafür eine Stunde die Maschine A und eine Stunde die Maschine B. Eine Einheit von Produkt 2 belegt zwei Stunden lang Maschine A, eine Stunde Maschine B und drei Stunden Maschine C. Ziel ist es, Produktionsmengen zu bestimmen, die den Deckungsbeitrag der Firma maximieren, ohne die Maschinenkapazitäten zu überschreiten. Fixkosten können in dem Optimierungsproblem ignoriert und anschließend dazuaddiert werden, da sie per Definition unabhängig von den zu bestimmenden Produktionsmengen sind.

Mathematische Modellierung

Veranschaulichung des Beispiels (Erklärung siehe Text)

Angenommen, der Betrieb fertigt pro Monat $x_{1}$ ME von Produkt 1 und $x_{2}$ ME von Produkt 2. Dann beträgt der Gesamtdeckungsbeitrag

$G(x_{1},x_{2})=300x_{1}+500x_{2}.$

Diesen Wert möchte die Firma maximieren. Da die Maschinenkapazitäten eingehalten werden müssen, ergeben sich die Nebenbedingungen:

${\begin{alignedat}{3}x_{1}&+&2x_{2}&\leq 170&&{\text{ (Maschine A, rechts in schwarz eingezeichnet)}}\\x_{1}&+&x_{2}&\leq 150&&{\text{ (Maschine B, rechts in tuerkis eingezeichnet)}}\\&&3x_{2}&\leq 180&&{\text{ (Maschine C, rechts in violett eingezeichnet)}}\end{alignedat}}$

Da außerdem keine negativen Produktionsmengen möglich sind, muss $x_{1},x_{2}\geq 0$ gelten (Nichtnegativitätsbedingung).

Aufgabe

Landwirtschaftlicher Betrieb /Aufgabe

Schreiben Sie das Lineare Ungleichungssystem (LGS) in der Normalform an !Stichworte: Schlupfvariablen, Umkehrung des Ungleichheitszeichen

In einem landwirtschaftlichen Betrieb werden Kühe und Schafe gehalten. Für 50 Kühe und 200 Schafe sind Ställe vorhanden. Der Betrieb verfügt über 72 Morgen Weideland. Für eine Kuh wird ein Morgen und für ein Schaf wird 0, 2 Morgen benötigt. Auf eine Kuh entfallen jährlich bis zu 150 Arbeitsstunden, auf ein Schaf 25 Arbeitsstunden. Zur Versorgung des Viehs stehen jährlich 10.000 Arbeitsstunden zur Verf¨ugung. Der jährliche Reingewinn beträgt 250 Euro pro Kuh und 45 Euro pro Schaf. Die Anzahlen x 1 und x 2 der gehaltenen Kühe bzw. Schafe sind so zu bestimmen, dass der Gesamtgewinn möglichst groß wird.

Es liegt ökonomisch nahe, zu versuchen, die Resourcen “Arbeitskraft“ und “Weideland“ voll auszunutzen. D.h. die Einschränkungen für die Resourcen “Arbeitskraft“ und “Weideland“ sollten eine eindeutige Lösung haben behandelt als Gleichungsystem. Man erhält also ein System aus Gleichungen ung Ungleichungen.

Aufgabe

Hier Aufgabenname einsetzen /Aufgabe

Warum ist die Lösung des Gleichungssystem korrespondierend mit den zu maximierenden Ressourcen gleichzeitg auch die Lösung des gesamten Ungleichungssystem ?

Aufgabe

Verständnisfrage:Normalform /Aufgabe

Was tut man, wenn das LGS nicht gleichsinnig ist, nur strenge Ungleichheit gilt, das Gleichheitszeichen fehlt ?Stichworte: Schlupfvariablen, Nichtnegativitätsbedingungen

Geometrische Interpretation als Polyeder

Im nebenstehenden Bild sind die Ungleichungen aus dem obigen Beispiel als türkise, schwarze und violette Beschränkungen eingezeichnet. Zusammen definieren sie das (blau umrandete) Polyeder der zulässigen Punkte. Die rotgestrichelten Linien stellen Iso-Gewinnfunktionen dar, d. h. alle Punkte auf einer solchen Linie haben denselben Zielfunktionswert. Da die Firma möglichst viel produzieren will, ist das Ziel der Optimierung, solch eine rot gestrichelte Linie soweit nach rechts oben zu schieben, so dass sie gerade noch das Polyeder berührt. Alle Berührungspunkte sind dann optimal. In diesem Fall ist der Punkt (130,20) die eindeutige optimale Ecke, und der optimale Zielfunktionswert beträgt 49.000 Euro.

Im allgemeinen ist die Optimallösung eines linearen Optimierungsproblems allerdings weder eindeutig noch ganzzahlig. Wenn beispielsweise beide Produkte den gleichen Deckungsbeitrag hätten, wären die roten Iso-Gewinnfunktionen parallel zur Ungleichung $x_{1}+x_{2}\leq 150$. In diesem Fall wäre jeder Punkt auf der Strecke zwischen (130,20) und (150,0) optimal, es gäbe also unendliche viele Optimallösungen.

FAQ: Wie erkennt man die Unlösbarkeit eines LP-Problems ?

 How do I diagnose an infeasible LP model?

A linear program is infeasible if there exists no solution that satisfies all of the constraints -- in other words, if no feasible solution can be constructed. Since any real operation that you are modeling must remain within the constraints of reality, infeasibility most often indicates an error of some kind. Simplex-based LP software efficiently detects when no feasible solution is possible; some early interior-point codes could not detect an infeasible situation as reliably, but remedies for this flaw have been introduced.

The source of infeasibility is often difficult to track down. It may stem from an error in specifying some of the constraints in your model, or from some wrong numbers in your data. It can be the result of a combination of factors, such as the demands at some customers being too high relative to the supplies at some warehouses.

Upon detecting infeasibility, LP codes typically show you the most recent infeasible solution that they have encountered. Sometimes this solution provides a good clue as to the source of infeasibility. If it fails to satisfy certain capacity constraints, for example, then you would do well to check whether the capacity is sufficient to meet the demand; perhaps a demand number has been mistyped, or an incorrect expression for the capacity has been used in the capacity constraint, or or the model simply lacks any provision for coping with increasing demands. More often, unfortunately, LP codes respond to an infeasible problem by returning a meaninglessly infeasible solution, such as one that violates material balances.

A more useful approach is to forestall meaningless infeasibilities by explicitly modeling those sources of infeasibility that you view as realistic. As a simple example, you could add a new "slack" variable on each capacity constraint, having a very high penalty cost. Then infeasibilities in your capacities would be signalled by positive values for these slacks at the optimal solution, rather than by a mysterious lack of feasibility in the linear program as a whole. Many modelers recommend the use of "soft constraints" of this kind in all models, since in reality many so-called constraints can be violated for a sufficiently high price. Modeling approaches that use such constraints have a number of names, most notably "goal programming" and "elastic programming".

I want to know the specific constraints that contradict each other

There can be many ways to answer this question, some of them potentially harder than solving the underlying LP would be (if it were feasible). One useful appoach is to apply auxiliary algorithms that look for small groups of constraints that can be considered to "cause" the infeasibility of the LP.

Several codes include methods for finding an "irreducible infeasible subset" (IIS) of constraints that has no feasible solution, but that becomes feasible if any one constraint is removed. John Chinneck has developed MINOS(IIS), an extended version of the MINOS package that finds an IIS when the constraints have no feasible solution; a demonstration copy is available for downloading. There are also IIS finders in CPLEX, LINDO, OSL, and Xpress-MP, as well as Premium Solver Platform for Excel.

Methods also exist for finding an "IIS cover" that has at least one constraint in every IIS. A minimal IIS cover is the smallest subset of constraints whose removal makes the linear program feasible. Further details and references for a variety of IIS topics are available in papers by John Chinneck.

The software system ANALYZE carries out various other analyses to detect structures typically associated with infeasibility. (A bibliography on optimization modeling systems collected by Harvey Greenberg of the University of Colorado at Denver contains cross-references to over 100 papers on the subject of model analysis.)

I just want to know whether or not a feasible solution exists

From the standpoint of computational complexity, finding out if an LP model has a feasible solution is essentially as hard as actually finding the optimal LP solution, within a factor of 2 on average, in terms of effort in the Simplex Method; plug your problem into a normal LP solver with any objective function you like, such as c=0. For MIP models, it's also difficult - if there exists no feasible solution, then you must go through the entire Branch and Bound procedure (or whatever algorithm you use) to prove this. There are no shortcuts in general, unless you know something useful about your model's structure (e.g., if you are solving some form of a transportation problem, you may be able to assure feasibility by checking that the sources add up to at least as great a number as the sum of the destinations).

Gegenstand des Satzes: Lineares Ungleichungssystem =

Sei A·x ≥ b ein lineares Ungleichungssystem mit Zielfunktion γ  : $F^{n}$ → F .

Prämisse: Existenz von zwei optimalen Lösungen

Besitzt A · x ≥ b bzgl. γ wenigstens zwei optimale Lösungen

Behauptung: Existenz unendlich vieler optimaler Lösungen

So existieren unendlich viele optimale Lösungen von A · x ≥ b bzgl. γ.

Satz 11.5:

Gegenstand des Satzes

Sei A eine m×n - Matrix und A·x ≥ b ein lösbares lineares Ungleichungssystem. Die Zielfunktion sei γ(x) = $g_{0}$ + $g_{1}$ · $x_{1}$ + ... + $g_{n}$ · $x_{n}$ , wobei x = ($x_{1}$ , ..., $x_{n}$ ) ist.

Prämisse, Eigenschaft

Wenn ein w ∈ F n existiert mit γ(w) > $g_{0}$ und A · w ≥ 0

Behauptung: γ auf Lösungsmenge L:= { alle x | A · x ≥ b }

Dann ist γ auf der Lösungsmenge L von A · x ≥ b unbeschrännkt.

Satz 11.6:

Gegenstand:

Sei L die Lösungsmenge des linearen Ungleichungssystems A · x ≥ b mit b = $(b_{1},...,b_{m})$ ∈ $F^{m}$ und seien $z_{i}$ , 1 ≤ i ≤ m die Zeilenvektoren der m × n - Matrix.

A. Die Zielfunktion sei γ(x) = $g_{0}$+ g · x, mit g = ($g_{1}$ , ..., $g_{n}$ ) ∈ $F^{n}$ , x = ($x_{1},...,x_{n}$ ) und g 0 ∈ F .

Prämisse:

Angenommen es gibt eine Teilmenge T der Ziffern {1, 2, ..., m} derart, dass die folgenden drei Bedingungen erfüllt sind:

• a) {$z_{t}$ | t ∈ T } ist eine Basis des Zeilenraumes von A.
• b) Es gibt ein v ∈ L mit $z_{t}$ · v = $b_{t}$ für alle t ∈ T .
• c) g = P t∈T h t · z t ist eine Linearkombination der Zeilenvektoren z t von A, t ∈ T , mit Koeffizienten h t ≤ 0.

Behautptung:

Dann gelten die folgenden Aussagen:

• (1) Das lineare Gleichungssystem

(G) $z_{t}$ · x = $b_{t}$ , t ∈ T ist lösbar.

• (2) Jede Lösung v ∈ F n von (G) ist eine optimale Lösung von A · x ≥ b bzgl. γ.

Eckenfindung

Satz 12.3:

Die folgenden elementaren Spaltenumformungen einer (m + 1) × (n + 1) - Matrix C mit den Spaltenvektoren $s_{1},...,s_{n+1}$ sind zulässig:

• 1) Vertauschung der Spaltenvektoren s i und s j , mit 1 ≤ i, j ≤ n.
• 2) Multiplikation der i - ten Spalte mit einem 0 6= λ ∈ F , wobei 1 ≤ i ≤ n ist.
• 3) Ersetzung der i - ten Spalte durch die Summe s i +λ·s j f¨ur ein λ ∈ F , wobei i 6= j und j ≤ n ist (es darf i = n + 1 sein).

Satz 12.4:

Sei u eine Lösung des linearen Ungleichungssystems A · x ≥ b mit m × n - Koeffizientenmatrix A. Sei γ(x) = $g_{0}$ + g · x die Gewinnfunktion und B = A k g G ! die zu u gehörige Ausgangsmatrix. Sei C eine Matrix, welche aus B durch zulässige Spaltenumformungen hervorgeht. Wenn C einen Spaltenvektor s j mit j ≤ n hat, dessen Komponenten alle das gleiche Vorzeichen haben und dessen letzte Komponente von Null verschieden ist

dann gelten folgende Aussagen:

• a) Es gibt ein w ∈ Fn mit γ(w) > $g_{0}$ und A · w ≥ 0
• b) γ ist auf der Lösungsmenge L von A · x ≥ b nach oben unbeschränkt.

Sei C eine (m + 1) × (n + 1) - Matrix mit den Zeilenvektoren $z_{1},...,z_{m}+1$ . Eine Teilmenge T von {1, . . . , m + 1} heißt Eckmenge von C, wenn die folgenden Bedingungen erfüllt sind:

• • a) Die Zeilenvektoren $z_{t}$ , t ∈ T , sind voneinander verschiedene Einheitsvektoren.
  • b) $z_{t}$ 6= $e_{n+1}$ für alle t ∈ T .
  • c) Wenn j ≤ n und die j-te Spalte 6= 0 ist, dann ist $z_{t}$ = $e_{j}$ für ein t ∈ T .

Satz 12.5:

Sei u eine Lösung des linearen Ungleichungssystems (U) A · x ≥ b mit m × n - Koeffizientenmatrix A. Sei γ(x) = $g_{0}$ + g · x die Gewinnfunktion und B = A k g G ! die zu u gehörige Ausgangsmatrix. Sei C eine Matrix, welche aus B durch zulässige Spaltenumformungen hervorgeht und die folgenden Eigenschaften hat:

• 1) Die Kontrollspalte von C ist ≥ 0.
• 2) Die Gewinnzeile von C ist ≤ 0.
• 3) C hat eine Eckmenge T .

Dann gilt:

• a) T erfüllt die Bedingungen von Satz 11.6.
• b) Sind $z_{i}$ , 1 ≤ i ≤ m, die Zeilen von A, dann ist das Gleichungssystem

(L) $z_{t}$ · x = $b_{t}$ , t ∈ T, x = ($x_{1},...,x_{n}$ )

lösbar, und jede Lösung v ∈ Fn des Gleichungssystems (L) ist eine optimale Lösung von (U) mit Gewinn γ(v) gleich dem Gewinn G ∗ von C.

Eckenfindungs-Algorithmus

Sei B eine (m + 1) × (n + 1)− Matrix mit Gewinnzeile g = (g 1 , . . . , g n ) und Kontrollspalte k = ($k_{1}$ , . . . , $k_{n}$ ) ≥ 0. Wir setzen zunächst h = 1.

1. (Maximumkriterium) Wähle einen Spaltenindex j mit h ≤ j ≤ n derart, dass s j 6= 0 und |g j | möglichst groß sind. Wenn ein solches j nicht existiert, dann endet der Algorithmus. Wenn es mehrere Möglichkeiten zur Wahl von j gibt, wählt man daraus das kleinste j.

2. (Quotientenkriterium) Ist $s_{j}$ = ($b_{1}j$ , . . . , $b_{m}j$ , $g_{j}$ ) die im ersten Schritt gewählte Spalte, dann ist die relevante Zeilenindexmenge R = {i | $b_{i}j$ 6= 0 und $b_{i}j$ · $g_{j}$ ≤ 0}.

• (a) Wenn R = ∅ , dann bricht der Algorithmus ab (unbeschränkter Fall).
• (b) Wenn R 6= ∅ , wähle einen Zeilenindex i ∈ R mit ki |bij | ≤ kr |brj | für alle r ∈ R. Gibt es daf¨ur mehrere Möglichkeiten, so w¨ahlt man i minimal unter diesen.

• 3. Ersetze B durch die Matrix, welche aus B durch Spaltenpivotierung an der Stelle (i, j) entsteht.

• 4. Wenn j 6= h , ersetze B durch die Matrix, welche aus B durch Vertauschung der j-ten und der h-ten Spalte entsteht.

• 5. Ersetze h durch h + 1.

Wiederhole die Schritte 1 bis 5 so lange, bis der Algorithmus endet.

Satz 12.7

Wendet man den Eckenfindungs-Algorithmus auf eine (m + 1) × (n + 1) - Matrix B mit Kontrollspalte k ≥ 0 an, dann gelten folgende Aussagen:

• a) Im Eckenfindungsalgorithmus werden nur zulässige Spaltenumformungen vorgenommen.
• b) Der Eckenfindungs-Algorithmus endet nach spätestens 5 · n Schritten. Darüber hinaus hat die Endmatrix $B^{*}$ die folgenden Eigenschaften:

c) Die Kontrollspalte von $B^{*}$ ist ≥ 0.

d) Der Gewinn von $B^{*}$ ist mindestens so groß wie der Gewinn von B.

e) Wenn der Eckenfindungs-Algorithmus beim Maximumkriterium endet, dann hat $B^{*}$ eine Eckmenge, nämlich die Menge der Pivotzeilen.

f) Wenn der Eckenfindungs-Algorithmus beim Quotientenkriterium abbricht, dann hat $B*$ eine Spalte $s_{j}$ mit j ≤ n, deren Komponenten alle das gleiche Vorzeichen haben und deren letzte Komponente von Null verschieden ist.

Eckentausch

Gegenstand

Sei B (m + 1) × (n + 1) - Matrix mit Gewinnzeile g, Kontrollspalte k ≥ 0 und Eckmenge T .

Prämisse, Eigenschaft

Sei C eine Matrix, die aus B durch Anwendung des EckenaustauschAlgorithmus hervorgeht.

Behauptung

Dann gelten die folgenden Aussagen:

a) Beim Eckenaustausch-Algorithmus werden nur zulässige Spaltenumformungen vorgenommen.

b) Die Kontrollspalte von C ist ≥ 0.

c) Der Gewinn von C ist mindestens so groß wie der Gewinn von B .

d) C hat eine Eckmenge.

e) Wenn der Eckenaustausch-Algorithmus mit C bei Anwendung des Maximumkriteriums endet, dann erfüllt C alle Bedingungen von Satz 12.5.

f) Wenn der Eckenaustausch-Algorithmus mit C bei Anwendung des Quotientenkriteriums endet, dann erfüllt C alle Bedingungen von Satz 12.4.

What references are there in this field?

What follows is an idiosyncratic list, based on my own preferences, various people's recommendations on the net, and recent announcements of new publications. It is divided into the following categories: General reference, Textbooks, Presentations of LP modeling systems, Books containing source code, Additional books, Periodicals, and Articles of interest. See also the listings of [#Q8 online sources of information] following.

I have not reviewed everything listed.

General reference

• Nemhauser, Rinnooy Kan, and Todd, eds, Optimization: Handbooks in Operations Research and Management Science, Volume 1, North-Holland, 1989. (Very broad-reaching, with large bibliography; a good reference, and worth checking first. Expensive, though, and tough reading for beginners.)

Textbooks

Regarding the common question of the choice of textbook for a college LP course, it's difficult to give a blanket answer because of the variety of topics that can be emphasized: brief overview of algorithms, deeper study of algorithms, theorems and proofs, complexity theory, efficient linear algebra, modeling techniques, solution analysis, and so on. A small and unscientific poll of ORCS-L mailing list readers in 1993 uncovered a consensus that #Chvatal Chvatal was in most ways pretty good, at least for an algorithmically oriented class; of course, some new candidate texts have been published in the meantime. For a class in modeling, a book about a commercial code would be useful (LINDO, AMPL, GAMS were suggested), especially if the students are going to use such a code; and many are fond of [#Williams [Williams]], which presents a considerable variety of modeling examples.

• Bazaraa, Jarvis and Sherali. Linear Programming and Network Flows. Grad level.
• Bertsimas, Dimitris and Tsitsiklis, John, Introduction to Linear Optimization. Athena Scientific, 1997 (ISBN 1-886529-19-1 <a href="javascript:Pick it!ISBN: 1-886529-19-1"><img style="border: 0px none ;" src="http://www.citavi.com/softlink?linkid=FindIt" alt="Pick It!" title='Titel anhand dieser ISBN in Citavi-Projekt übernehmen'></a> ). Graduate-level text on linear programming, network flows, and discrete optimization.
• Bisschop, J.J., Optimization Modeling.
• Chvatal, Linear Programming, Freeman, 1983. Undergrad or grad.
• Cook, W.J., Cunningham, W.H., Pulleyblank, W.R. and Schrijver, A. Combinatorial Optimization, Wiley Interscience, 1997.
• Daellenbach, Hans G., A User's Guide to Linear Programming. Good for engineers. Currently out of print.
• Fang, S.-C. and Puthenpura, S., Linear Optimization and Extensions: Theory and Algorithms. Prentice Hall, 1993.
• Dantzig, George B., Linear Programming and Extensions, Princeton University Press, 1963.. The most widely cited early textbook in the field.
• Dantzig, George B. and Thapa, Mukund N., Linear Programming 1: Introduction, Springer Verlag, 1997..
• Gass, Saul I., Linear Programming: Methods and Applications, 5th edition. International Thomson Publishing, 1985.. The author received the 1997 INFORMS Expository Writing Award.
• Ignizio, J.P. � Cavalier, T.M., Linear Programming, Prentice Hall, 1994. Covers usual LP topics, plus interior point, multi-objective and heuristic techniques.
• Luenberger, Introduction to Linear and Nonlinear Programming, Addison Wesley, 1984. Updated version of an old standby. The author received the 1999 INFORMS Expository Writing Award.
• Murtagh, B., Advanced Linear Programming: Computation and Practice. McGraw-Hill, 1981. Good one after you've read an introductory text. Currently out of print.
• Murty, K., Linear and Combinatorial Programming.
• Nash, S., and Sofer, A., Linear and Nonlinear Programming, McGraw-Hill, 1996.
• Nazareth, J.L., Computer Solution of Linear Programs, Oxford University Press, New York and Oxford, 1987.
• Nemhauser, G.L. and Wolsey, L.A., Integer and Combinatorial Optimization, Wiley Interscience, 1988. An advanced text that covers many theortical and computational topics.
• Nering, E.D. � Tucker, A.W., Linear Programs and Related Problems, Academic Press, 1993.
• Roos, Terlaky and Vial, Theory and Algorithms for Linear Optimization: An Interior Point Approach. John Wiley, Chichester, 1997
• Saigal, R., Linear Programming: A Modern Integrated Analysis, Kluwer Academic Publishers, 1995.
• Schrijver, A., Theory of Linear and Integer Programming, Wiley, 1986. Advanced.
• Taha, H., Operations Research: An Introduction, 1987.
• Thie, P.R., An Introduction to Linear Programming and Game Theory, Wiley, 1988.
• Vanderbei, Robert J., Linear Programming: Foundations and Extensions. Kluwer Academic Publishers, 1996. Balanced coverage of simplex and interior-point methods. Source code available on-line for all algorithms presented.
• Williams, H.P., Model Building in Mathematical Programming, Wiley 1993, 3rd edition. Little on algorithms, but excellent for learning what makes a good model.
• Wright, Stephen J., Primal-Dual Interior-Point Methods. SIAM Publications, 1997. Covers theoretical, practical and computational aspects of the most important and useful class of interior-point algorithms. The web page for this book contains current information on interior-point codes for linear programming, including links to their websites.
• Ye, Yinyu, Interior Point Algorithms: Theory and Analysis. Wiley, 1997.

Presentations of LP modeling systems (usable as texts for some classes)

Free software for problems of limited size is available to accompany most of these books. See the associated software websites for details.

• Bisschop and Roelofs, AIMMS Language Reference and AIMMS User's Guide, Paragon Decision Technology, 1999.
• Brooke, Kendrick � Meeraus, GAMS: A Users' Guide, The Scientific Press/Duxbury Press, 1988.
• Fourer, Gay � Kernighan, AMPL: A Modeling Language for Mathematical Programming (2nd edition), Duxbury Press, 2002.
• Greenberg, H.J., Modeling by Object-Driven Linear Elemental Relations: A User's Guide for MODLER, Kluwer Academic Publishers, 1993.
• Guéret, C., Prins, C. and Sevaux, M., Applications of Optimization with Xpress-MP (translated and revised by Susanne Heipcke), Dash Optimization, 2002.
• Schrage, L., Optimization Modeling with LINDO, 5th edition, and Optimization Modeling with LINGO, LINDO Systems.

Books containing source code

• Best and Ritter, Linear Programming: active set analysis and computer programs, Prentice-Hall, 1985.
• Bertsekas, D.P., Linear Network Optimization: Algorithms and Codes, MIT Press, 1991.
• Bunday and Garside, Linear Programming in Pascal, Edward Arnold Publishers, 1987.
• Bunday, Linear Programming in Basic (presumably the same publisher).
• Burkard and Derigs, Springer Verlag Lecture Notes in Math Systems #184 (the Assignment Problem and others).
• Kennington � Helgason, Algorithms for Network Programming, Wiley, 1980. (A special case of LP; contains Fortran source code.)
• Lau, H.T., A Numerical Library in C for Scientists and Engineers, 1994, CRC Press. (Contains a section on optimization.)
• Martello and Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990. (Contains Fortran code, comes with a disk - also covers Assignment Problem.)
• Press, Flannery, Teukolsky � Vetterling, Numerical Recipes, Cambridge, 1986. (Comment: use their LP code with care.)
• Syslo, Deo � Kowalik, Discrete Optimization Algorithms with Pascal Programs, Prentice-Hall (1983). (Contains code for 28 algorithms such as Revised Simplex, MIP, networks.)

Additional books

• Ahuja, Magnanti and Orlin, Network Flows, Prentice Hall, 1993.
• Beasley, ed., Advances in Linear and Integer Programming. Oxford University Press, 1996. Each chapter is a self-contained essay on one aspect of the subject.
• Bertsekas, Network Optimization: Continuous and Discrete Models, Athena Scientific, 1998.
• Chandru and Hooker, Optimization Methods for Logical Inference, Wiley-Interscience, 1999.
• Edelsbrunner, Algorithms in Combinatorial Geometry, Springer Verlag, 1987.
• Forsythe, Malcolm � Moler, Computer Methods for Mathematical Computations, Prentice-Hall.
• Gill, Murray and Wright, Numerical Linear Algebra and Optimization, Addison-Wesley, 1991.
• Greenberg, A Computer-Assisted Analysis System for Mathematical Programming Models and Solutions: A User's Guide for ANALYZE, Kluwer Academic Publishers, 1993.
• Hooker, Logic-Based Methods for Optimization, Wiley-Interscience, 2000.
• Hwang and Yoon, Multiple Attribute Decision Making: An Introduction, Sage, 1995.
• Lawler, Lenstra, Rinnooy Kan and Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, 1985.
• Moré and Wright, Optimization Software Guide, SIAM Publications, 1993. See also the NEOS Guide to Optimization Software.
• Murty, Network Programming, Prentice Hall, 1992.
• Papadimitriou and Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover, 1998. Also contains a discussion of complexity of simplex method.
• Reeves, ed., Modern Heuristic Techniques for Combinatorial Problems, Halsted Press (Wiley), 1993. Contains chapters on tabu search, simulated annealing, genetic algorithms, neural nets, and Lagrangian relaxation.
• Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications, Springer-Verlag, 1994.
• Rockafellar, Network Flows and Monotropic Optimization, Athena Scientific, 1984, reprinted 1998.

Periodicals

• Publications of INFORMS, the principal operations research and management science society in the United States:
  • OR/MS Today, the bimonthly newsletter of INFORMS, includes case studies, software reviews, and software surveys relevant to linear programming. It also has the most extensive collection of advertisements for commercial linear programming (and other optimization) software packages.
  • Interfaces frequently publishes interesting accounts of applications that make use of linear programming.
  • INFORMS Journal on Computing includes some articles on the computational aspects of linear programming algorithms.
  • Interactive Transactions of OR/MS contains a number of useful surveys and bibliographies relevant to linear programming.
• Publications of the Mathematical Programming Society:
  • Mathematical Programming contains technical articles on theory and computation.
  • Optima, the Society's newsletter, incorporates survey articles and book reviews.
• Publications of SIAM, the principal applied mathematics society in the United States:
  • SIAM Journal on Optimization contains technical articles, mainly of a mathematical nature.
  • SIAG/OPT Newsletter, from the SIAM Activity Group on Optimization.
• Publisher-sponsored technical journals focusing on optimization topics:
  • Computational Optimization and Applications (and allied Software Forum)
  • Constraints
  • Journal of Optimization Theory and Applications
  • Optimization Methods and Software

Articles of interest

• Avis and Fukuda, "A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra", Discrete and Computational Geometry, 8 (1992), 295--313.
• Balas, E. and Martin, C., "Pivot And Complement: A Heuristic For 0-1 Programming Problems", Management Science, 1980, Vol 26, pp 86-96.
• Balinski, M.L., "An Algorithm for Finding all Vertices of Convex Polyhedral Sets", SIAM J. 9, 1, 1961.
• Carpaneto, Dell'amico and Toth, "A Branch-and-bound Algorithm for Large Scale Asymmetric Travelling Salesman Problems," ACM Transactions on Mathematical Software 21 (1995) 410-415.
• Haessler, "Selection and Design of Heuristic Procedures for Solving Roll Trim Problems," Management Science 12 (1988) 1460-1471.
• Lustig, Marsten and Shanno, "Interior Point Methods for Linear Programming: Computational State of the Art", ORSA Journal on Computing, Vol. 6, No. 1, Winter 1994, pp. 1-14. Followed by commentary articles, and a rejoinder by the authors.
• Marsten, Subramanian, Shanno, Saltzman and Lustig, "Interior point methods for linear programming: Just call Newton, Lagrange, and Fiacco and McCormick!" Interfaces, Vol. 20, No. 4 (1990) pp. 105-116.
• Mattheis and Rubin, "A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets", Mathematics of Operations Research, vol. 5 no. 2 1980, pp. 167-185.
• Seidel, "Constructing Higher-Dimensional Convex Hulls at Logarithmic Cost per Face", 1986, 18th ACM STOC, 404--413.
• Smale, Stephen, "On the Average Number of Steps in the Simplex Method of Linear Programming", Math Programming 27 (1983), 241-262.
• Swart, "Finding the Convex Hull Facet by Facet", Journal of Algorithms, 6 (1985), 17--48.
• P.E. Sweeney and E.R. Paternoster, "Cutting and Packing Problems: A Categorized, Application-Oriented Research Bibliography," Journal of the Operational Research Society 43 (1992) 691-706.
• Volgenant, A., Symmetric TSPs, European Journal of Operations Research, 49 (1990) 153-154.
• A special issue of Optimization Methods and Software (volumes 11-12, December 1999) is devoted to interior-point methods and includes a supplementary CD with related sofware.

What's available online in this field?

Though traditional publications may remain the best places to learn about optimization theory and algorithms, the Web is the place to go for optimization software. In addition to numerous sources of optimization codes and optimization-related home pages, the Web is increasingly a source of optimization services that let you try out solvers without having to install them on your own equipment.

On-line sources of optimization services

The following websites offer, in some sense, to run your linear or integer programming problem and return a result. Check their home pages for details, which vary considerably. (See also the analogous listing in the NLP FAQ.)

• AMPL. A convenient interface supports experimentation with the AMPL modeling language on test problems up to 300 variables and 300 constraints objectives. Users can request any example from the AMPL book, or provide their own model and data files. There is a choice among 8 solvers for linear and integer programming (as well as nonlinear optimization and complementarity problems).
• DecisionNet. Provides access to "a distributed collection of decision technologies," including linear programming, "that are made available for execution over the World Wide Web. These technologies are developed and maintained locally by their providers. DecisionNet contains technology metainformation necessary to guide consumers in search, selection, and execution of these technologies." Facilities for submitting problems in popular modeling language formats are currently being tested.
• GIDEN. An interactive graphical environment for a variety of network optimization problems and algorithms. It is written in Java, so you can try it out through any Java-enabled Web browser.
• Kestrel. This interface permits varied linear, integer, and nonlinear optimization problems to be sent directly from the AMPL and GAMS modeling systems to the NEOS Server. Results are sent back to AMPL or GAMS, where they may be displayed and analyzed just as if the solving had been done locally.
• LPL. Small problems modeled in the LPL language can be submitted by typing or pasting into a web form. Results are returned on a subsequent web page.
• MILP by Dmitry V. Golovashkin. Small-scale mixed-integer programs in a simple algebraic format are solved through a web form interface.
• Network-Enabled Optimization System (NEOS) Server. Offers access to several dozen solvers for linear and integer programming as well as various nonlinear optimization problems.
  • Linear and integer programs are accepted in [#Q5 MPS format] or in modeling languages such as AMPL and GAMS.
  • Submissions may be made by sending e-mail, by submitting names of local files through a Web form, or via a socket-based submission tool available in Java and Unix tcl/tk versions.
• Numerische Mathematik Interaktiv includes teaching tools for various linear and nonlinear optimization methods (in German).
• Optimisation Service Provision (OSP) is a prototype for a web-based service that offers varied modeling tools, solvers, and data management facilities. It presents a sophisticated interface and currently offers the only web access to the CPLEX and OSL solvers.
• RIOT. The Remote Interactive Optimization Testbed at Berkeley's Industrial Engineering and Operations Research Department, offering online demonstrations of numerous optimization tools and applications.

A more extensive survey appears in Optimization as an Internet Resource by R. Fourer and J.-P. Goux, in the INFORMS journal Interfaces, volume 31, number 2 (2001).

Online sources of optimization software

The Netlib Repository contains a huge collection of mathematical software, papers, and databases, maintained at the University of Tennessee, Knoxville and Oak Ridge National Laboratory. There are also mirror sites in the United States, Norway, the United Kingdom, and other locations. Once you know what you want from Netlib, you may may prefer to make requests by anonymous ftp or e-mail; alternative access methods and many other relevant matters are explained in the Netlib FAQ.

Many optimization packages are distributed from their own Web sites. Numerous links to these sites are provided elsewhere in this FAQ, especially under the [#Q2 Where is there good software?] question.

Online sources of optimization information

Varied general sources on optimization include information on linear and integer programming. They include:

• The Optimization Online repository of papers and reports on optimization. Contributions are accepted from anyone working in the field, and are moderated by a team of volunteer coordinators; you can subscribe to a monthly digest that summarizes reports recently received.
• The e-Optimization.community, a web meeting place for optimization users and developers, featuring a who's who of people in optimization as well as listings of optimization resources, applications, vendors, case studies, and news.
• The NEOS Guide of the Argonne/Northwestern Optimization Technology Center.
• The Decision Tree for Optimization Software by Hans Mittelmann and P. Spellucci, and the related Benchmarks for Optimization Software.
• Harvey Greenberg's Mathematical Programming Glossary and Bibliography for the Development of An Intelligent Mathematical Programming System.
• Listings of optimization software and related information at the Center for Advanced Modeling and Optimization.

More specialized sources include:

• Interior-Point Methods Online, containing most new reports in the area of interior-point methods that have appeared since December 1994. Abstracts for all reports are available, as are links to postscript source for most reports; a mailing list carries announcements of new papers, conferences, software, and special journal issues relevant to interior-point methods.
• A bibliography of books and papers on Interior-Point methods (including many older ones) compiled by Eberhard Kranich.
• A resource website in semidefinite programming maintained by Christoph Helmberg, and a semidefinite programming bibliography by Henry Wolkowicz.
• An extensive bibliography for stochastic programming and a specialized one for stochastic integer programming, compiled by Maarten van der Vlerk.

The following sites cover operations research and management science more generally, but have a large amount of content relevant to linear programming and other optimization problems:

• INFORMS Online, the website of the Institute for Operations Research and the Management Sciences, including:
  • Searchable databases of INFORMS conference presentations going back to 1990, and publications in operations research back to 1982.
  • The INFORMS OR/MS Resource Collection (formerly "Michael Trick's Operations Research Page").
• WORMS (World-Wide-Web for Operations Research and Management Science) at the Department of Mathematics and Statistics, University of Melbourne, Australia.
  

Who maintains this FAQ list?

This list is maintained by Robert Fourer, 4er@iems.northwestern.edu and the Optimization Technology Center of Northwestern University and Argonne National Laboratory.

This article is Copyright © 2000 by Robert Fourer. It may be freely redistributed in its entirety provided that this copyright notice is not removed. It may not be sold for profit or incorporated in commercial documents without the written permission of the copyright holder. Permission is expressly granted for this document to be made available for file transfer from installations offering unrestricted anonymous file transfer on the Internet.

The material in this document does not reflect any official position taken by any organization. While all information in this article is believed to be correct at the time of writing, it is provided "as is" with no warranty implied.

If you wish to cite this FAQ formally -- this may seem strange, but it does come up -- you may use:

Robert Fourer (4er@iems.northwestern.edu), "Linear Programming Frequently Asked Questions," Optimization Technology Center of Northwestern University and Argonne National Laboratory, http://wiki.mcs.anl.gov/NEOS/index.php/Linear_Programming_FAQ (2000).

Suggestions, corrections, topics you'd like to see covered, and additional material are all solicited. Send them to Robert Fourer.

Further References

See also the following pages pertaining to mathematical programming and optimization modeling:

• The related Nonlinear Programming FAQ.
• Harvey Greenberg's Mathematical Programming Glossary.
• The Optimization Online repository of reports and papers.
• The e-Optimization.community website.
• The NEOS Guide to optimization models and software.
• The Decision Tree for Optimization Software by H.D. Mittelmann and P. Spellucci.
• Software for Optimization: A Buyer's Guide by Robert Fourer.
• The OR/MS Today 2005 Linear Programming Software Survey.
• The NEOS Server for access to optimization solvers through the internet
• Hans Mittelmann's Benchmarks for Optimization Software.
• The Computational Optimization and Applications Software Forum

. . . and don't forget the Web search engines! Services such as Google (especially Google Scholar), Lycos, Yahoo, and Ask Jeeves can be surprisingly helpful in finding pages on particular problem types or application areas.