Conference Proceedings

Approximate Uni-directional Benders Decomposition

Christina N Burt, Nir Lipovetzky, Adrian R Pearce, Peter J Stuckey

Proceedings of PlanSOpt-15 Workshop on Planning, Search and Optimization AAAI-15 (2015) | AAAI Press | Published : 2015


We examine a decomposition approach to find good quality feasible solutions. In particular, we study a method to reduce the search-space by decomposing a problem into two partitions, where the second partition (i.e., the subproblem) contains the fixed solution of the first (i.e., the master). This type of approach is usually motivated by the presence of two sub-problems that are each more easily solved by different methods. Our work is motivated by methods for which it is nontrivial to return a strong 'no-good', 'Benders feasibility', or 'op- Timality' cut. Instead, we focus our attention on a uni-directional decomposition approach. Instead of providing a relaxation of the sub-problem for th..

View full abstract