Proceedings

The Exponentiated Subgradient Algorithm for Heuristic Boolean Programming

Download BibTeX Cite

Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 334-340.

© 2001 International Joint Conferences on Artificial Intelligence

Abstract

Boolean linear programs (BLPs) are ubiquitous in AI. Satisfiability testing, planning with resource constraints, and winner determination in combinatorial auctions are all examples of this type of problem. Although increasingly well-informed 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 general-purpose local search procedure that can be simultaneously applied to the entire range of BLP problems, without modification. Although one might suspect that a general-purpose 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.

  1. [Andersson et al., 2000] A. Andersson, M. Tenhunen, and F. Ygge. Integer programming for combinatorial auction winner determination. In Proceedings ICMAS-00, 2000.
  2. [Beacham et al., 2001] A. Beacham, X. Chen, J. Sillito, and P. van Beek. Constraint programming lessons learned from crossword puzzles. In Proc. Canadian AI Conf., 2001.
  3. [Bertsekas, 1995] D. Bertsekas. Nonlinear Optimization. Athena Scientific, 1995.
  4. [Davenport et al., 1994] A. Davenport, E. Tsang, C. Wang, and K. Zhu. GENET: A connectionist architecture for solving constraint satisfaction problems. In Proceedings AAAI-94, pages 325-330, 1994.
  5. [Everett, 1963] H. Everett. Generalized Lagrange multiplier method for solving problems of the optimal allocation of resources. Operations Res., 11:399-417, 1963.
  6. [Fisher, 1981] M. Fisher. The Lagrangian relaxation method for solving integer programming problems. Management Sci., 27:1-18, 1981.
  7. [Frank, 1997] J. Frank. Learning short-tem weights for GSAT. In Proceedings IJCAI-97, pages 384-391, 1997.
  8. [Fujishima et al., 1999] Y. Fujishima, K. Leyton-Brown, and Y. Shoham. Taming the computational complexity of com- binatorial auctions: optimal and approximate approaches. In Proceedings IJCAI-99, pages 548-553, 1999. IJCAI
  9. [Glover, 1989] F. Glover. Tabu search Part 1. ORSA Journal on Computing, 1(3):190-206, 1989.
  10. [Gomes, 2000] C. Gomes. Structure, duality, and random- ization: Common themes in AI and OR. In Proceedings AAAI-00, pages 1152-1158, 2000.
  11. [Held and Karp, 1970] M. Held and R. Karp. The travelling salesman problem and minimum spanning trees. Opera- tions Res., 18:1138-1162, 1970.
  12. [Holte, 2001] R. Holte. Combinatorial auctions, knapsack problems, and hill-climbing search. In Proceedings Cana- dian AI Conference, 2001.
  13. [Hooker et al., 1999] J. Hooker, G. Ottosson, E. Thorsteins- son, and H.-K. Kim. On integrating constraint propaga- tion and linear programming for combinatorial optimiza- tion. Proceedings AAAI-99, pages 136-141, 1999.
  14. [Hoos and Boutilier, 2000] H. Hoos and C. Boutilier. Solv- ing combinatorial auctions using stochastic local search. In Proceedings AAAI-00, pages 22-29, 2000.
  15. [Hoos and Stützle, 2000] H. Hoos and T. Stützle. Local search algorithms for SAT: An empirical evaluation. J. Automat. Reas., 24:421-481, 2000.
  16. [Hoos, 1999] H. Hoos. On the run-time behavior of stochas- tic local search algorithms for SAT. In Proceedings AAAI- 99, pages 661-666, 1999.
  17. [Kautz and Selman, 1996] H. Kautz and B. Selman. Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings AAAI-96, pages 1194-1201, 1996.
  18. [Kautz and Walser, 1999] H. Kautz and J. Walser. State- space planning by integer optimization. Proceedings AAAI-99, pages 526-533, 1999.
  19. [Kivinen and Warmuth, 1997] J. Kivinen and M. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Infor. Comput., 132:1-63, 1997.
  20. [Larsson et al., 1996] T. Larsson, M. Patriksson, and A.-B. Stromberg. Conditional subgradient optimization-theory and applications. Euro. J. Oper. Res., 88:382-403, 1996.
  21. [Lau et al., 2000] H. Lau, A. Lim, and Q. Liu. Solving a supply chain optimization problem collaboratively. Pro- ceedings AAAI-00, pages 780-785, 2000.
  22. [Leyton-Brown et al., 2000] K. Leyton-Brown, M. Pearson, and Y. Shoham. Towards a universal test suite for combi- natorial auction algorithms. In Proc. EC-00, 2000.
  23. [Magazine and Oguz, 1984] M. Magazine and O. Oguz. A heuristic algorithm for the multidimensional knapsack problem. Euro. J. Oper. Res., 16:319-326, 1984.
  24. [Martin, 1999] R. Martin. Large Scale Linear and Integer Optimization. Kluwer, 1999.
  25. [McAllester et al., 1997] D. McAllester, B. Selman, and H. Kautz. Evidence for invariants in local search. In Pro- ceedings AAAI-97, pages 321-326, 1997.
  26. [Parkes and Walser, 1996] A. Parkes and J. Walser. Tuning local search for satisfiability testing. In Proceedings AAAI- 96, pages 356-362, 1996.
  27. [Resende and Feo, 1996] M. Resende and T. Feo. A GRASP for satisfiability. In Cliques, Coloring, and Satisfiability, DIMACS series v.26, pages 499-520. AMS, 1996.
  28. [Sandholm, 1999] T. Sandholm. An algorithm for optimal winner determination in combinatorial auctions. In Pro- ceedings IJCAI-99, pages 542-547, 1999. IJCAI
  29. [Schuurmans and Southey, 2000] D. Schuurmans and F. Southey. Local search characteristics of incomplete SAT procedures. In Proc. AAAI-00, pages 297-302, 2000.
  30. [Selman et al., 1994] B. Selman, H. Kautz, and B. Cohen. Noise strategies for improving local search. In Proceed- ings AAAI-94, pages 337-343, 1994.
  31. [Thornton and Sattar, 1999] J. Thornton and A. Sattar. On the behavior and application of constraint weighting. In Proceedings CP-99, pages 446-460, 1999.
  32. [Vossen et al., 1999] T. Vossen, M. Ball, A. Lotem, and D. Nau. On the use of integer programming models in AI planning. Proceedings IJCAI-99, pages 304-309, 1999. IJCAI
  33. [Voudouris and Tsang, 1996] C. Voudouris and E. Tsang. Partial constraint satisfaction problems and guided local search. In Proceedings PACT-96, pages 337-356, 1996.
  34. [Walser, 1999] J. Walser. Integer Optimization by Local Search. Springer-Verlag, 1999.
  35. [Wu and Wah, 2000] Z. Wu and W. Wah. An efficient global- search strategy in discrete Lagrangian methods for solv- ing hard satisfiability problems. In Proceedings AAAI-00, pages 310-315, 2000.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards