Decomposition Techniques for Hybrid MILP/CP Models applied to Scheduling and Routing Problems

Pedro M. Castro (), Ignacio E. Grossmann and Louis-Martin Rousseau
Additional contact information
Pedro M. Castro: Unidade de Modelação e Optimização de Sistemas Energéticos

A chapter in Hybrid Optimization, 2011, pp 135-167 from Springer

Abstract: Abstract This chapter provides a review of decomposition algorithms for models that are formulated as hybrid mixed-integer linear/constraint programming problems, such as logic Bender Decomposition and Constraint Programming-Based Column Generation. We first focus the decomposition techniques on single stage scheduling problems with parallel machines where the hybrid model provides a natural representation as the decisions decompose into assignment and sequencing decisions. We describe a general decomposition algorithm for the hybrid MILP/CP model in terms of a Benders decomposition scheme, as well as in terms of a branch and cut framework. We then consider Vehicle Routing and Crew Rostering applications to illustrate how Hybrid Branch-and-Price method can be applied, and we discuss the different models that have been proposed in the literature.

Keywords: Schedule Problem; Column Generation; Constraint Programming; Master Problem; Linear Programming Relaxation (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-1-4419-1644-0_4

Ordering information: This item can be ordered from
http://www.springer.com/9781441916440

DOI: 10.1007/978-1-4419-1644-0_4

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().