A Meta-heuristic for Subset Problems
- 219 Downloads
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.
KeywordsProblem Class Lookup Table Constraint Program Constraint Satisfaction Problem Boolean Variable
Unable to display preview. Download preview PDF.
- 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.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
- 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.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.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.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
- 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.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.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.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.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.S. Minton. Automatically configuring constraint satisfaction programs: A case study. Constraints 1(1–2):7–43, 1996.Google Scholar
- 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.E.P.K. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.Google Scholar
- 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.P. Van Hentenryck. The OPL Optimization Programming Language. The MIT Press, 1999.Google Scholar