Approximate uni-directional benders decomposition

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

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 'op- Timality' 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.

Original languageEnglish
Title of host publicationWorkshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15)
Subtitle of host publicationW12: Planning, Search, and Optimization
EditorsWeng-Keen Wong, Daniel Lowd
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages24-31
Number of pages8
VolumeWS-15-12
ISBN (Electronic)9781577357230
Publication statusPublished - 2015
Externally publishedYes
EventW12: Planning, Search, and Optimization - Austin, United States of America
Duration: 25 Jan 201525 Jan 2015
https://aaai.org/Workshops/ws15.php

Conference

ConferenceW12: Planning, Search, and Optimization
CountryUnited States of America
CityAustin
Period25/01/1525/01/15
Internet address

Cite this