Accelerating Benders decomposition with heuristic master problem solutions

Alysson M. Costa; Jean François Cordeau; Bernard Gendron; Gilbert Laporte

doi:10.1590/s0101-74382012005000005

Accelerating Benders decomposition with heuristic master problem solutions

Alysson M. Costa, Jean François Cordeau, Bernard Gendron, Gilbert Laporte

Research output: Contribution to journal › Article › peer-review

28 Citations (SciVal)

Abstract

In this paper, a general scheme for generating extra cuts during the execution of a Benders decomposition algorithm is presented. These cuts are based on feasible and infeasible master problem solutions generated by means of a heuristic. This article includes general guidelines and a case study with a fixed charge network design problem. Computational tests with instances of this problem show the efficiency of the strategy. The most important aspect of the proposed ideas is their generality, which allows them to be used in virtually any Benders decomposition implementation.

Original language	English
Pages (from-to)	3-19
Number of pages	17
Journal	Pesquisa Operacional
Volume	32
Issue number	1
DOIs	https://doi.org/10.1590/s0101-74382012005000005
Publication status	Published - 2012

Keywords

Benders decomposition
Extra cuts generation
Mixed-integer programming

ASJC Scopus subject areas

Management Science and Operations Research

Access to Document

10.1590/s0101-74382012005000005Licence: CC BY-NC

Cite this

@article{be7fcac99ebc4708830d92315b91cf67,

title = "Accelerating Benders decomposition with heuristic master problem solutions",

abstract = "In this paper, a general scheme for generating extra cuts during the execution of a Benders decomposition algorithm is presented. These cuts are based on feasible and infeasible master problem solutions generated by means of a heuristic. This article includes general guidelines and a case study with a fixed charge network design problem. Computational tests with instances of this problem show the efficiency of the strategy. The most important aspect of the proposed ideas is their generality, which allows them to be used in virtually any Benders decomposition implementation.",

keywords = "Benders decomposition, Extra cuts generation, Mixed-integer programming",

author = "Costa, {Alysson M.} and Cordeau, {Jean Fran{\c c}ois} and Bernard Gendron and Gilbert Laporte",

year = "2012",

doi = "10.1590/s0101-74382012005000005",

language = "English",

volume = "32",

pages = "3--19",

journal = "Pesquisa Operacional",

issn = "0101-7438",

publisher = "Sociedade Brasileira de Pesquisa Operacional",

number = "1",

}

TY - JOUR

T1 - Accelerating Benders decomposition with heuristic master problem solutions

AU - Costa, Alysson M.

AU - Cordeau, Jean François

AU - Gendron, Bernard

AU - Laporte, Gilbert

PY - 2012

Y1 - 2012

N2 - In this paper, a general scheme for generating extra cuts during the execution of a Benders decomposition algorithm is presented. These cuts are based on feasible and infeasible master problem solutions generated by means of a heuristic. This article includes general guidelines and a case study with a fixed charge network design problem. Computational tests with instances of this problem show the efficiency of the strategy. The most important aspect of the proposed ideas is their generality, which allows them to be used in virtually any Benders decomposition implementation.

AB - In this paper, a general scheme for generating extra cuts during the execution of a Benders decomposition algorithm is presented. These cuts are based on feasible and infeasible master problem solutions generated by means of a heuristic. This article includes general guidelines and a case study with a fixed charge network design problem. Computational tests with instances of this problem show the efficiency of the strategy. The most important aspect of the proposed ideas is their generality, which allows them to be used in virtually any Benders decomposition implementation.

KW - Benders decomposition

KW - Extra cuts generation

KW - Mixed-integer programming

UR - http://www.scopus.com/inward/record.url?scp=84860851626&partnerID=8YFLogxK

U2 - 10.1590/s0101-74382012005000005

DO - 10.1590/s0101-74382012005000005

M3 - Article

AN - SCOPUS:84860851626

SN - 0101-7438

VL - 32

SP - 3

EP - 19

JO - Pesquisa Operacional

JF - Pesquisa Operacional

IS - 1

ER -

Accelerating Benders decomposition with heuristic master problem solutions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this