{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T04:10:01Z","timestamp":1752379801247,"version":"3.41.2"},"reference-count":66,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2003,1]]},"DOI":"10.1023\/a:1021902812784","type":"journal-article","created":{"date-parts":[[2003,3,21]],"date-time":"2003-03-21T18:56:29Z","timestamp":1048272989000},"page":"9-39","source":"Crossref","is-referenced-by-count":17,"title":["Current Approaches for Solving Over-Constrained Problems"],"prefix":"10.1007","volume":"8","author":[{"given":"Pedro","family":"Meseguer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noureddine","family":"Bouhmala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taoufik","family":"Bouzoubaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Morten","family":"Irgens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mart\u00ed","family":"S\u00e1nchez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"5112284_CR1","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1287\/mnsc.37.1.98","volume":"37","author":"D. A. Abramson","year":"1991","unstructured":"Abramson, D. A. (1991). Constructing school timetables using simulated annealing: Sequential and parallel algorithms. Management Science, 37(1): 98\u2013113.","journal-title":"Management Science"},{"key":"5112284_CR2","unstructured":"Affane, M.-S., & Bennaceu, H. (1998). A weight are consistency technique for Max-CSP. In Proc. of ECAI-98, pages 209\u2013213."},{"key":"5112284_CR3","doi-asserted-by":"crossref","unstructured":"Alvarez-Valdes, R., Martin, G., & Tamarit, J. M. (1996). Constructing good solutions for the Spanish school timetabling problem. Journal of the Operational Research Society, 1203\u20131215.","DOI":"10.1057\/jors.1996.149"},{"key":"5112284_CR4","doi-asserted-by":"crossref","unstructured":"Belegundu, A. D., Murthy, D. V., Salagame, & Constant, E. W. (1994). Multi-objective optimization of laminated ceramic composites using genetic algorithms. In Fifth AIAA\/USAF\/NASA Symposium on Multidisciplinary Analysis and Optimization, Paper 84-4363-CP, pages 1015\u20131022.","DOI":"10.2514\/6.1994-4363"},{"issue":"3","key":"5112284_CR5","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1023\/A:1026488509554","volume":"4","author":"E. Bensana","year":"1999","unstructured":"Bensana, E., Lemaitre, M., & Verfaillie, G. (1999). Earth observation satellite management. Constraints, 4(3): 293\u2013299.","journal-title":"Constraints"},{"key":"5112284_CR6","unstructured":"Bistarelli, S., Montanari, U., & Rossi, F. (1995). Constraint solving over semirings. In Proc. IJCAI-95, pages 624\u2013630."},{"key":"5112284_CR7","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1023\/A:1026441215081","volume":"4","author":"S. Bistarelli","year":"1999","unstructured":"Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaille, G., & Fargier, H. (1999). Semiring-based CSPs and valued CSPs: Frameworks, properties and comparison. Constraints, 4: 199\u2013240.","journal-title":"Constraints"},{"key":"5112284_CR8","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01807506","volume":"5","author":"A. Borning","year":"1992","unstructured":"Borning, A., Freeman-Benson, B., & Wilson, M. (1992). Constraint hierarchies. Lisp and Symbolic Computation, 5: 223\u2013270.","journal-title":"Lisp and Symbolic Computation"},{"issue":"1","key":"5112284_CR9","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1023\/A:1009812409930","volume":"4","author":"B. Cabon","year":"1999","unstructured":"Cabon, B., De Givry, S., Lobjois, L., Schiex, T., & Warners, J. (1999). Radio link frequency assignment. Constraints, 4(1): 79\u201389.","journal-title":"Constraints"},{"key":"5112284_CR10","unstructured":"Cabon, B., Verfaillie, G., Martinez, D., & Bourret, P. (1996). Using mean field methods for boosting backtrack search in constraint satisfaction problems. In Proc. of ECAI-96, pages 165\u2013169."},{"key":"5112284_CR11","doi-asserted-by":"crossref","unstructured":"Cabon, B., Givry, S., & Verfaillie, G. (1998). Anytime lower bounds for constraint violation minimization problems. In Proc. of CP-98, pages 117\u2013131.","DOI":"10.1007\/3-540-49481-2_10"},{"key":"5112284_CR12","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0305-0548(96)00032-9","volume":"24","author":"P. Chu","year":"1997","unstructured":"Chu, P., & Beasley, J. E. (1997). Genetic algorithms for the generalized assignment problem. Computers and Operations Research, 24: 17\u201323.","journal-title":"Computers and Operations Research"},{"key":"5112284_CR13","series-title":"Technical Report","volume-title":"A genetic algorithm, to solve the timetable problem","author":"A. Colorni","year":"1992","unstructured":"Colorni, A., Dorigo, & Maniezzo (1992). A genetic algorithm, to solve the timetable problem. Technical Report 90.060, Politecnico di Milano, Italy."},{"key":"5112284_CR14","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/0377-2217(94)90009-4","volume":"76","author":"D. Costa","year":"1994","unstructured":"Costa, D. (1994). A tabu search algorithm for computing an operational timetable. European Journal of Operational Research, 76: 98\u2013110.","journal-title":"European Journal of Operational Research"},{"key":"5112284_CR15","unstructured":"Davenport, A., Tsang, E., Wang, C., & Zhu, K. (1994). GENET: A connectionist architecture for solving constraint satisfaction problems by iterative improvement. In Proc. of AAAI-94, pages 325\u2013330."},{"key":"5112284_CR16","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF00132735","volume":"6","author":"D. Dubois","year":"1996","unstructured":"Dubois, D., Fargier, H., & Prade, H. (1996). Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty. Applied Intelligence, 6: 287\u2013309.","journal-title":"Applied Intelligence"},{"key":"5112284_CR17","doi-asserted-by":"crossref","unstructured":"Eiben, A. E., Raua, P.-E., & Ruttkay, Zs. (1994). Solving constraint satisfaction problem using genetic algorithms. In Proc. 1st IEEE Conference on Evolutionary Computing, pages 543\u2013547.","DOI":"10.1109\/ICEC.1994.350002"},{"key":"5112284_CR18","first-page":"97","volume":"747","author":"H. Fargier","year":"1993","unstructured":"Fargier, H., & Lang, J. (1993). Uncertainty in constraint satisfaction problems: A probabilistic approach. In Proc. ECSQARU-93, In Vol. 747 of LNCS, pages 97\u2013104.","journal-title":"Proc. ECSQARU-93"},{"key":"5112284_CR19","unstructured":"Fargier, H. (1994). Problemes de satisfaction de constraintes flexibles: Application a l'ordonnancement de production. Ph.D. Thesis, Univ. Paul Sabatier, Toulouse, France."},{"key":"5112284_CR20","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0004-3702(92)90004-H","volume":"58","author":"E. Freuder","year":"1992","unstructured":"Freuder, E., & Wallace, R. (1992). Partial constraint satisfaction. Artificial Intelligence, 58: 21\u201371.","journal-title":"Artificial Intelligence"},{"key":"5112284_CR21","doi-asserted-by":"crossref","unstructured":"Givry, S., Verfaillie, G., & Schiex, T. (1997). Bounding the optimum of constraint optimization problems. In Proc. of CP-97, pages 405\u2013419.","DOI":"10.1007\/BFb0017456"},{"key":"5112284_CR22","volume-title":"Genetic Algorithms in Search, Optimization and Machine Learning","author":"D. E. Goldberg","year":"1989","unstructured":"Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addition-Wesley Publishing Co., Reading, MA."},{"key":"5112284_CR23","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0004-3702(80)90051-X","volume":"14","author":"R. M. Haralick","year":"1980","unstructured":"Haralick, R. M., & Elliot, G. L. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14: 263\u2013313.","journal-title":"Artificial Intelligence"},{"key":"5112284_CR24","doi-asserted-by":"crossref","unstructured":"Holland, J. H. (1992). Adaptation in Natural and Artificial Systems, 2nd ed. MITPress.","DOI":"10.7551\/mitpress\/1090.001.0001"},{"issue":"4","key":"5112284_CR25","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1177\/003754979406200405","volume":"62","author":"A. Homaifar","year":"1994","unstructured":"Homaifar, A., Lai, S. H. Y., & Qi, X. (1994). Constrained optimization via genetic algorithms. Simulation, 62(4): 242\u2013254.","journal-title":"Simulation"},{"key":"5112284_CR26","series-title":"Technical Report Illi GAI Report","volume-title":"Multi-objective optimization using the niched pareto genetic algorithm","author":"J. Horn","year":"1993","unstructured":"Horn, J., & Nafpliotis, N. (1993). Multi-objective optimization using the niched pareto genetic algorithm. Technical Report Illi GAI Report 93005, University of Illinois at Urbana Champaign."},{"key":"5112284_CR27","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/0377-2217(92)90360-L","volume":"61","author":"L. Kang","year":"1992","unstructured":"Kang, L., & White, G. M. (1992). A logic approach to the resolution of constraints in timetabling. European Journal of Operational Research, 61: 306\u2013317.","journal-title":"European Journal of Operational Research"},{"issue":"4598","key":"5112284_CR28","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelat, C., & Vicci, M. (1983). Optimization by simulated annealing. Science, 220(4598): 671\u2013680.","journal-title":"Science"},{"key":"5112284_CR29","doi-asserted-by":"crossref","unstructured":"Koster, A. M., Hoesel, C. P., & Kolen, A. W. Optimal solutions for a frequency assignment problem via tree-decomposition. In Vol. 1665 of LNCS, pages 338-349.","DOI":"10.1007\/3-540-46784-X_32"},{"key":"5112284_CR30","unstructured":"Kumar, V. (1992). Algorithms for constraint satisfaction problems: A survey. AI Magazine, Spring 1992, pages 32\u201344."},{"key":"5112284_CR31","unstructured":"Lanfear, T. A. (1989). Graph theory and radio link frequency assignment problems. Technical Report, NATO, Allied Radio Frequency."},{"key":"5112284_CR32","doi-asserted-by":"crossref","unstructured":"Larrosa, J. (2000). Boosting search with variable elimination. In Proc. CP-00, pages 291\u2013305.","DOI":"10.1007\/3-540-45349-0_22"},{"key":"5112284_CR33","doi-asserted-by":"crossref","unstructured":"Larrosa, J., & Meseguer, P. (1996). Exploiting the use of DAC in Max-CSP. In Proc. of CP-96, pages 308\u2013322.","DOI":"10.1007\/3-540-61551-2_83"},{"key":"5112284_CR34","doi-asserted-by":"crossref","unstructured":"Larrosa, J., & Meseguer, P. (1999). Partition-based lower bound for max-CSP. In Proc. of CP-99, pages 303\u2013315.","DOI":"10.1007\/978-3-540-48085-3_22"},{"issue":"1","key":"5112284_CR35","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0004-3702(98)00108-8","volume":"107","author":"J. Larrosa","year":"1999","unstructured":"Larrosa, J., Meseguer, P., & Schiex, T. (1999). Maintaining reversible DAC for max-CSP. Artificial Intelligence, 107(1): 149\u2013163.","journal-title":"Artificial Intelligence"},{"key":"5112284_CR36","doi-asserted-by":"crossref","unstructured":"Lau, H. C. (1996). A new approach for weighted constraint satisfaction: Theoretical and computational results. In Proc. of CP-96, pages 323\u2013337.","DOI":"10.1007\/3-540-61551-2_84"},{"key":"5112284_CR37","unstructured":"Lemaitre, M., & Verfaillie, G. (1997). Daily management of an earth observation satellite: comparairon of ILOG solver with dedicated algorithms for Valued CSP. In Proc. of the Third ILOG International Users Meeting. Paris, France."},{"key":"5112284_CR38","unstructured":"Li, Y. H. (1997). Directed annealing search in constraint satisfaction and optimization. Ph.D. Thesis, Imperial College of Science, Department of Computing."},{"key":"5112284_CR39","unstructured":"Minton, S., Johnson, M., Philips, A., & Laird, P. (1990). Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method. In Proc. of AAAI-90, pages 17\u201324."},{"key":"5112284_CR40","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0004-3702(92)90007-K","volume":"58","author":"S. Minton","year":"1992","unstructured":"Minton, S., Johnson, M., Philips, A., & Laird, P. (1992). Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 58: 161\u2013205.","journal-title":"Artificial Intelligence"},{"key":"5112284_CR41","unstructured":"Morris, P. (1993). The breakout method for escaping from local minima. In Proc. of AAAI-93, pages 40\u201345."},{"issue":"8","key":"5112284_CR42","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1145\/361082.361092","volume":"17","author":"G. A. Neufeld","year":"1974","unstructured":"Neufeld, G. A., & Tartar, J. (1974). Graph coloring conditions for the existence of solutions to the timetable problem. Communications of the ACM, 17(8): 450\u2013453.","journal-title":"Communications of the ACM"},{"key":"5112284_CR43","volume-title":"The integration of evolutionary and adaptive computing technologies with product\/ system design and realization","author":"I. Parmee","year":"1989","unstructured":"Parmee, I. (1989). The integration of evolutionary and adaptive computing technologies with product\/ system design and realization. Springer-Verlag, Plymouth, UK."},{"key":"5112284_CR44","doi-asserted-by":"crossref","unstructured":"R\u00e9gin, J. C., Petit, T., Bessi\u00e9re, C., & Puget, J. F., (2000). An original constraint based approach for solving over constrained problems. In Proc. CP-00, pages 543\u2013548.","DOI":"10.1007\/3-540-45349-0_46"},{"key":"5112284_CR45","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1111\/j.1540-5915.1985.tb01479.x","volume":"16","author":"R. Rosenthal","year":"1985","unstructured":"Rosenthal, R. (1985). Principles of multiobjective optimization. Decision Sciences, 16: 133\u2013152.","journal-title":"Decision Sciences"},{"key":"5112284_CR46","unstructured":"Ruttkay, Z., Eiben, A. E., & Raue, P. E. (1995). Improving the performance of GAs on a GA-hard CSP. In Proceedings, CP95 Workshop on Studying and Solving Really Hard Problems, pages 157\u2013171."},{"key":"5112284_CR47","unstructured":"Schaerf, A. (1996). Tabu search techniques for large high-school timetabling problems. In Proc. of ECAI-96, pages 634\u2013639."},{"key":"5112284_CR48","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1023\/A:1006576209967","volume":"13","author":"A. Schaerf","year":"1996","unstructured":"Schaerf, A. (1996). A survey of automated timetabling. Artificial Intelligence Review, 13: 87\u2013127.","journal-title":"Artificial Intelligence Review"},{"key":"5112284_CR49","unstructured":"Schiex, T., Verfaille, G., & Fargier, H. (1995). Valued constraint satisfaction problems: Hard and easy problems. In Proc. IJCAI-95, pages 631\u2013637."},{"key":"5112284_CR50","doi-asserted-by":"crossref","unstructured":"Schiex, T. (2000). Arc consistency for soft constraints. In Proc. CP-2000, pages 411\u2013424.","DOI":"10.1007\/3-540-45349-0_30"},{"key":"5112284_CR51","unstructured":"Srinivas, N., & Deb, K. (1993). Multi-objective optimization using nondominated sorting in genetic algorithms, Technical Report, Department of Mechanical Engineering, Indian Institute of Technology, Kanpur."},{"key":"5112284_CR52","unstructured":"Tsang, E. (1993). Foundations of Constraint Satisfaction. Academic Press."},{"key":"5112284_CR53","unstructured":"Tsang, E., Wang, C., Davenport, A., Voudouris, C., & Lau, T. (1999). A family of stochastic methods for constraint satisfaction and optimization. In The First International Conference on the Practical Application of Constraint Technologies and Logic Programming, London."},{"key":"5112284_CR54","first-page":"269","volume-title":"Multicriteria Analysis","author":"E. L. Ulungu","year":"1997","unstructured":"Ulungu, E. L., Teghem, J., & Fortemps, P. H. (1997). Heuristics for multi-objective combinatorial optimization by simulated annealing. In Gu, J., Chen, G., Wei, Q., & Wang, S. (eds.), Multicriteria Analysis, pages 269\u2013278. Springer-Verlag, Berlin."},{"issue":"4","key":"5112284_CR55","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/(SICI)1099-1360(199907)8:4<221::AID-MCDA247>3.0.CO;2-O","volume":"8","author":"E. L. Ulungu","year":"1999","unstructured":"Ulungu, E. L., Teghem, J., Fortemps, P. H., & Tuyttens, D. (1999). MOSA method: A tool for solving multi-objective combinatorial optimization problems. Journal of Multi-Criteria Decision Analysis, 8(4): 221\u2013236.","journal-title":"Journal of Multi-Criteria Decision Analysis"},{"key":"5112284_CR56","doi-asserted-by":"crossref","first-page":"1044","DOI":"10.1057\/palgrave.jors.2600569","volume":"49","author":"E. L. Ulungu","year":"1998","unstructured":"Ulungu, E. L., Teghem, J., & Ost, C. (1998). Interactive simulate annealing in a multi-objective framework: Application to an industrial problem. J. Oper. Res. Soc., 49: 1044\u20131050.","journal-title":"J. Oper. Res. Soc."},{"key":"5112284_CR57","unstructured":"Verfaille, G., & Schiex, T. (1994). Solution reuse in dynamic constraint satisfaction problems. In Proc. of AAAI-94, pages 307\u2013312."},{"key":"5112284_CR58","unstructured":"Verfaillie, G., Lemaitre, M., & Schiex, T. (1996). Russian doll search for solving constraint satisfaction problems. In Proc. of AAAI-96, pages 181\u2013187."},{"key":"5112284_CR59","doi-asserted-by":"crossref","unstructured":"Wah, B., & Wang, T. (1999). Simulated annealing with asymptotic convergence for nonlinear constrained global optimization. In Proc. of CP-99, pages 461\u2013475.","DOI":"10.1007\/978-3-540-48085-3_33"},{"key":"5112284_CR60","doi-asserted-by":"crossref","unstructured":"Wallace, R. (1995). Directed arc consistency preprocessing. In Meyer, M. (ed.), Selected Papers from the ECAI-94 Workshop on Constraint Processing, Vol. 923 of LNCS, pages 121\u2013137.","DOI":"10.1007\/3-540-59479-5_22"},{"key":"5112284_CR61","unstructured":"Wallace, R. (1996). Enhancements of branch and bound methods for the maximal constraint satisfaction problem. In Proc. of AAAI-96, pages 188\u2013195."},{"key":"5112284_CR62","unstructured":"Wallace, R., & Freuder, E. C. (1993). Conjunctive width heuristics for maximal constraint satisfaction. In Proc. of AAAI-93, pages 762\u2013768."},{"key":"5112284_CR63","doi-asserted-by":"crossref","unstructured":"Wallace R., & Freuder, E. C. (1995). Heuristics methods for over-constrained constraint satisfaction problems. In Over-Constrained Systems, Vol. 1106 of LNCS. (Also Workshop in CP-95.)","DOI":"10.1007\/3-540-61479-6_23"},{"key":"5112284_CR64","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0743-1066(93)90046-J","volume":"16","author":"M. Wilson","year":"1993","unstructured":"Wilson, M., & Borning, A. (1993). Hierarchical constraint logic programming. Journal of Logic Programming, 16: 227\u2013318.","journal-title":"Journal of Logic Programming"},{"key":"5112284_CR65","unstructured":"Yokoo, M. (1994). Weak-commitment search for solving constraint satisfaction problems. In Proc. of AAAI-94, pages 313\u2013318."},{"issue":"1","key":"5112284_CR66","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1109\/64.482960","volume":"11","author":"M. Yoshikawa","year":"1996","unstructured":"Yoshikawa, M., Kaneko, K., Yamanouchi, T., & Watanabe M. (1996). A constraint-based high school scheduling system. IEEE Expert, 11(1): 63\u201372.","journal-title":"IEEE Expert"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1021902812784.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1021902812784\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1021902812784.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T03:42:43Z","timestamp":1752378163000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1021902812784"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["5112284"],"URL":"https:\/\/doi.org\/10.1023\/a:1021902812784","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}