Advertisement

A Meta-heuristic for Subset Problems

  • Pierre Flener
  • Brahim Hnich
  • Zeynep Kiziltan
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 1990)

Abstract

In constraint solvers, variable and value ordering heuristics are used to finetune the performance of the underlying search and propagation algorithms. However, few guidelines have been proposed for when to choose what heuristic among the wealth of existing ones. Empirical studies have established that this would be very hard, as none of these heuristics outperforms all the other ones on all instances of all problems (for an otherwise fixed solver). The best heuristic varies not only between problems, but even between different instances of the same problem. Taking heed of the popular dictum “If you can’t beat them, join them!” we devise a practical meta-heuristic that automatically chooses, at run-time, the “best” available heuristic for the instance at hand. It is applicable to an entire class of NP-complete subset problems.

Keywords

Problem Class Lookup Table Constraint Program Constraint Satisfaction Problem Boolean Variable 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    J.E. Borrett, E.P.K. Tsang, and N.R. Walsh. Adaptive constraint satisfaction: The quickest-first principle. In Proc. of ECAI’96, pp. 160–164. JohnWiley & Sons, 1996.Google Scholar
  2. 2.
    M. Carlsson, G. Ottosson, and B. Carlson. An open-ended finite domain constraint solver. In: H. Glaser, P. Hartel, and H. Kuchen (eds), Proc. of PLILP’97, pp. 191–206. LNCS 1292. Springer-Verlag, 1997.Google Scholar
  3. 3.
    T. Ellman, J. Keane, A. Banerjee, and G. Armhold. A transformation system for interactive reformulation of design optimization strategies. Research in Engineering Design 10(1):30–61, 1998.CrossRefGoogle Scholar
  4. 4.
    P. Flener, H. Zidoum, and B. Hnich. Schema-guided synthesis of constraint logic programs. In Proc. of ASE’98, pp. 168–176. IEEE Computer Society Press, 1998.Google Scholar
  5. 5.
    P. Flener, B. Hnich, and Z. Kiziltan. Towards schema-guided compilation of set constraint programs. In B. Jayaraman and G. Rossi (eds), Proc. of DPS’99, pp. 59–66. Tech. Rep. 200, Math. Dept., Univ. of Parma, Italy, 1999.Google Scholar
  6. 6.
    P. Flener, B. Hnich, and Z. Kiziltan. Compiling high-level type constructors in constraint programming. In: I.V. Ramakrishnan (ed), Proc. of PADL’01. LNCS, this volume. Springer-Verlag, 2001.Google Scholar
  7. 7.
    P.A. Geelen. Dual viewpoint heuristics for binary constraint satisfaction problems. In Proc. of ECAI’92, pp. 31–35. John Wiley & Sons, 1992.Google Scholar
  8. 8.
    C. Gervet. Interval propagation to reason about sets: Definition and implementation of a practical language. Constraints 1(3):191–244, 1997.zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    J.M. Gratch and S.A. Chien. Adaptive problem-solving for large scale scheduling problems: A case study. J. of Artificial Intelligence Research 4:365–396, 1996.Google Scholar
  10. 10.
    B. Hnich and Z. Kiziltan. Generating programs for k-subset problems. In P. Alexander (ed), Proc. of the ASE’99 Doctoral Symposium. 1999.Google Scholar
  11. 11.
    B. Hnich, Z. Kiziltan, and P. Flener. A meta-heuristic for subset decision problems. In: K.R. Apt, E. Monfroy, and F. Rossi (eds), Proc. of the 2000 ERCIM/CompuLog Workshop on Constraint Programming. 2000.Google Scholar
  12. 12.
    Z. Kiziltan, P. Flener, and B. Hnich. A labelling heuristic for subset problems. Submitted for review. Available via http://www.dis.uu.se/~pierref/astra/.
  13. 13.
    Z. Kiziltan and P. Flener. An adaptive meta-heuristic for subset problems. Submitted for review. Available via http://www.dis.uu.se/~pierref/astra/.
  14. 14.
    S. Minton. Automatically configuring constraint satisfaction programs: A case study. Constraints 1(1–2):7–43, 1996.Google Scholar
  15. 15.
    T. Müller. Solving set partitioning problems with constraint programming. In Proc. of PAPPACT’98, pp. 313–332. The Practical Application Company, 1998.Google Scholar
  16. 16.
    E.P.K. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.Google Scholar
  17. 17.
    E.P.K. Tsang, J.E. Borrett, and A.C.M. Kwan. An attempt to map the performance of a range of algorithm and heuristic combinations. In Proc. of AISB’95, pp. 203–216. IOS Press, 1995.Google Scholar
  18. 18.
    P. Van Hentenryck. The OPL Optimization Programming Language. The MIT Press, 1999.Google Scholar
  19. 19.
    C.P. Williams and T. Hogg. Exploiting the deep structure of constraint problems. Artificial Intelligence 70:73–117, 1994.zbMATHCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Pierre Flener
    • 1
  • Brahim Hnich
    • 1
  • Zeynep Kiziltan
    • 1
  1. 1.Computer Science Division, Department of Information ScienceUppsala UniversityUppsalaSweden

Personalised recommendations