Exploring the Impact of Early Decisions in Variable Ordering for Constraint Satisfaction Problems

Article English OPEN
Ortiz-Bayliss, José Carlos ; Amaya, Ivan ; Conant-Pablos, Santiago Enrique ; Terashima-Marín, Hugo (2018)
  • Publisher: Hindawi
  • Journal: Computational Intelligence and Neuroscience, volume 2,018 (issn: 1687-5265, eissn: 1687-5273)
  • Related identifiers: doi: 10.1155/2018/6103726, pmc: PMC5842740
  • Subject: R858-859.7 | Computer applications to medicine. Medical informatics | Research Article | Neurosciences. Biological psychiatry. Neuropsychiatry | RC321-571 | Article Subject

When solving constraint satisfaction problems (CSPs), it is a common practice to rely on heuristics to decide which variable should be instantiated at each stage of the search. But, this ordering influences the search cost. Even so, and to the best of our knowledge, no earlier work has dealt with how first variable orderings affect the overall cost. In this paper, we explore the cost of finding high-quality orderings of variables within constraint satisfaction problems. We also study differences among the orderings produced by some commonly used heuristics and the way bad first decisions affect the search cost. One of the most important findings of this work confirms the paramount importance of first decisions. Another one is the evidence that many of the existing variable ordering heuristics fail to appropriately select the first variable to instantiate. Another one is the evidence that many of the existing variable ordering heuristics fail to appropriately select the first variable to instantiate. We propose a simple method to improve early decisions of heuristics. By using it, performance of heuristics increases.
  • References (48)
    48 references, page 1 of 5

    Garey, M. R., Johnson, D. S.. Computers and Intractability: A Guide to the Theory of NP-Completeness . 1979

    Berlier, J. A., McCollum, J. M.. A constraint satisfaction algorithm for microcontroller selection and pin assignment. : 348-351

    Bochkarev, S. V., Ovsyannikov, M. V., Petrochenkov, A. B., Bukhanov, S. A.. Structural synthesis of complex electrotechnical equipment on the basis of the constraint satisfaction method. Russian Electrical Engineering . 2015; 86 (6): 362-366

    Brailsford, S. C., Potts, C. N., Smith, B. M.. Constraint satisfaction problems: algorithms and applications. European Journal of Operational Research . 1999; 119 (3): 557-581

    Hell, P., Nesetril, J.. Colouring, constraint satisfaction, and complexity. Computer Science Review . 2008; 2 (3): 143-163

    Williams, C. P., Hogg, T.. Using deep structure to locate hard problems. : 472-477

    Dechter, R.. Constraint networks. In Encyclopedia of Artificial Intelligence . 1992: 276-286

    Purdom, P. W.. Backtracking and random constraint satisfaction. Annals of Mathematics and Artificial Intelligence . 1997; 20 (1-4): 393-410

    Christensen, S., Oppacher, F.. What can we learn from no free lunch? a first attempt to characterize the concept of a searchable function. : 1219-1226

    Wolpert, D. H., Macready, W. G.. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation . 1997; 1 (1): 67-82

  • Metrics
    No metrics available
Share - Bookmark