On generating maximal nondominated Benders cuts

Hanif Sherali () and Brian Lunday ()

Annals of Operations Research, 2013, vol. 210, issue 1, 57-72

Abstract: In this paper, we explore certain algorithmic strategies for accelerating the convergence of Benders decomposition method via the generation of maximal nondominated cuts. Based on interpreting the seminal work of Magnanti and Wong (Operations Research, 29(3), 464–484, 1981 ) for generating nondominated cuts within a multiobjective framework, we propose an algorithmic strategy that utilizes a preemptively small perturbation of the right-hand-side of the Benders subproblem to generate maximal nondominated Benders cuts, as well as a complimentary strategy that generates an additional cut in each iteration via an alternative emphasis on decision variable weights. We also examine the computational effectiveness of solving a secondary subproblem using an objective cut as proposed by Magnanti and Wong versus identifying the Pareto-optimality region for cut generation by utilizing complementary slackness conditions. In addition, we exhibit how a standard feasibility cut can be extracted from the solution of subproblems that generate only optimality cuts through the use of artificial variables. With Magnanti and Wong’s baseline procedure approximated during implementation via the use of a core point estimation technique (Papadakos in Computers and Operations Research, 36(1), 176–195, 2009 ), these algorithmic strategies are tested on instances from the literature concerning the fixed charge network flow program. Copyright Springer Science+Business Media, LLC 2013

Keywords: Benders decomposition; Maximal cuts; Nondominated cuts; Pareto-optimal cuts (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-011-0883-6 (text/html)
Access to full text is restricted to subscribers.

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:annopr:v:210:y:2013:i:1:p:57-72:10.1007/s10479-011-0883-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-011-0883-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().