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

2005 | Buch

A Primer in Column Generation Kapitel lesen Erstes Kapitel lesen

Column Generation

herausgegeben von: Guy Desaulniers, Jacques Desrosiers, Marius M. Solomon

Verlag: Springer US

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

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Column Generation is an insightful overview of the state of the art in integer programming column generation and its many applications. The volume begins with "A Primer in Column Generation" which outlines the theory and ideas necessary to solve large-scale practical problems, illustrated with a variety of examples. Other chapters follow this introduction on "Shortest Path Problems with Resource Constraints," "Vehicle Routing Problem with Time Window," "Branch-and-Price Heuristics," "Cutting Stock Problems," each dealing with methodological aspects of the field. Three chapters deal with transportation applications: "Large-scale Models in the Airline Industry," "Robust Inventory Ship Routing by Column Generation," and "Ship Scheduling with Recurring Visits and Visit Separation Requirements." Production is the focus of another three chapters: "Combining Column Generation and Lagrangian Relaxation," "Dantzig-Wolfe Decomposition for Job Shop Scheduling," and "Applying Column Generation to Machine Scheduling." The final chapter by François Vanderbeck, "Implementing Mixed Integer Column Generation," reviews how to set-up the Dantzig-Wolfe reformulation, adapt standard MIP techniques to the column generation context (branching, preprocessing, primal heuristics), and deal with specific column generation issues (initialization, stabilization, column management strategies).

Inhaltsverzeichnis

Frontmatter
Chapter 1. A Primer in Column Generation
Abstract
We give a didactic introduction to the use of the column generation technique in linear and in particular in integer programming. We touch on both, the relevant basic theory and more advanced ideas which help in solving large scale practical problems. Our discussion includes embedding Dantzig-Wolfe decomposition and Lagrangian relaxation within a branch-and-bound framework, deriving natural branching and cutting rules by means of a so-called compact formulation, and understanding and influencing the behavior of the dual variables during column generation. Most concepts are illustrated via a small example. We close with a discussion of the classical cutting stock problem and some suggestions for further reading.
Jacques Desrosiers, Marco E. Lübbecke
Chapter 2. Shortest Path Problems with Resource Constraints
Abstract
In most vehicle routing and crew scheduling applications solved by column generation, the subproblem corresponds to a shortest path problem with resource constraints (SPPRC) or one of its variants.
This chapter proposes a classification and a generic formulation for the SPPRCs, briefly discusses complex modeling issues involving resources, and presents the most commonly used SPPRC solution methods. First and foremost, it provides a comprehensive survey on the subject.
Stefan Irnich, Guy Desaulniers
Chapter 3. Vehicle Routing Problem with Time Windows
Abstract
In this chapter we discuss the Vehicle Routing Problem with Time Windows in terms of its mathematical modeling, its structure and decomposition alternatives. We then present the master problem and the subproblem for the column generation approach, respectively. Next, we illustrate a branch-and-bound framework and address acceleration strategies used to increase the efficiency of branch-and-price methods. Then, we describe generalizations of the problem and report computational results for the classic Solomon test sets. Finally, we present our conclusions and discuss some open problems.
Brian Kallehauge, Jesper Larsen, Oli B.G. Madsen, Marius M. Solomon
Chapter 4. Branch-and-Price Heuristics: A Case Study on the Vehicle Routing Problem with Time Windows
Abstract
Branch-and-price is a powerful framework to solve hard combinatorial problems. It is an interesting alternative to general purpose mixed integer programming as column generation usually produces at the root node tight lower bounds (when minimizing) that are further improved when branching. Branching also helps to generate integer solutions, however branch-and-price can be quite weak at producing good integer solutions rapidly because the solution of the relaxed master problem is rarely integer-valued. In this paper, we propose a general cooperation scheme between branch-and-price and local search to help branch-and-price finding good integer solutions earlier. This cooperation scheme extends to branch-and-price the use of heuristics in branch-and-bound and it also generalizes three previously known accelerations of branch-and-price. We show on the vehicle routing problem with time windows (Solomon benchmark) that it consistently improves the ability of branch-and-price to generate good integer solutions ea rly while retaining the ability of branch-and-price to produce good lower bounds.
Emilie Danna, Claude Le Pape
Chapter 5. Cutting Stock Problems
Abstract
Column generation has been proposed by Gilmore and Gomory to solve cutting stock problem, independently of Dantzig-Wolfe decomposition. We survey the basic models proposed for cutting stock and the corresponding solution approaches. Extended Dantzig-Wolfe decomposition is surveyed and applied to these models in order to show the links to Gilmore-Gomory model. Branching schemes discussion is based on the subproblem formulation corresponding to each model. Integer solutions are obtained by combining heuristics and branch-and-price schemes. Linear relaxations are solved by column generation. Stabilization techniques such as dual-optimal inequalities and stabilized column generation algorithms that have been proposed to improve the efficiency of this process are briefly discussed.
Hatem Ben Amor, José Valério de Carvalho
Chapter 6. Large-Scale Models in the Airline Industry
Abstract
Operations research models are widely used in the airline industry. By using sophisticated optimization models and algorithms many airlines are able to improve profitability. In this paper we review these models and the underlying solution methodologies. We focus on models involving strategic business processes as well as operational processes. The former models include schedule design and fleeting, aircraft routing, and crew scheduling, while the latter models cope with irregular operations.
Diego Klabjan
Chapter 7. Robust Inventory Ship Routing by Column Generation
Abstract
We consider a real integrated ship scheduling and inventory management problem. A fleet of ships transports a single product between production and consumption plants. The transporter has the responsibility for keeping the inventory level within its limits at all actual plants, and there should be no need to stop the production at any plants caused by missing transportation possibilities.
Due to uncertainties in sailing time, we introduce soft inventory constraints and artificial penalty costs to the underlying model. The model is solved by a column generation approach. By introducing some model adjustments, the problem decomposes into a routing and scheduling subproblem for each ship and an inventory management subproblem for each port. The columns in the master problem represent ship schedules and port call sequences.
Marielle Christiansen, Bjørn Nygreen
Chapter 8. Ship Scheduling with Recurring Visits and Visit Separation Requirements
Abstract
This chapter discusses an application of advanced planning support in designing a sea-transport system. The system is designed for Norwegian companies who depend on sea-transport between Norway and Central Europe. They want to achieve faster and more frequent transport by combining tonnage. This requires the possible construction of up to 15 new ships with potential investments of approximately 150 mill US dollars. The problem is a variant of the general pickup and delivery problem with multiple time windows. In addition, it includes requirements for recurring visits, separation between visits and limits on transport lead-time. It is solved by a heuristic branch-and-price algorithm.
Mikkel M. Sigurd, Nina L. Ulstein, Bjørn Nygreen, David M. Ryan
Chapter 9. Combining Column Generation and Lagrangian Relaxation
Abstract
Although the possibility to combine column generation and Lagrangian relaxation has been known for quite some time, it has only recently been exploited in algorithms. In this paper, we discuss ways of combining these techniques. We focus on solving the LP relaxation of the Dantzig-Wolfe master problem. In a first approach we apply Lagrangian relaxation directly to this extended formulation, i.e. no simplex method is used. In a second one, we use Lagrangian relaxation to generate new columns, that is Lagrangian relaxation is applied to the compact formulation. We will illustrate the ideas behind these algorithms with an application in lot-sizing. To show the wide applicability of these techniques, we also discuss applications in integrated vehicle and crew scheduling, plant location and cutting stock problems.
Dennis Huisman, Raf Jans, Marc Peeters, Albert P.M. Wagelmans
Chapter 10. Dantzig-Wolfe Decomposition for Job Shop Scheduling
Abstract
This chapter presents a formulation for the job shop problem based on Dantzig-Wolfe decomposition with a subproblem for each machine. Each subproblem is a sequencing problem on a single machine with time windows. The formulation is used within an exact algorithm capable of solving problems with objectives C max, T max, as well as an objective consistent with the Just-In-Time principle. This objective involves an irregular cost function of operation completion times. Numerical results are presented for 2 to 10 machine problems involving up to 500 operations.
Sylvie Gélinas, François Soumis
Chapter 11. Applying Column Generation to Machine Scheduling
Abstract
The goal of a scheduling problem is to find out when each task must be performed and by which machine such that an optimal solution is obtained. Especially when the main problem is to divide the jobs over the machines, column generation turns out to be very successful. Next to a number of these ‘partitioning’ problems, we shall discuss a number of other problems that have successfully been tackled by a column generation approach.
Marjan van den Akker, Han Hoogeveen, Steef van de Velde
Chapter 12. Implementing Mixed Integer Column Generation
Abstract
We review the main issues that arise when implementing a column generation approach to solve a mixed integer program: setting-up the Dantzig-Wolfe reformulation, adapting standard MIP techniques to the context of column generation (branching, preprocessing, primal heuristics), and dealing with issues specific to column generation (initialization, stabilization, column management strategies). The description of the different features is done in generic terms to emphasize their applicability across problems. More hand-on experiences are reported in the literature in application specific context, f.i., see Desaulniers et al. (2001) for vehicle routing and crew scheduling applications. This paper summarizes recent work in the field, in particular that of Vanderbeck (2002, 2003).
François Vanderbeck
Metadaten
Titel
Column Generation
herausgegeben von
Guy Desaulniers
Jacques Desrosiers
Marius M. Solomon
Copyright-Jahr
2005
Verlag
Springer US
Electronic ISBN
978-0-387-25486-9
Print ISBN
978-0-387-25485-2
DOI
https://doi.org/10.1007/b135457

Premium Partner

    Bildnachweise