A new cross decomposition method for stochastic mixed-integer linear programming

Emmanuel Ogbe and Xiang Li

European Journal of Operational Research, 2017, vol. 256, issue 2, 487-499

Abstract: Two-stage stochastic mixed-integer linear programming (MILP) problems can arise naturally from a variety of process design and operation problems. These problems, with a scenario based formulation, lead to large-scale MILPs that are well structured. When first-stage variables are mixed-integer and second-stage variables are continuous, these MILPs can be solved efficiently by classical decomposition methods, such as Dantzig/Wolfe decomposition (DWD), Lagrangian decomposition, and Benders decomposition (BD), or a cross decomposition strategy that combines some of the classical decomposition methods. This paper proposes a new cross decomposition method, where BD and DWD are combined in a unified framework to improve the solution of scenario based two-stage stochastic MILPs. This method alternates between DWD iterations and BD iterations, where DWD restricted master problems and BD primal problems yield a sequence of upper bounds, and BD relaxed master problems yield a sequence of lower bounds. The method terminates finitely to an optimal solution or an indication of the infeasibility of the original problem. Case study of two different supply chain systems, a bioproduct supply chain and an industrial chemical supply chain, show that the proposed cross decomposition method has significant computational advantage over BD and the monolith approach, when the number of scenarios is large.

Keywords: Stochastic programming; Mixed-integer linear programming; Cross decomposition; Benders decomposition; Dantzig–Wolfe decomposition (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716306208
Full text for ScienceDirect subscribers only

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:eee:ejores:v:256:y:2017:i:2:p:487-499

DOI: 10.1016/j.ejor.2016.08.005

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().