TITLE

A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem

AUTHOR(S)
Hadjar, Ahmed; Marcotte, Odile; Soumis, François
PUB. DATE
January 2006
SOURCE
Operations Research;Jan/Feb2006, Vol. 54 Issue 1, p130
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
We consider the multiple depot vehicle scheduling problem (MDVSP) and propose a branch-and-bound algorithm for solving it that combines column generation, variable fixing, and cutting planes. We show that the solutions of the linear relaxation of the MDVSP contain many "odd cycles." We derive a class of valid inequalities by extending the notion of odd cycle and describe a lifting procedure for these inequalities. We prove that the lifted inequalities represent, under certain conditions, facets of the underlying polytope. Finally, we present the results of a computational study comparing several strategies (variable fixing, cutting planes, mixed branching, and tree search) for solving the MDVSP.
ACCESSION #
19949374

 

Related Articles

  • Minimizing total completion time subject to release dates and sequence-dependent processing times. Bianco, Lucio; Dell'Olmo, Paolo; Giordani, Stefano // Annals of Operations Research;1999, Vol. 86 Issue 1-4, p393 

    We consider the problem of scheduling jobs with release dates and sequence-dependent processing times on a single machine to minimize the total completion time. We show that this problem is equivalent to the Cumulative Traveling Salesman Problem with additional time constraints. For this latter...

  • INTEGER PROGRAMMING POST-OPTIMAL ANALYSIS WITH CUTTING PLANES. Klein, Dieter; Holm, Søren // Management Science;Jan1979, Vol. 25 Issue 1, p64 

    Sufficient conditions have been developed for testing the optimality of solutions to all-integer and mixed-integer linear programming problems after coefficient changes in the right hand side and the objective function, or after introduction of new variables. The same conditions can be used as...

  • FROM VALID INEQUALITIES TO HEURISTICS: A UNIFIED VIEW OF PRIMAL-DUAL APPROXIMATION ALGORITHMS IN COVERING PROBLEMS. Bertsimas, Dimitris; Chung-Piaw Teo // Operations Research;Jul/Aug98, Vol. 46 Issue 4, p503 

    In recent years approximation algorithms based on primal-dual methods have been successfully applied to a broad class of discrete optimization problems. In this paper, we propose a generic primal-dual framework to design and analyze approximation algorithms for integer programming problems of...

  • Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs. Binyuan Chen; Küçükyavuz, Simge; Sen, Suvrajeet // Operations Research;Jan2011, Vol. 59 Issue 1, p202 

    In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm that constructs a linear program that has the same optimal...

  • Reformulations in mathematical programming: automatic symmetry detection and exploitation. Liberti, Leo // Mathematical Programming;Feb2012, Vol. 131 Issue 1/2, p273 

    If a mathematical program has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given...

  • Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem. Mokotoff, E.; Jimeno, J. L. // Annals of Operations Research;Nov2002, Vol. 117 Issue 1-4, p133 

    The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration....

  • EXTREME POINT MATHEMATICAL PROGRAMMING. Kirby, M. J. L.; Love, H. R.; Swarup, Kanti // Management Science;May72, Vol. 18 Issue 9, p540 

    The paper considers a class of optimization problems. The problems are linear programming problems: maximize ex subject to Ax = b with the additional constraint that x must also be an extreme point of a second convex polyhedron Dx = d. X ≥ 0. A cutting-plane algorithm for solving such...

  • SCHEDULING UNIT - TIME TASKS ON FLOW - SHOPS UNDER RESOURCE CONSTRAINTS. Błażewicz, J.; Kubiak, W.; Szwarcfiter, J. // Annals of Operations Research;1988, Vol. 16 Issue 1-4, p255 

    We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is...

  • EARLINESS-TARDINESS SCHEDULING PROBLEMS, I: WEIGHTED DEVIATION OF COMPLETION TIMES ABOUT A COMMON DUE DATE. Hall, Nicholas G.; Posner, Marc E. // Operations Research;Sep/Oct91, Vol. 39 Issue 5, p836 

    This paper and its companion (Part II) concern the scheduling of jobs with cost penalties for both early and late completion. In Part I, we consider the problem of minimizing the weighted sum of earliness and tardiness of jobs scheduled on a single processor around a common due date, d. We...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics