×

zbMATH — the first resource for mathematics

Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. (English) Zbl 0782.90054
Summary: The paper describes a simple heuristic approach for solving large-scale constraint satisfaction and scheduling problems. In this approach one starts with an inconsistent assignment for a set of variables and searches through the space of possible repairs. The search can be guided by a value-ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. The heuristic can be used with a variety of different search strategies.
We demonstrate empirically that on the \(n\)-queens problem, a technique based on this approach performs oders of magnitude better than traditional backtracking techniques. We also describe a scheduling application where the approach has been used successfully. A theoretical analysis is presented both to explain why this method works well on certain types of problems and to predict when it is likely to be most effective.

MSC:
90B35 Deterministic scheduling theory in operations research
Software:
Prodigy
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramson, B.; Yung, M., Divide and conquer under global constraints: a solution to the n-queens problem, J. parallel distrib. comput., 61, 649-662, (1989)
[2] Adorf, H.M.; Johnston, M.D., A discrete stochastic neural network algorithm for constraint satisfaction problems, () · Zbl 0825.90654
[3] Biefeld, E.; Cooper, L., Bottleneck identification using process chronologies, () · Zbl 0745.68100
[4] Bitner, J.; Reingold, E.M., Backtrack programming techniques, Commun. ACM, 18, 651-655, (1975) · Zbl 0313.68026
[5] Brassard, G.; Bratley, P., ()
[6] Brelaz, D., New methods to color the vertices of a graph, Commun. ACM, 22, 251-256, (1979) · Zbl 0394.05022
[7] Cheeseman, P.; Kanefsky, B.; Taylor, W.M., Where the really hard problems are, () · Zbl 0747.68064
[8] Dechter, R.; Pearl, J., Network-based heuristics for constraint-satisfaction problems, Artif. intell., 34, 1-38, (1988) · Zbl 0643.68156
[9] Eskey, M.; Zweben, M., Learning search control for constraint-based scheduling, ()
[10] Fox, M.S., ()
[11] Fox, M.S.; Sadeh, N.; Baykan, C., Constrained heuristic search, () · Zbl 0707.68073
[12] Freuder, E.C., Partial constraint satisfaction, (), Artif. intell., 58, 21-70, (1992), (this volume)
[13] Ginsberg, M.L.; Harvey, W.D., Iterative broadening, ()
[14] Hammond, K.J., Case-based planning: an integrated theory of planning, learning and memory, ()
[15] Haralick, R.M.; Elliot, G.L., Increasing tree search efficiency for constraint satisfaction problems, Artif. intell., 14, 263-313, (1980)
[16] Hertz, A.; de Werra, D., Using tabu search techniques for graph coloring, Computing, 39, 345-351, (1987) · Zbl 0626.68051
[17] Hickman, A.K.; Lovett, M.C., Partial match and search control via internal analogy, ()
[18] Hopfield, J.J., Neural networks and physical systems with emergent collective computational abilities, () · Zbl 1369.92007
[19] Johnson, D.S.; Aragon, C.R.; McGeoch, L.A.; Schevon, C., Optimization by simulated annealing: an experimental evaluation, J. oper. res., 39, 3, 378-406, (1991), Part II · Zbl 0739.90055
[20] Johnson, D.S.; Papadimitrou, C.H.; Yannakakis, M., How easy is local search?, J. comput. syst. sci., 37, 79-100, (1988) · Zbl 0655.68074
[21] Johnston, M.D., Automated telescope scheduling, ()
[22] Johnston, M.D.; Adorf, H.M., Learning in stochastic neural networks for constraint satisfaction problems, () · Zbl 0825.90654
[23] Kale, L.V., An almost perfect heuristic for the n nonattacking queens problem, Inf. process. lett., 34, 173-178, (1990) · Zbl 0696.68097
[24] Kambhampati, S., Supporting flexible plan reuse, ()
[25] Keng, N.; Yun, D.Y.Y., A planning/scheduling methodology for the constrained resource problem, ()
[26] Kolodner, J.L.; Simpson, R.L.; Sycara-Cyranski, K., A process model of case-based reasoning in problem solving, ()
[27] Kurtzman, C.R., Time and resource constrained scheduling, with applications to space station planning, ()
[28] Kurtzman, C.R.; Aiken, D.L., The mfive space station crew activity scheduler and stowage logistics clerk, ()
[29] Langley, P., Systematic and nonsystematic search strategies, ()
[30] Minton, S.; Johnston, M.; Philips, A.B.; Laird, P., Solving large scale constraint sastisfaction and scheduling problems using a heuristic repair method, ()
[31] Morris, P., Solutions without exhaustive search: an iterative descent method for binary constraint satisfaction problems, ()
[32] Morris, P., An iterative improvement algorithm with guaranteed convergence, Tech. rept. TR-M-91-1, intellicorp technical note, (1991)
[33] Morris, P., On the density of solutions in equilibrium points for the queens problem, ()
[34] Muscettola, N.; Smith, S.F.; Amiri, G.; Pathak, D., Generating space telescope observation schedules, ()
[35] Musick, R.; Russell, S., How long will it take?, ()
[36] Selman, B.; Levesque, H.J.; Mitchell, D., A new method for solving hard satisfiability problems, ()
[37] Simmons, R.G., A theory of debugging plans and interpretations, ()
[38] Sosic, R.; Gu, J., A polynomial time algorithm for the n-queens problem, Sigart, 1, 3, (1990)
[39] Stone, H.S.; Stone, J.M., Efficient search techniques—an empirical study of the n-queens problem, IBM J. res. dev., 31, 464-474, (1987)
[40] Sussman, G.J., ()
[41] Turner, J.S., Almost all k-colorable graphs are easy to color, J. algorithms, 9, 63-82, (1988) · Zbl 0661.68066
[42] Veloso, M.M.; Carbonell, J.G., Towards scaling up machine learning: a case study with derivation analogy in prodigy, ()
[43] Waldrop, M., Will the hubble space telescope compute?, Science, 243, 1437-1439, (1989)
[44] Zweben, M., A framework for iterative improvement search algorithms suited for constraint satisfaction problems, ()
[45] Zweben, M.; Deale, M.; Gargan, R., Anytime rescheduling, ()
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.