Automated Reformulation of Specifications by Safe Delay of Constraints

Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference (KR2004)

Volume

No

Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference (KR2004)

Contents

In this paper we propose a form of reasoning on specifications of combinatorial problems, with the goal of reformulating them so that they are more efficiently solvable. The reformulation technique highlights constraints that can be safely "delayed", and solved afterwards. Our main contribution is the characterization (with soundness proof) of safe-delay constraints with respect to a criterion on the specification, thus obtaining a mechanism for the automated reformulation of specifications applicable to a great variety of problems, e.g., graph coloring and job-shop scheduling. This is an advancement with respect to the forms of reasoning done by state-of-the-art-systems, which typically just detect linearity of specifications. Another contribution is a preliminary experimentation on the effectiveness of the proposed technique, which reveals promising time savings.