The Exponentiated Subgradient Algorithm for Heuristic Boolean Programming
- Dale Schuurmans, AICML
- Finnegan Southey
- Robert Holte, Department of Computing Science, University of Alberta
Boolean linear programs (BLPs) are ubiquitous in AI. Satisfiability testing, planning with resource constraints, and winner determination in combina torial auctions are all examples of this type of prob lem. Although increasingly wellinformed by work in OR, current AI research has tended to focus on specialized algorithms for each type of BLP task and has only loosely patterned new algorithms on effective methods from other tasks. In this paper we introduce a single generalpurpose local search pro cedure that can be simultaneously applied to the en tire range of BLP problems, without modification. Although one might suspect that a generalpurpose algorithm might not perform as well as specialized algorithms, we find that this is not the case here. Our experiments show that our generic algorithm simultaneously achieves performance comparable with the state of the art in satisfiability search and winner determination in combinatorial auctions--- two very different BLP problems. Our algorithm is simple, and combines an old idea from OR with recent ideas from AI.
Citation
D. Schuurmans, F. Southey, R. Holte. "The Exponentiated Subgradient Algorithm for Heuristic Boolean Programming". International Joint Conference on Artificial Intelligence (IJCAI), pp 334-341, August 2001.| Keywords: | exponentiated, subgradient |
| Category: | In Conference |
BibTeX
@incollection{Schuurmans+al:IJCAI01,
author = {Dale Schuurmans and Finnegan Southey and Robert Holte},
title = {The Exponentiated Subgradient Algorithm for Heuristic Boolean
Programming},
Pages = {334-341},
booktitle = {International Joint Conference on Artificial Intelligence
(IJCAI)},
year = 2001,
}Last Updated: August 13, 2007Submitted by Russ Greiner
