Optimization Online


Approximate Uni-directional Benders Decomposition

Christina N Burt (cnburt***at***unimelb.edu.au)
Nir Lipovetzky (nir.lipovetzky***at***unimelb.edu.au)
Adrian R Pearce (adrianrp***at***unimelb.edu.au)
Peter J Stuckey (pstuckey***at***unimelb.edu.au)

Abstract: 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 'optimality' cut. Instead, we focus our attention on a uni-directional decomposition approach. Instead of providing a relaxation of the sub-problem for the master problem, as in Benders decomposition, we provide an approximation of the sub-problem. Thus, we aim at finding good quality feasible solutions in the first iteration. While the quality of the approximation itself affects the impact of this approach, we illustrate that even using a simple approximation can have strong positive impact on two examples: the Travelling Purchaser Problem and a Mine Planning Problem.

Keywords: Benders Decomposition; State-space Search; Heuristics

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Scheduling )

Citation: AAAI-15 Workshop on Planning, Search and Optimisation

Download: [PDF]

Entry Submitted: 11/30/2014
Entry Accepted: 11/30/2014
Entry Last Modified: 02/10/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society