KI-Beratung Beta

Produktbild: Maximal Lattice-Free Polyhedra in Mixed-Integer Cutting Plane Theory

Maximal Lattice-Free Polyhedra in Mixed-Integer Cutting Plane Theory

19,70 €

inkl. gesetzl. MwSt.

Beschreibung

This thesis deals with the generation, evaluation, and analysis of cutting planes for mixed-integer linear programs (MILP's). Such optimization problems involve finitely many variables, some of which are required to be integer. The aim is to maximize or minimize a linear objective function over a set...

Beschreibung

This thesis deals with the generation, evaluation, and analysis of cutting planes for mixed-integer linear programs (MILP's). Such optimization problems involve finitely many variables, some of which are required to be integer. The aim is to maximize or minimize a linear objective function over a set of finitely many linear equations and inequalities.
Many industrial problems can be formulated as MILP's. The presence of both, discrete and continuous variables, makes it difficult to solve MILP's algorithmically. The currently available algorithms fail to solve many real-life problems in acceptable time or can only provide heuristic solutions. As a consequence, there is an ongoing interest in novel solution techniques.
A standard approach to solve MILP's is to apply cutting plane methods. Here, the underlying MILP is used to construct a sequence of linear programs whose formulations are improved by successively adding linear constraints – so-called cutting planes – until one of the linear programs has an optimal solution which satisfies the integrality conditions on the integer constrained variables.
For many combinatorial problems, it is possible to immediately deduce several families of cutting planes by exploiting the inherent combinatorial structure of the problem. However, for general MILP's, no structural properties can be used. The generation of cutting planes must rather be based on the objective function and the given, unstructured set of linear equations and inequalities. On the one hand, this makes the derivation of strong cutting planes for general MILP's more difficult than the derivation of cutting planes for structured problems. On the other hand, for this very reason, the analysis of cutting plane generation for general MILP's becomes mathematically interesting.
This thesis presents an approach to generate cutting planes for a general MILP. The cutting planes are obtained from lattice-free polyhedra, that is polyhedra without interior integer point. The point of departure is an optimal solution of the linear programming relaxation of the underlying MILP. By considering multiple rows of an associated simplex tableau, a further relaxation is derived.
The first part of this thesis is dedicated to the analysis of this relaxation and it is shown how cutting planes for the general MILP can be deduced from the considered relaxation. It turns out that the generated cutting planes have a geometric interpretation in the space of the discrete variables. In particular, it is shown that the strongest cutting planes which can be derived from the considered relaxation correspond to maximal lattice-free polyhedra. As a result, problems on cutting planes are transferable into problems on maximal lattice-free polyhedra.
The second part of this thesis addresses the evaluation of the generated cutting planes. It is shown that the cutting planes which are important, are at the same time the cutting planes which are difficult to derive in the sense that they correspond to highly complex maximal lattice-free polyhedra. In addition, it is shown that under certain assumptions on the underlying system of linear equations and inequalities, the important cutting planes can be approximated with cutting planes which correspond to less complex maximal lattice-free polyhedra. A probabilistic model is used to complement the analysis. Moreover, a geometric interpretation of the results is given.
The third part of this thesis focuses on the analysis of lattice-free polyhedra. In particular, the class of lattice-free integral polyhedra is investigated, a class which is important within a cutting plane framework. Two different notions of maximality are introduced. It is distinguished into the class of lattice-free integral polyhedra which are not properly contained in another lattice-free integral polyhedron, and the class of lattice-free integral polyhedra which are not properly contained in another lattice-free convex set. Both classes are analyzed, especially with respect to the properties of their representatives and the relation between the two classes. It is shown that both classes are of large cardinality and that they contain very large elements.
For the second as well as the third part of this thesis, statements about two-dimensional lattice-free convex sets are needed. For that reason, the fourth part of this thesis is devoted to the derivation of these results.

Produktdetails

Format

PDF

Kopierschutz

Nein

Family Sharing

Ja

Text-to-Speech

Nein

Produktdetails

Format

PDF

Format

eBooks im PDF-Format haben eine festgelegte Seitengröße und eignen sich daher nur bedingt zum Lesen auf einem tolino eReader oder Smartphone. Für den vollen Lesegenuss empfehlen wir Ihnen bei PDF-eBooks die Verwendung eines Tablets oder Computers.

Kopierschutz

Nein

Kopierschutz

Dieses eBook können Sie uneingeschränkt auf allen Geräten der tolino Familie, allen sonstigen eReadern und am PC lesen. Das eBook ist nicht kopiergeschützt und kann ein personalisiertes Wasserzeichen enthalten. Weitere Hinweise zum Lesen von eBooks mit einem personalisierten Wasserzeichen finden Sie unter Hilfe/Downloads.

Family Sharing

Ja

Family Sharing

Mit Family Sharing können Sie eBooks innerhalb Ihrer Familie (max. sechs Mitglieder im gleichen Haushalt) teilen. Sie entscheiden selbst, welches Buch Sie mit welchem Familienmitglied teilen möchten. Auch das parallele Lesen durch verschiedene Familienmitglieder ist durch Family Sharing möglich. Um eBooks zu teilen oder geteilt zu bekommen, muss jedes Familienmitglied ein Konto bei Thalia oder einem anderen tolino-Buchhändler haben. Weitere Informationen finden Sie unter Hilfe/Family-Sharing.

Text-to-Speech

Nein

Text-to-Speech

Bedeutet Ihnen Stimme mehr als Text? Mit der Funktion Text-to-Speech können Sie sich im tolino webReader und in der aktuellen Thalia – Lesen & Hören App das eBook vorlesen lassen. Weitere Informationen finden Sie unter Hilfe/Text-to-Speech.

Erscheinungsdatum

15.11.2011

Verlag Cuvillier Verlag eBooks
Seitenzahl

181 (Printausgabe)

Dateigröße

1486 KB

Sprache

Englisch

EAN

9783736939271

Barrierefreiheit
  • keine Information zur Barrierefreiheit bekannt

Noch keine Bewertungen vorhanden

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.

Kundinnen und Kunden meinen

Bewertungen (0)

Weitere Artikel finden Sie in

Die Leseprobe wird geladen.
  • Produktbild: Maximal Lattice-Free Polyhedra in Mixed-Integer Cutting Plane Theory