×

Combining VNS with constraint programming for solving anytime optimization problems. (English) Zbl 1160.90661

Summary: This paper presents an hybrid search method for solving on-line optimization problems that are modelled using the vcsp Valued Constraint Satisfaction Problems framework. To each constraint is associated a valuation representing the “cost to pay” when this constraint will be violated by a solution. Our method (VNS/LDS+CP) uses principles of VNS (Variable Neighborhood Search) and combines a partial tree search (Limited Discrepancy Search) with Constraint Propagation in order to compute local optima. Experiments on the CELAR benchmarks demonstrate significant improvements on other competing methods: LNS/CP/GR [L. Lobjois, M. Lemaitre, G. Verfaillie, Large neighbourhood search using constraint propagation and greedy reconstruction for valued csp resolution. in: Proceedings of the ECAI2000 Workshop on Modelling and Solving Problems with Constraints (2000)], another hybrid method using vcsps, and two standard versions of Simulated-Annealing [Y. H. Li, Directed annealing search in constraint satisfaction and optimization. Ph.D. thesis, Imperial College of Science, Department of Computing (1997)]: Quick and Medium. Moreover, VNS/LDS+CP clearly satisfies the key properties of anytime algorithms. Finally, VNS/LDS+CP has been successfully applied to a real-life on-line resource allocation problem in computer networks.

MSC:

90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Applegate, D.; Cook, W., A computational study of the job-shop scheduling problem, ORSA Journal on Computing, 3, 2, 149-156 (1991) · Zbl 0755.90039
[2] Apt, K., Principles of Constraint Programming (2003), Cambridge University Press · Zbl 1187.68132
[3] Aylett, R., Biundo, S., Ghallab, M., de Givry, S., Kearney, P., McCluskey, L., 2001. The planet roadmap on ai planning and scheduling. Technical Report 28439, Network of Excellence PLANET Project.; Aylett, R., Biundo, S., Ghallab, M., de Givry, S., Kearney, P., McCluskey, L., 2001. The planet roadmap on ai planning and scheduling. Technical Report 28439, Network of Excellence PLANET Project.
[4] Beck, J.C., Perron, L., 2000. Discrepancy-bounded depth-first search. In: Proceedings of CP-AI-OR’2000, Paderborn, Germany, pp. 1382-1387.; Beck, J.C., Perron, L., 2000. Discrepancy-bounded depth-first search. In: Proceedings of CP-AI-OR’2000, Paderborn, Germany, pp. 1382-1387.
[5] Bensana, E., Verfaillie, G., Agnèse, J.C., Bataille, N., Blumstein, D., 1996. Exact and approximate methods for the daily management of an earth observation satellite. In: Proceeding of the 4th International Symposium on Space Mission Operations and Ground Data Systems (SpaceOps-9-), Munich, Germany.; Bensana, E., Verfaillie, G., Agnèse, J.C., Bataille, N., Blumstein, D., 1996. Exact and approximate methods for the daily management of an earth observation satellite. In: Proceeding of the 4th International Symposium on Space Mission Operations and Ground Data Systems (SpaceOps-9-), Munich, Germany.
[6] Bensana, E.; Lemaıˆtre, M.; Verfaillie, G., Benchmark problems: Earth observation satellite management, Constraints, 4, 3, 293-299 (1999) · Zbl 0963.90507
[7] Bessière, C., Régin, J.-C., 1996. MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problem. In: CP’96, Cambridge, MA.; Bessière, C., Régin, J.-C., 1996. MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problem. In: CP’96, Cambridge, MA.
[8] Bistarelli, S.; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G.; Fargier, H., Semiring-based csps and valued csps: Frameworks, properties, and comparison, Constraints, 4, 3, 199-240 (1999) · Zbl 0946.68143
[9] Boddy, M., Dean, T.L., 1988. An analysis of time-dependent planning. In: AAAI 88, Twelfth National Conference on Artificial Intelligence, St. Paul, MN, pp. 49-54.; Boddy, M., Dean, T.L., 1988. An analysis of time-dependent planning. In: AAAI 88, Twelfth National Conference on Artificial Intelligence, St. Paul, MN, pp. 49-54.
[10] Boddy, M.; Dean, T. L., Deliberation scheduling for problem solving in time-constrained environments, Artificial Intelligence, 67, 245-295 (1994) · Zbl 0809.68103
[11] Boizumault, P.; David, P.; Djellab, H., Resource allocation in a mobile telephone network: A constructive repair algorithm, RAIRO Operations Research, 35, 2, 189-209 (2001) · Zbl 1014.90061
[12] Cabon, B.; de Givry, S.; Lobjois, L.; Schiex, T.; Warners, J. P., Radio link frequency assignment, Constraints, 4, 1, 79-89 (1999) · Zbl 1020.94500
[13] Dechter, R., Constraint Processing (2003), Morgan Kaufmann
[14] de Givry, S., 1998. Algorithmes d’Optimisation Sous Contraintes Étudiés Dans Un Cadre Temps Réel. Ph.D. thesis, École Nationale Supérieure de l’Aéronautique et de l’Espace, Toulouse, France.; de Givry, S., 1998. Algorithmes d’Optimisation Sous Contraintes Étudiés Dans Un Cadre Temps Réel. Ph.D. thesis, École Nationale Supérieure de l’Aéronautique et de l’Espace, Toulouse, France.
[15] de Givry, S., Hamadi, Y., Mattioli, J., Lemaitre, M., Verfaillie, G., Aggun, A., Gouachi, I., Benoist, T., Bourreau, E., Laburthe, F., Loudni, S., David, P., Bourgault, S., 2001. Towards an on-line optimisation framework. OLCP 2001, International Workshop on On-Line Combinatorial Problem Solving and Constraint Programming (at CP-2001), Paphos, Cyprus.; de Givry, S., Hamadi, Y., Mattioli, J., Lemaitre, M., Verfaillie, G., Aggun, A., Gouachi, I., Benoist, T., Bourreau, E., Laburthe, F., Loudni, S., David, P., Bourgault, S., 2001. Towards an on-line optimisation framework. OLCP 2001, International Workshop on On-Line Combinatorial Problem Solving and Constraint Programming (at CP-2001), Paphos, Cyprus.
[16] de Givry, S.; Larrosa, J.; Meseguer, P.; Schiex, T., Solving max-sat as weighted csp, (Proceeding of the 9th International Conference on Principles and Practice of Constraint Programming (CP’03) (2003), Springer-Verlag: Springer-Verlag Kinsale, Ireland), 363-376 · Zbl 1273.68368
[17] Fargier, H., Lang, J., Schiex, T., 1992. Selecting preferred solutions in fuzzy constraint satisfaction problems. In: Proceedings of 1st European Congress on Fuzzy and Intelligent Technologies (EUFIT).; Fargier, H., Lang, J., Schiex, T., 1992. Selecting preferred solutions in fuzzy constraint satisfaction problems. In: Proceedings of 1st European Congress on Fuzzy and Intelligent Technologies (EUFIT).
[18] Firby, R.J., 1987. An investigation into reactive planning in complex domains. In: AAAI 87, Eleventh National Conference on Artificial Intelligence, Seattle, WA, pp. 202-206.; Firby, R.J., 1987. An investigation into reactive planning in complex domains. In: AAAI 87, Eleventh National Conference on Artificial Intelligence, Seattle, WA, pp. 202-206.
[19] Focacci, F.; Laburthe, F.; Lodi, A., Local search and constraint programming, (Glover, F.; Kochenberger, G., Handbook on Metaheuristics (2002), Kluwer Academic Publishers) · Zbl 1137.90729
[20] Freuder, E.; Wallace, R., Partial constraint satisfaction, Artificial Intelligence, 58, 21-70 (1992)
[21] Gilbert, D.; Backofen, R.; Yap, R., Special issue on bioinformatics. Special issue on bioinformatics, Constraints: An International Journal, 6, 2-3 (2001)
[22] Ginsberg, M.; Harvey, W. D., Iterative broadening, Artificial Intelligence, 55, 367-383 (1992)
[23] Glover, F.; Laguna, M., Chapter: Tabu Search, (Modern Heuristic Techniques for Combinatorial Problems (1993), Blackwell Scientific Publishing), 70-141
[24] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers · Zbl 0930.90083
[25] Gornuejols, G.; Nemhausser, G. H.; Wolsey, L., Discrete location theory, chapter the uncapacitated facility location problem, Lecture Note in Artificial Intelligence, 1865, 119-171 (1990)
[26] Hansen, E. A.; Zilberstein, S., Monitoring and control of anytime algorithms: A dynamic programming approach, Artificial Intelligence, 126, 139-157 (2001) · Zbl 0969.68138
[27] Hansen, P.; Mladenović, N.; Perez-Brito, D., Variable neighborhood decomposition search, Journal of Heuristics, 7, 4, 335-350 (2001) · Zbl 1041.68623
[28] Haralick, R.; Elliott, G., Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence, 14, 263-313 (1980)
[29] Harvey, W.D., 1995. Non-systematic backtracking search. Ph.D. thesis, Stanford University.; Harvey, W.D., 1995. Non-systematic backtracking search. Ph.D. thesis, Stanford University.
[30] Harvey, W.D., Ginsberg, M.L., 1995. Limited discrepancy search. In: Mellish, C. (Ed.), IJCAI’95: Proceedings International Joint Conference, Montreal.; Harvey, W.D., Ginsberg, M.L., 1995. Limited discrepancy search. In: Mellish, C. (Ed.), IJCAI’95: Proceedings International Joint Conference, Montreal.
[31] Heras, F.; Larrosa, J., Intelligent variable orderings and re-orderings in dac-based solvers for wcsp, Journal of Heuristics, 12, 287-306 (2006) · Zbl 1125.90041
[32] Johnson, S.D., Trick, M., 1996. Second dimacs implementation challenge: Cliques, coloring and satisfiability. Discrete Mathematics and Theoretical Computer Science 26.; Johnson, S.D., Trick, M., 1996. Second dimacs implementation challenge: Cliques, coloring and satisfiability. Discrete Mathematics and Theoretical Computer Science 26. · Zbl 0875.68678
[33] Kirkpatrick, S., Optimization by simulated annealing: Quantitative studies, Journal of Statistical Physics, 34, 5, 1984 (1984)
[34] Kolen, A., 1994. A constraint satisfaction approach to the radio link frequency assignment problem. Technical Report 2.2.2, EUCLID CALMA project. Available from: <ftp://ftp.win.tue.nl/pub/techreports/CALMA/222.ps>; Kolen, A., 1994. A constraint satisfaction approach to the radio link frequency assignment problem. Technical Report 2.2.2, EUCLID CALMA project. Available from: <ftp://ftp.win.tue.nl/pub/techreports/CALMA/222.ps>
[35] Korf, R., 1996. Improved limited discrepancy search. In: Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96), Portland, OR, pp. 286-291.; Korf, R., 1996. Improved limited discrepancy search. In: Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96), Portland, OR, pp. 286-291.
[36] Koster, A.; van Hoesel, C.; Kolen, A., The partial constraint satisfaction problem: Facets and lifting theorems, Operations Research Letters, 23, 3-5, 89-97 (1998) · Zbl 0957.90095
[37] Laburthe, F., 2000. Choco: Implementing a cp kernel. In: CP00 Post Conference Workshop on Techniques for Implementing Constraint programming Systems (TRICS), Singapore.; Laburthe, F., 2000. Choco: Implementing a cp kernel. In: CP00 Post Conference Workshop on Techniques for Implementing Constraint programming Systems (TRICS), Singapore.
[38] Larrosa, J.; Meseguer, P.; Schiex, T., Maintaining reversible dac for solving max-csp, Artificial Intelligence, 107, 1, 149-163 (1999) · Zbl 0911.68064
[39] Li, Y.H., 1997. Directed Annealing Search in Constraint Satisfaction and Optimization. Ph.D. thesis, Imperial College of Science, Department of Computing.; Li, Y.H., 1997. Directed Annealing Search in Constraint Satisfaction and Optimization. Ph.D. thesis, Imperial College of Science, Department of Computing.
[40] Lobjois, L., 1999. Problèmes d’Optimisation sous Contraintes: vers la Conception Automatique de Méthodes de Résolution Adaptées à Chaque Instance. Ph.D. thesis, École Nationale Supérieure de l’Aéronautique et de l’Espace, Toulouse, France.; Lobjois, L., 1999. Problèmes d’Optimisation sous Contraintes: vers la Conception Automatique de Méthodes de Résolution Adaptées à Chaque Instance. Ph.D. thesis, École Nationale Supérieure de l’Aéronautique et de l’Espace, Toulouse, France.
[41] Lobjois, L., Lemaitre, M., Verfaillie, G., 2000. Large neighbourhood search using constraint propagation and greedy reconstruction for valued csp resolution. In: Proceedings of the ECAI2000 Workshop on Modelling and Solving Problems with Constraints.; Lobjois, L., Lemaitre, M., Verfaillie, G., 2000. Large neighbourhood search using constraint propagation and greedy reconstruction for valued csp resolution. In: Proceedings of the ECAI2000 Workshop on Modelling and Solving Problems with Constraints.
[42] Loudni, S.; Boizumault, P., Solving constraint optimization problems in anytime contexts, (Gottlob, G.; Walsh, T., IJCAI-03: Proceedings of the 18th International Joint Conference on Artificial Intelligence (2003), Morgan Kaufmann: Morgan Kaufmann Acapulco, Mexico), 251-256
[43] Loudni, S.; Boizumault, P.; David, P., On-line resources allocation for ATM networks with rerouting, Computers And Operations Research, 33, 2891-2917 (2006) · Zbl 1086.90502
[44] Meseguer, P., Larrosa, J., Sánchez, M., 2001. Lower bounds for non-binary constraint optimization problems. In: Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP 2001), Paphos, Cyprus, pp. 317-331.; Meseguer, P., Larrosa, J., Sánchez, M., 2001. Lower bounds for non-binary constraint optimization problems. In: Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP 2001), Paphos, Cyprus, pp. 317-331. · Zbl 1067.68656
[45] Minton, S.; Johnston, M.; Philips, A.; Laird, P., Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence, 58, 161-205 (1992) · Zbl 0782.90054
[46] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers and Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119
[47] Musliner, D. J.; Durfee, E. H.; Shin, K. G., Circa: A cooperative intelligent real-time control architecture, IEEE Trans. Systems, Man, and Cybernetics, 23, 6, 1993 (1993)
[48] Pearl, J., Probabilistic inference in intelligent systems, Networks of Plausible Inference (1998), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[49] Pos, A., 1993. Time-constrained model-based diagnosis. Ph.D. thesis, Department of Computer Science, University of Twente, The Netherlands.; Pos, A., 1993. Time-constrained model-based diagnosis. Ph.D. thesis, Department of Computer Science, University of Twente, The Netherlands.
[50] Rousseau, L. M.; Gendreau, M.; Pesant, G., Using constraint programming based operators to solve the vehicle routing problem with time windows, Journal of Heuristics, 8, 43-58 (2001) · Zbl 1073.90056
[51] Sandholm, T., 1999. An algorithm for optimal winner determination in combinatorial auctions. In: IJCAI’99: Proceedings International Joint Conference on Artificial Intelligence, pp. 342-347.; Sandholm, T., 1999. An algorithm for optimal winner determination in combinatorial auctions. In: IJCAI’99: Proceedings International Joint Conference on Artificial Intelligence, pp. 342-347.
[52] Schiex, T., 1992. Possibilistic constraint satisfaction problems or “How to handle soft constraints?” In: 8th International Conference on Uncertainty in Artificial Intelligence, Stanford.; Schiex, T., 1992. Possibilistic constraint satisfaction problems or “How to handle soft constraints?” In: 8th International Conference on Uncertainty in Artificial Intelligence, Stanford.
[53] Schiex, T., Fargier, H., Verfaillie, G., 1995. Valued constraint satisfaction problems: Hard and easy problems. In: Mellish, C. (Ed.), IJCAI’95: Proceedings International Joint Conference on Artificial Intelligence, Montreal, Canada.; Schiex, T., Fargier, H., Verfaillie, G., 1995. Valued constraint satisfaction problems: Hard and easy problems. In: Mellish, C. (Ed.), IJCAI’95: Proceedings International Joint Conference on Artificial Intelligence, Montreal, Canada. · Zbl 0940.68132
[54] Shaw, P., 1998. Using constraint programming and local search methods to solve vehicle routing problems. In: Proceedings of the International Conference on Principles And Practice of Constraint Programming (CP-98)431, Pisa, Italy, pp. 417-431.; Shaw, P., 1998. Using constraint programming and local search methods to solve vehicle routing problems. In: Proceedings of the International Conference on Principles And Practice of Constraint Programming (CP-98)431, Pisa, Italy, pp. 417-431.
[55] Voudouris, C., Tsang, E. Solving the radio link frequency assignment problem using guided local search. In: Proceedings of NATO symposium on Frequency Assignment, Sharing and Conservation in Systems, Aalborg, Denmark.; Voudouris, C., Tsang, E. Solving the radio link frequency assignment problem using guided local search. In: Proceedings of NATO symposium on Frequency Assignment, Sharing and Conservation in Systems, Aalborg, Denmark. · Zbl 0937.90094
[56] Walsh, T., 1997. Depth-bounded discrepancy search. In: IJCAI’97: Proceedings International Joint Conference on Artificial Intelligence, Nagoya, Japan, pp. 202-206.; Walsh, T., 1997. Depth-bounded discrepancy search. In: IJCAI’97: Proceedings International Joint Conference on Artificial Intelligence, Nagoya, Japan, pp. 202-206.
[57] Wong, Z.; Crowcroft, J., Quality of service routing for supporting multimedia applications, IEEE Journal on Selected Area in Communications, 17, 7, 1228-1234 (1996)
[58] Zhang, W., Configuration landscape analysis and backbone guided local search. Part I: Satisfiability and maximum satisfiability, Artificial Intelligence, 158, 1-26 (2004) · Zbl 1085.68678
[59] Zilberstein, S., Using anytime algorithms in intelligent systems, AI Magazine, 17, 3, 73-83 (1996)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.