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

Simon Spoorendonk; Guy Desaulniers; Jacques Desrosiers

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

Simon Spoorendonk, Guy Desaulniers, Jacques Desrosiers

Research output: Contribution to conference › Conference abstract for conference › Research › peer-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 language	English
Publication date	2010
Publication status	E-pub ahead of print - 2010
Event	4th Nordic Optimization Symposium - Aarhus, Denmark Duration: 30 Sept 2010 → 2 Oct 2010 Conference number: 4 http://www.asb.dk/forskning/forskningscentreoggrupper/forskningscentre/coral/4thnordicoptimizationsymposium/

Conference

Conference	4th Nordic Optimization Symposium
Number	4
Country/Territory	Denmark
City	Aarhus
Period	30/09/2010 → 02/10/2010
Internet address	http://www.asb.dk/forskning/forskningscentreoggrupper/forskningscentre/coral/4thnordicoptimizationsymposium/

OpenUrl availability

Full text

Cite this

@conference{74da40dc73964035a9021a93a956f679,

title = "Cutting in branch‐and‐cut‐and‐ price algorithms",

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.",

author = "Simon Spoorendonk and Guy Desaulniers and Jacques Desrosiers",

year = "2010",

language = "English",

note = "4th Nordic Optimization Symposium, NOS4 ; Conference date: 30-09-2010 Through 02-10-2010",

url = "http://www.asb.dk/forskning/forskningscentreoggrupper/forskningscentre/coral/4thnordicoptimizationsymposium/",

}

TY - ABST

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

AU - Spoorendonk, Simon

AU - Desaulniers, Guy

AU - Desrosiers, Jacques

N1 - Conference code: 4

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

M3 - Conference abstract for conference

T2 - 4th Nordic Optimization Symposium

Y2 - 30 September 2010 through 2 October 2010

ER -

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

Abstract

Conference

OpenUrl availability

Fingerprint

Cite this