Approximate Uni-directional Benders Decomposition
Christina N. Burt, Nir Lipovetzky, Adrian R. Pearce, Peter J. Stuckey · 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 re-turn a strong ‘no-good’, ‘Benders feasibility’, or ’op-timality ’ cut. Instead, we focus our attention on a uni-directional decomposition approach. Instead of provid-ing a relaxation of the sub-problem for the master prob-lem, as in Benders decomposition, we provide an ap-