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

Content Provider	Springer Nature Link
Author	Saharidis, Georgios K. D. Ierapetritou, Marianthi G.
Copyright Year	2012
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.
Starting Page	101
Ending Page	123
Page Count	23
File Format	PDF
ISSN	02545330
Journal	Annals of Operations Research
Volume Number	210
Issue Number	1
e-ISSN	15729338
Language	English
Publisher	Springer US
Publisher Date	2012-11-17
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Benders decomposition Mixed integer linear programming Multi-generation of cuts Covering cut bundle generation (CCB) Active constraints Operations Research/Decision Theory Combinatorics Theory of Computation
Content Type	Text
Resource Type	Article
Subject	Management Science and Operations Research

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Classical Cuts for Mixed-Integer Programming and Branch-and-Cut

Solution of preemptive multi-objective network design problems applying Benders decomposition method

Accelerating benders decomposition with heuristicmaster problem solutions

Single-facility scheduling by logic-based Benders decomposition

Lift-and-project cuts for convex mixed integer nonlinear programs : Linear programming based separation and extended formulations

An interior-point Benders based branch-and-cut algorithm for mixed integer programs

Generalized Benders Decomposition Method to Solve Big Mixed-Integer Nonlinear Optimization Problems with Convex Objective and Constraints Functions

Resolution method for mixed integer bi-level linear problems based on decomposition technique

A decomposition approach to the two-stage stochastic unit commitment problem

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

Similar Documents

Classical Cuts for Mixed-Integer Programming and Branch-and-Cut

Solution of preemptive multi-objective network design problems applying Benders decomposition method

Accelerating benders decomposition with heuristicmaster problem solutions

Single-facility scheduling by logic-based Benders decomposition

Lift-and-project cuts for convex mixed integer nonlinear programs : Linear programming based separation and extended formulations

An interior-point Benders based branch-and-cut algorithm for mixed integer programs

Generalized Benders Decomposition Method to Solve Big Mixed-Integer Nonlinear Optimization Problems with Convex Objective and Constraints Functions

Resolution method for mixed integer bi-level linear problems based on decomposition technique

A decomposition approach to the two-stage stochastic unit commitment problem

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