Publication Details
Title: How to Solve Interval Constraint Networks: The Definitive Answer - Probably
Author: P. Ladkin and A. Reinefeld
Group: ICSI Technical Reports
Date: November 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-063.pdf
Overview:
We implemented and tested an algorithm for solving interval constraint problems which returned solutions in less than or equal to 0.5 seconds on the average, with the hardest problem taking less than or equal to 0.5 minutes on a RISC workstation. This is a surprising result considering the problem is known to be NP-complete. We conclude that our algorithm suffices for solving random interval constraint problems in practice. Other conclusions are that path-consistency is an excellent pruning technique for solution search, which becomes almost a linear selection of atomic labels; also that path-consistency by itself is an excellent consistency heuristic for networks with fewer than six or greater than 15 nodes. We tested the algorithm on over two million randomly generated interval networks of various sizes, hence our title.
Bibliographic Information:
ICSI Technical Report TR-91-063
Bibliographic Reference:
P. Ladkin and A. Reinefeld. How to Solve Interval Constraint Networks: The Definitive Answer - Probably. ICSI Technical Report TR-91-063, November 1991
Author: P. Ladkin and A. Reinefeld
Group: ICSI Technical Reports
Date: November 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-063.pdf
Overview:
We implemented and tested an algorithm for solving interval constraint problems which returned solutions in less than or equal to 0.5 seconds on the average, with the hardest problem taking less than or equal to 0.5 minutes on a RISC workstation. This is a surprising result considering the problem is known to be NP-complete. We conclude that our algorithm suffices for solving random interval constraint problems in practice. Other conclusions are that path-consistency is an excellent pruning technique for solution search, which becomes almost a linear selection of atomic labels; also that path-consistency by itself is an excellent consistency heuristic for networks with fewer than six or greater than 15 nodes. We tested the algorithm on over two million randomly generated interval networks of various sizes, hence our title.
Bibliographic Information:
ICSI Technical Report TR-91-063
Bibliographic Reference:
P. Ladkin and A. Reinefeld. How to Solve Interval Constraint Networks: The Definitive Answer - Probably. ICSI Technical Report TR-91-063, November 1991