Cutting in branch‐and‐cut‐and‐ price algorithms

Simon Spoorendonk, Guy Desaulniers, Jacques Desrosiers

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    Abstract

    Given a Dantzig-Wolfe decomposition of an integer program, this talk presents a general framework for formulating, on the original formulation, valid inequalities derived on an equivalent master problem. It is possible to model these inequalities by adding new variables and constraints to the original formulation. We show how the additional inequalities may give rise to an augmented sub-problem. Examples on how to apply this framework are given for the vehicle routing problem with time windows.
    Original languageEnglish
    Publication date2010
    Publication statusE-pub ahead of print - 2010
    Event4th Nordic Optimization Symposium - Aarhus, Denmark
    Duration: 30 Sep 20102 Oct 2010
    Conference number: 4
    http://www.asb.dk/forskning/forskningscentreoggrupper/forskningscentre/coral/4thnordicoptimizationsymposium/

    Conference

    Conference4th Nordic Optimization Symposium
    Number4
    CountryDenmark
    CityAarhus
    Period30/09/201002/10/2010
    Internet address

    Fingerprint Dive into the research topics of 'Cutting in branch‐and‐cut‐and‐ price algorithms'. Together they form a unique fingerprint.

    Cite this