We propose a machine-assisted approach to synthesise implied constraints for global constraints based on combinatorial objects. By reusing the Bound Seeker (BS) [8], we generate thousands of relationships between features. We present a scalable algorithm that automatically selects the relationships that filter the most, which we manually prove. We consider the Partition and the BinSeq constraints, which model the different ways of dividing a collection of objects into clusters, or the repartition of shifts in a 0–1 sequence. We use Partition and BinSeq in the Balanced Academic Curriculum Problem (BACP), and the Balanced Shift-Scheduling Problem (BSSP), where we optimise the distribution of the work to balance the workload. For 2 models of the BACP and 2 models of the BSSP, we show how the filtering inferred by the BS improves the cost of the solution found on different solvers. This filtering proved optimality for all CSPLib instances of the BACP.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Acquiring and Selecting Implied Constraints with an Application to the BinSeq and Partition Global Constraints

  • Jovial Cheukam Ngouonou,
  • Ramiz Gindullin,
  • Claude-Guy Quimper,
  • Nicolas Beldiceanu,
  • Rémi Douence

摘要

We propose a machine-assisted approach to synthesise implied constraints for global constraints based on combinatorial objects. By reusing the Bound Seeker (BS) [8], we generate thousands of relationships between features. We present a scalable algorithm that automatically selects the relationships that filter the most, which we manually prove. We consider the Partition and the BinSeq constraints, which model the different ways of dividing a collection of objects into clusters, or the repartition of shifts in a 0–1 sequence. We use Partition and BinSeq in the Balanced Academic Curriculum Problem (BACP), and the Balanced Shift-Scheduling Problem (BSSP), where we optimise the distribution of the work to balance the workload. For 2 models of the BACP and 2 models of the BSSP, we show how the filtering inferred by the BS improves the cost of the solution found on different solvers. This filtering proved optimality for all CSPLib instances of the BACP.