Constraint Satisfaction as Global Optimization
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 579-584.
Abstract
We present a optimization formulation for discrete binary CSP, based on the construction of a continuous function A(P) whose global maximum represents the best possible solution for that problem. By the best possible solution we mean either (i) a solution of the problem, if it is solvable, or (ii) a partial solution violating a minimal number of constraints, if the problem is unsolvable. This approach is based on relaxation labeling techniques used to enforce consistency in image interpretation. We have used a projected gradient ascent algorithm to maximize A(P) on the n-queens problem obtaining good results but with a high computational cost. To elude this problem, we have developed a heuristic for variable and value selection inspired in the direction in which A(P) is maximized. We have tested this heuristic with forward checking on several classes of CSP.
@inproceedings{ijcai1995p76,
title = {Constraint Satisfaction as Global Optimization},
author = {Meseguer, Pedro and Larrosa, Javier},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {579--584},
year = {1995},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1995/76},
}
TY - CPAPER TI - Constraint Satisfaction as Global Optimization AU - Meseguer, Pedro AU - Larrosa, Javier T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 579 EP - 584 UR - https://ijcai.org/proceedings/1995/76 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
