News & Events

Kevin Wood - Advances in Nested Benders Decomposition, Apr 4

Nested Benders decomposition nominally applies to multi-stage LPs, possibly with integer variables in the first stage. We apply the technique to a multi-stage binary IP, however, the open-pit mine block sequencing problem (OPBS). A solution to our OPBS model schedules the excavation of an open-pit mine over a multi-year time horizon, incorporating logical constraints on when adjacent blocks of earth are removed, plus lower- and upper-bounding constraints on resources. Cumulative binary variables (block b is extracted by time period t, or it is not) enable the creation of aggregate models that help guide a new “hierarchical decomposition.” Among other things, this decomposition can recursively split a model into a master problem and two subproblems rather than into a master problem and the usual single subproblem. We show computational results that are the best in the literature for OPBS models with both lower- and upper-bounding resource constraints. Potential applications in other areas such as production scheduling are also discussed.

Drawings will be used, painted with a broad brush, but with enough detail to take the mystery out of nested Benders decomposition. Collaborators on this work are Thomas Vossen at the University of Colorado at Boulder and Alexandra Newman at Colorado School of Mines.

Dr. Kevin Wood is Distinguished Professor Emeritus of Operations Research at the Naval Postgraduate School, having retired in 2015. He earned a PhD in the IEOR Department at UC Berkeley in 1982 and joined NPS immediately. At NPS, he taught courses in networks and optimization and studied problems in network reliability; network algorithms; linear, integer and stochastic programming; game theory; and system interdiction and defense. He has published over 50 refereed papers. His 1993 paper “Deterministic Network Interdiction” spurred renewed interest in the theory and application of network- and system-interdiction models, and led to a series of papers on these topics by him and others. More recently, he has developed models for protecting an electrical power grid from attack—What is the minimum inventory of high-voltage “recovery transformers” needed to protect against a worst-case attack?—along with computational methods to solve such models. Most recently, he has been investigating variants on Benders decomposition for solving a variety of integer and mixed-integer programs. (For example, see “Benders decomposition: Solving binary master problems by enumeration,”")

Student Level Image: 
Prospective Students
Resources and information
The IEOR Department offers three graduate degrees: Master of Science (MS), Master of Engineering (MEng), and Ph.D.
Student Level Image: 
Current Students
Scheduling and faculty office hours
Resources and information for undergraduate and graduate students, faculty, and staff