Mixed-Integer Programming Subject to Uncertain Data (PDF)

Abstract

The here presented thesis deals with optimization problems where the underlying problem data are subject to uncertainty. Sources of data uncertainty in practical problems are manifold, and so are the ways to model uncertainty in a mathematical programming context. The position taken in this thesis is that the underlying problem is a linear or mixedinteger program where some part of the problem data, e.g., the constraint matrix, is described by a set of possible matrices instead of a single one. There are two opposite viewpoints on this: The optimist assumes that he can influence the uncertainty and, thus, can choose a constraint matrix along with values for the variables of the underlying problem. The pessimist, however, assumes that he has to take a decision without having this possibility to choose and, therefore, assumes the worst case. The former viewpoint is expressed by a so called generalized mixed-integer program, the latter by a so called robust mixed-integer program.

In the first part of this thesis, robust problems with uncertainty in the cost vector are investigated. Here, the emphasis lies on considering simply structured uncertainties that allow the reduction of a problem with uncertainty to a series of problems of the same type but without uncertainty. It is known from the literature that this is possible for robust 0-1 programs and the robust minimum-cost flow problem if the uncertainty is a (higher dimensional) interval where the upper bound corner is cut off by a single cardinality constraint; this constraint permits control over the amount of robustness in the problem. In this thesis, it is demonstrated that this is still possible for uncertainties where the upper bound is cut off by arbitrarily many knapsack constraints with non-negative coefficients, which permits more detailed control. For the robust minimum-cost flow problem, a subgradient optimization approach is proposed; this is more practical than the binary search method proposed in literature.

The second part of this thesis is concerned with more general uncertainties, mainly polyhedral ones, and robust and generalized mixed-integer programs. Reformulations of these problems as mixed-integer programs are discussed, and some useful tools known from linear programming, like duality and Farkas’ lemma, are reviewed for linear programs with uncertainty. With help of these, it is shown that lattice-free cuts for robust mixed-integer programs are generated by generalized linear programs while lattice-free cuts for generalized mixed-integer programs are generated by robust linear programs. Strengthening procedures, known from literature for the non-uncertain case, and, finally, problems with uncertainties described by convex conic sets are investigated.

The performance of the lattice-free cuts for robust mixed-integer programs is assessed in terms of the amount of gap closed and the time spent for cut generation by a computational study.



Zusammenfassung

Die hier vorgelegte Dissertation beschäftigt sich mit Optimierungsproblemen, bei denen die zugrundeliegenden Daten Unsicherheit unterliegen. Quellen für Unsicherheit der Daten praktischer Probleme sind vielfältiger Natur und genauso vielfältig sind demnach die Herangehensweisen, Unsicherheit im Kontext der mathematischen Programmierung zu modellieren. Der Standpunkt dieser Arbeit ist, dass das zugrundeliegende Problem ein lineares oder gemischt-ganzzahliges Programm ist, bei dem ein Teil der Daten, zum Beispiel die Nebenbedingungsmatrix, anstatt durch eine einzelne Matrix durch eine Menge an möglichen Matrizen beschrieben ist. Hierauf gibt es zwei entgegengesetzte Sichtweisen: Der Optimist geht davon aus, dass er die Unsicherheit beeinflussen kann und so eine Nebenbedingungsmatrix zusammen mitWerten für die Variablen des zugrundeliegenden Problems frei wählen kann. Der Pessimist jedoch nimmt an, dass er eine Entscheidung ohne dieseWahlmöglichkeit treffen muss, und geht daher vom schlimmsten Fall aus. Erstere Sichtweise drückt sich durch ein sogenanntes verallgemeinertes gemischt-ganzzahliges Programm aus, letztere durch ein sogenanntes robustes gemischt-ganzzahliges Programm.

Im ersten Teil dieser Dissertation werden robuste Probleme mit Unsicherheit im Kostenvektor untersucht. Hier liegt der Schwerpunkt bei der Betrachtung von einfach strukturierten Unsicherheiten, die es erlauben, das Problem mit Unsicherheit auf eine Reihe von Problemen gleichen Typs, aber ohne Unsicherheit zurückzuführen. Aus der Literatur ist bekannt, dass dies für robuste 0-1-Programme und für das robuste Minimum-Cost-Flow-Problem möglich ist, sofern die Unsicherheit durch ein (mehrdimensionales) Intervall gegeben ist, bei dem die obere Schranke durch eine Kapazitätsungleichung abgeschnitten wird; diese Ungleichung ermöglicht es, das Maß an Robustheit im Problem zu regulieren. In dieser Arbeit wird gezeigt, dass dies immer noch für Unsicherheiten, bei denen die obere Schranke durch beliebig viele Knapsack-Ungleichungen mit nichtnegativen Koeffizienten abgeschnitten wird und die so eine genauere Regulierung der Robustheit erlauben, immer noch möglich ist. Für das robuste Minimum-Cost-Flow-Problem wird hierbei ein Subgradientenverfahren vorgeschlagen, welches für die Praxis geeigneter ist als die in der Literatur vorgeschlagene binäre Suche.

Der zweite Teil dieser Dissertation beschäftigt sich mit allgemeineren Unsicherheiten, hauptsächlich polyedrischen, bei robusten und verallgemeinerten gemischt-ganzzahligen Programmen. Zunächst werden einige Reformulierungen solcher Probleme als gemischt-ganzzahlige Programme diskutiert, gefolgt von einem Überblick über einige nützliche Hilfsmittel für lineare Programme mit Unsicherheit, die bereits von der klassischen linearen Programmierung bekannt sind, etwa Dualität und Farkas Lemma. Mit deren Hilfe wird dann gezeigt, dass Lattice-Free-Cuts für robuste gemischt-ganzzahlige Programme durch verallgemeinerte lineare Programme erzeugt werden, sowie dass Lattice-Free-Cuts für verallgemeinerte gemischt-ganzzahlige Programme durch robuste lineare Programme erzeugt werden. Darüber hinaus werden Strengthening-Methoden, bekannt aus der Literatur für den Fall ohne Unsicherheit, und schließlich Probleme mit konvex-konischer Unsicherheit untersucht.

Die Güte der Lattice-Free-Cuts für robuste gemischt-ganzzahlige Programme wird anhand von rechnergestützten Experimenten hinsichtlich der überbrückten Ganzzahligkeitslücke und der zur Cut-Generierung benötigten Zeit bewertet.