Benders decomposition: Solving binary master problems by enumeration

详细信息    查看全文

• 作者：D. Antony Tarvin^a ; ^{tony.tarvin@hotmail.com" class="auth_mail" title="E-mail the corresponding author} ; R. Kevin Wood^b ; ^{kwood@nps.edu" class="auth_mail" title="E-mail the corresponding author} ; Alexandra M. Newman^c ; ^{anewman@mines.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Benders decomposition ; Explicit enumeration ; Facility location
• 刊名：Operations Research Letters
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：44
• 期：1
• 页码：80-85
• 全文大小：486 K

文摘

We develop a variant of Benders decomposition for mixed-integer programming that solves each master problem by explicit enumeration. By storing the master problem’s current objective-function value for each potential solution, computational effort remains essentially constant across iterations. Using both serial and parallel processing, tests against competing methods show computational speedups that exceed two orders of magnitude.