Generalizing backdoors

Roberto Rossi, Steven Prestwich, S Armagan Tarim, Brahim Hnich

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A powerful intuition in the design of search methods is that one wants to proactively select variables that simplify the problem instance as much as possible when these variables are assigned values. The notion of "Backdoor" variables follows this intuition. In this work we generalize Backdoors in such a way to allow more general classes of sub-solvers, both complete and heuristic. In order to do so, Pseudo-Backdoors and Heuristic-Backdoors are formally introduced and then applied firstly to a simple Multiple Knapsack Problem and secondly to a complex combinatorial optimization problem in the area of stochastic inventory control. Our preliminary computational experience shows the effectiveness of these approaches that are able to produce very low run times and | in the case of Heuristic-Backdoors | high quality solutions by employing very simple heuristic rules such as greedy local search strategies.
Original languageEnglish
Title of host publicationProceedings of the 5th International Workshop on Local Search Techniques in Constraint Satisfaction (LSCS 2008)
Publication statusPublished - 2008
Event5th International Workshop on Local Search Techniques in Constraint Satisfaction (LSCS 2008) - Sydney, Australia
Duration: 14 Sep 2008 → …

Workshop

Workshop5th International Workshop on Local Search Techniques in Constraint Satisfaction (LSCS 2008)
CountryAustralia
CitySydney
Period14/09/08 → …

Fingerprint Dive into the research topics of 'Generalizing backdoors'. Together they form a unique fingerprint.

Cite this