Speed-up Benders decomposition using maximum density cut (MDC) generation

Author： Saharidis Georgios Ierapetritou Marianthi

ISSN： 0254-5330

Source： Annals of Operations Research, Vol.210, Iss.1, 2013-11, pp. : 101-123

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The classical implementation of Benders decomposition in some cases results in low density Benders cuts. Covering Cut Bundle (CCB) generation addresses this issue with a novel way generating a bundle of cuts which could cover more decision variables of the Benders master problem than the classical Benders cut. Our motivation to improve further CCB generation led to a new cut generation strategy. This strategy is referred to as the Maximum Density Cut (MDC) generation strategy. MDC is based on the observation that in some cases CCB generation is computational expensive to cover all decision variables of the master problem than to cover part of them. Thus MDC strategy addresses this issue by generating the cut that involves the rest of the decision variables of the master problem which are not covered in the Benders cut and/or in the CCB. MDC strategy can be applied as a complimentary step to the CCB generation as well as a standalone strategy. In this work the approach is applied to two case studies: the scheduling of crude oil and the scheduling of multi-product, multi-purpose batch plants. In both cases, MDC strategy significant decreases the number of iterations of the Benders decomposition algorithm, leading to improved CPU solution times.