×

zbMATH — the first resource for mathematics

Weight-based heuristics for constraint satisfaction and combinatorial optimization problems. (English) Zbl 1263.90131
Summary: We propose mechanisms to improve instantiation heuristics by incorporating weighted factors on variables. The proposed weight-based heuristics are evaluated on several tree search methods such as chronological backtracking and discrepancy-based search for both constraint satisfaction and optimization problems. Experiments are carried out on random constraint satisfaction problems, car sequencing problems, and jobshop scheduling with time-lags, considering various parameter settings and variants of the methods.The results show that weighting mechanisms reduce the tree size and then speed up the solving time, especially for the discrepancy-based search method.
MSC:
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
Software:
YIELDS
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Artigues, C., Huguet, M.-J., Lopez, P.: Generalized disjunctive constraint propagation for solving the job shop problem with time lags. Eng. Appl. Artif. Intell. 24(2), 220–231 (2011)
[2] Beck, J.C., Prosser, P., Wallace, R.: Variable ordering heuristics show promise. In: Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming (CP’04), pp. 711–715. Toronto, Canada (2004)
[3] Bessière, C., Régin, J.-C.: MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In: Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP’96), pp. 61–75. Cambridge, Massachusetts, USA (1996)
[4] Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: Proceedings of the 16th European Conference on Artificial Intelligence (ECAI’04), pp. 146–150. Valencia, Spain, August (2004)
[5] Brucker, P., Hilbig, T., Hurink, J.: A branch and bound algorithm for a single machine scheduling with positive and negative time-lags. Discrete Appl. Math. 94, 77–99 (1999) · Zbl 0932.68006
[6] Caumond, A., Lacomme, P., Tchernev, N.: A memetic algorithm for the job-shop with time-lags. Comput. Oper. Res. 35, 2331–2356 (2008) · Zbl 1177.90147
[7] CSPLib: http//csplib.org
[8] Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003) · Zbl 1057.68114
[9] Frost, D.H., Bessière, C., Dechter, R., Régin, J.C.: Random uniform CSP generators. http://www.lirmm.fr/\(\sim\)bessiere/generator.html (1996)
[10] Gacias, B., Artigues, C., Lopez, P.: Parallel machine scheduling with precedence constraints and setup times. Comput. Oper. Res. 37(12), 2141–2151 (2010) · Zbl 1231.90192
[11] Gent, I.P.: Two results on car-sequencing problems. Research report 02-1998, APES, University of Strathclyde, UK (1998)
[12] Grimes, D., Wallace, R.J.: Learning from failure in constraint satisfaction search. In: AAAI Workshop on Learning for Search, Boston, Massachusetts, USA (2006)
[13] Haralick, R., Elliot, G.: Increasing tree search efficiency for constraint satisfaction problems. Artif. Intell. 14, 263–313 (1980)
[14] Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI’95), vol. 1, pp. 607–615. Montréal, Québec, Canada (1995)
[15] Van Hentenryck, P., Simonis, H., Dincbas, M.: Constraint satisfaction using constraint logic programming. Artif. Intell. 58, 113–159 (1992) · Zbl 0782.68028
[16] Ben Hmida, A., Haouari, M., Huguet, M.-J., Lopez, P.: Discrepancy search for the flexible job shop problem. Comput. Oper. Res. 37(12), 2192–2201 (2010) · Zbl 1231.90176
[17] Van Hoeve, W.J., Pesant, G., Rousseau, L.-M., Sabharwal, A.: New filtering algorithms for combinations of among constraints. Constraints 14(2), 273–292 (2009) · Zbl 1186.68552
[18] Hooker, J.: Logic-based Methods for Optimization: Combining Optimization and Constraint Satisfaction. Wiley, New York (2000) · Zbl 0974.90001
[19] Hurink, J., Keuchel, J.: Local search algorithms for a single-machine scheduling problem with positive and negative time-lags. Discrete Appl. Math. 112, 179–197 (2001) · Zbl 1010.90023
[20] Karoui, W., Huguet, M.-J., Lopez, P., Naanaa, W.: YIELDS: a yet improved limited discrepancy search for CSPs. In: Proceedings of the 4th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR’07), LNCS 4510, Springer, pp. 99–111. Brussels, Belgium (2007) · Zbl 1214.68358
[21] Korf, R.E.: Improved limited discrepancy search. In: Proceedings of the 13th National Conference on Artificial Intelligence (AAAI’96) and the 8th Innovative Applications of Artificial Intelligence Conference (IAAI’96), pp. 286–291. Portland, Oregon, USA (1996)
[22] Lacomme, P.: http://www.isima.fr/\(\sim\)lacomme/Job_Shop_TL.html
[23] Lecoutre, C., Sais, L., Tabary, S., Vidal, V.: Last conflict based reasoning. In: Proceedings of the 17th European Conference on Artificial Intelligence (ECAI’06), pp. 133–137. Trento, Italy (2006)
[24] Lecoutre, C., Sais, L., Vion, J.: Using SAT encodings to derive CSP value ordering heuristics. JSAT 1, 69–186 (2007) · Zbl 1147.68714
[25] Milano, M., Roli, A.: On the relation between complete and incomplete search: an informal discussion. In: Proceedings of the 4th International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR’02), pp. 237–250. Le Croisic, France (2002)
[26] Neumann, K., Schwindt, C., Zimmermann, J.: Project Scheduling with Time Windows and Scarce Resources. Springer (2002) · Zbl 1059.90001
[27] Prcovic, N., Neveu, B.: Ensuring a relevant visiting order of the leaf nodes during a tree search. In: Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming (CP’99), LNCS 1713, Springer, pp. 361–374. Alexandria, Virginia, USA (1999)
[28] Régin, J.-C., Puget, J.-F.: A filtering algorithm for global sequencing constraints. In: Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming (CP’97), pp. 32–46 (1997)
[29] Sabin, D., Freuder, E.C.: Contradicting conventional wisdom in constraint satisfaction. In: Proceedings of the 2nd Workshop on Principles and Practices of Constraint Programming (PPCP’94), LNCS 874, Springer, pp. 10–20. Rosario, Orcas Island, Washington, USA (1994)
[30] Smith, B.: Succeed-first or fail-first: a case study in variable and value ordering heuristics. In: Proceedings of the 3rd Conference on the Practical Applications of Constraint Technology (PACT’97), pp. 321–330. London, UK (1997)
[31] Solnon, C., Cung, V.D., Nguyen, A., Artigues, C.: The car sequencing problem: overview of state-of-the-art methods and industrial case-study of the ROADEF’05 challenge problem. Eur. J. Oper. Res. 191(3), 912–927 (2008) · Zbl 1156.90323
[32] Tsang, E.: Foundations of Constraint Satisfaction. Academic Press Ltd, London (1993)
[33] Walsh, T.: Depth-bounded discrepancy search. In: Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI’97), vol. 2, pp. 1388–1395. Nagoya, Japan (1997)
[34] Wikum, E.D., Llewellyn, D.C., Nemhauser, G.L.: One-machine generalized precedence constrained scheduling problems. Oper. Res. Lett. 16(2), 87–99 (1994) · Zbl 0823.90066
[35] Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif. Intell. 171, 514–534 (2007) · Zbl 1168.68554
[36] Zhang, Y., Yap, R.H.C.: Making AC-3 an optimal algorithm. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI’01), pp. 316–321. Seattle, Washington, USA (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.