Incorporating a Probabilistic Choice Model in Constraint-Based Search
Nakorn Indra-Payoong, Raymond S. K. Kwan, L. G. Proll · 2003
This paper presents a local search method for constraint satisfaction problems, which is guided by some learning properties derived from a probabilistic choice model. The local search algorithm randomly selects a variable in a violated constraint and another variable from the search space. Two trials are performed, each of which assigns a different value to one of the selected variables whilst keeping the other fixed. Partial constraint propagation is performed in the process. The evaluation function for these trials is based on the overall degree of constraint violation. The trial results are accumulated with respect to individual variables. When sufficient trial history has been collected for a variable, it is analysed to infer a likely optimal value for that variable to be fixed at for a number of iterations. The algorithms presented have been applied to a demand responsive container freight rail scheduling problem. In this problem, all the decision variables are binary and relatively few feasible solutions exist. This paper will report on tests using real life data from Thailand.