Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2018 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Compact Extended Linear Programming Models

verfasst von: Prof. Giuseppe Lancia, Prof. Paolo Serafini

Verlag: Springer International Publishing

Buchreihe : EURO Advanced Tutorials on Operational Research

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This book provides a handy, unified introduction to the theory of compact extended formulations of exponential-size integer linear programming (ILP) models. Compact extended formulations are equally powerful, but polynomial-sized, models whose solutions do not require the implementation of separation and pricing procedures. The book is written in a general, didactic form, first developing the background theoretical concepts (polyhedra, projections, linear and integer programming) and then delving into the various techniques for compact extended reformulations. The techniques are illustrated through a wealth of examples touching on many application areas, such as classical combinatorial optimization, network design, timetabling, scheduling, routing, computational biology and bioinformatics. The book is intended for graduate or PhD students – either as an advanced course on selected topics or within a more general course on ILP and mathematical programming – as well as for practitioners and software engineers in industry exploring techniques for developing optimization models for their specific problems.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
Linear Programming (LP) and Integer Linear Programming (ILP) are two of the most powerful tools ever created in mathematics. Their usefulness comes from the many areas where they can provide satisfactory modeling and solving techniques to real-life problems. Their appeal comes from the rich combinatorial and geometric theory they are based upon. Solving an LP problem consists in minimizing a linear functional over a polyhedron, which, in turn, amounts to detecting a vertex of the polyhedron where the linear functional achieves the minimum (if it exists).
Giuseppe Lancia, Paolo Serafini
Chapter 2. Polyhedra
Abstract
This chapter introduces the basic definitions and properties of polyhedra. Polyhedra are given an external description, in terms of a set of linear inequalities, and an internal description, in terms of vertices and extreme rays. The projection operator is described in detail. Other topics described are the union of polyhedra, Fourier elimination scheme, the relation of the number of facets with the number of vertices, Farkas’ Lemma.
Giuseppe Lancia, Paolo Serafini
Chapter 3. Linear Programming
Abstract
This chapter provides an introduction to Linear Programming theory. It discusses classical concepts such as duality, complementarity slackness, complexity and algorithmic issues.
Giuseppe Lancia, Paolo Serafini
Chapter 4. Integer Linear Programming
Abstract
This chapter provides an introduction to Integer Linear Programming (ILP). After reviewing the effective modeling of a problem via ILP, the chapter describes the two main solving procedures for integer programs, i.e., branch-and-bound and cutting planes. The theory of totally unimodular matrices is introduced to account for problems whose models have naturally integer solutions. State-of-the-art solvers for mixed-integer linear programs are described at the conclusion.
Giuseppe Lancia, Paolo Serafini
Chapter 5. Large-Scale Linear Programming
Abstract
This chapter describes ILP models of exponential-size, either in the number of constraints, the number of variables, or both. These are the models for which compact extended formulations are intended. The separation and pricing problems are introduced as a general paradigm for the solution of such large models.
Giuseppe Lancia, Paolo Serafini
Chapter 6. General Techniques for Compact Formulations
Abstract
This chapter illustrates the general way to build a compact extended formulation. The chapter also describes in detail how to use LP techniques to build a compact extended formulation. Some examples are immediately brought to the attention of the reader so that the technique can be better understood. Also the role of the nonnegative factorization of the slack matrix is explained and some preliminary examples are shown.
Giuseppe Lancia, Paolo Serafini
Chapter 7. The Permutahedron
Abstract
This chapter refers to a very interesting combinatorial object called permutahedron. We provide three different compact extended formulations. The first one is based on LP techniques and the second one on a simple projection of a polyhedron whose vertices are integral. Both these formulations require a quadratic number of variables and inequalities. A better compact extended formulation can be obtained via sorting networks for which a \(O(n\log n)\) formulation can be given.
Giuseppe Lancia, Paolo Serafini
Chapter 8. The Parity Polytope
Abstract
This chapter is focused on the parity polytope, i.e., the convex hull of all 0-1 vectors with an even number of ones. A closely related polytope is the convex hull of all 0-1 vectors with an odd number of ones. We show two alternative compact extended formulations for both polytopes, one based on the union of polyhedra and the other one on LP. Whereas the former is a quadratic extension, the latter is only linear. This result seems to be new.
Giuseppe Lancia, Paolo Serafini
Chapter 9. Trees
Abstract
This chapter is devoted to compact extended formulations of tree problems. First, we give a compact extended formulation for the relaxation of the Steiner tree problem. We then describe the well-known minimum spanning tree problem, for which there exist polynomial algorithms and exponential-size models. We use both LP techniques and nonnegative rank factorization to provide compact extended formulations. Finally we present two NP-hard problems related to spanning trees of some relevance in the literature. The first one deals with bounded-degree spanning trees and the second one with minimal routing-cost trees, that have a considerable importance in network design and computational biology.
Giuseppe Lancia, Paolo Serafini
Chapter 10. Cuts and Induced Bipartite Subgraphs
Abstract
In this chapter we compare three popular models for the maximum cut problem and show the equivalence of their relaxations by using compact extended formulations. These problems are closely related to the subject of edge-induced and node-induced bipartite subgraphs, for which we give compact extended formulations as well.
Giuseppe Lancia, Paolo Serafini
Chapter 11. Stable Sets
Abstract
In this chapter we show a general compact extended formulation for the relaxation of the stable set polytope. For some graphs the stable set polytope can be given an exact representation, although with an exponential number of inequalities. When the graphs are perfect, however, compact extended formulations are possible for the stable set polytope. We give an example of such situation by describing a compact extended formulation, obtained by LP techniques, for the class of comparability graphs.
Giuseppe Lancia, Paolo Serafini
Chapter 12. Traveling Salesman Problems
Abstract
This chapter is devoted to the Traveling Salesman Problem (TSP), one of the most famous problems of combinatorial optimization. Compact ILP models for this problem have been proposed since a long time, but most of them are not effective for computational purposes. We describe an effective compact model which expresses the subtour inequalities via the max-flow/min-cut theorem. In this chapter we also present a new formulation for the TSP that shows some flexibility to be adapted to some TSP variants such as, in particular, the TSP with time windows.
Giuseppe Lancia, Paolo Serafini
Chapter 13. Packing
Abstract
This chapter focuses on the famous cutting stock/bin packing problem which was the first problem to be modeled by column generation. The compact equivalent counterpart of this problem has a very interesting structure of a particular flow problem. Two other packing problems for which we may show compact extended formulations are the robust knapsack problem and the cycle packing problem. For the former problem we show, by using LP techniques, that of two different formulations appeared in the literature one is indeed the compact extended formulation of the other.
Giuseppe Lancia, Paolo Serafini
Chapter 14. Scheduling
Abstract
Scheduling problems are notoriously difficult and ILP models have not yet shown adequate strength for them to be competitive with other approaches. This chapter presents a time-indexed model for the Job-Shop problem that can be solved either by column generation or by a compact equivalent formulation. We present also an interesting approach for a one-machine problem for which a Dantzig-Wolfe decomposition was proposed. This example allows us to show how the Dantzig-Wolfe decomposition goes in the opposite direction with respect to the compactification techniques that we have extensively discussed in this book.
Giuseppe Lancia, Paolo Serafini
Chapter 15. Computational Biology Problems
Abstract
This chapter deals with some combinatorial optimization problems arising in computational biology. We first survey the assessment of the evolutionary distance between two genomes. The problem is equivalent to packing the edges of a bi-colored graph into a maximum number of alternating cycles, which naturally leads to an exponential-size ILP model. We then turn to the study of a particular type of bipartite matching, called alignment. Alignments are used to compare either protein sequences or protein 3-dimensional structures. We describe two exponential-size models for this type of comparisons and their compact extended reformulation.
Giuseppe Lancia, Paolo Serafini
Backmatter
Metadaten
Titel
Compact Extended Linear Programming Models
verfasst von
Prof. Giuseppe Lancia
Prof. Paolo Serafini
Copyright-Jahr
2018
Electronic ISBN
978-3-319-63976-5
Print ISBN
978-3-319-63975-8
DOI
https://doi.org/10.1007/978-3-319-63976-5