Miquel Bofill, Marc Garcia, Jesús Giráldez-Cru, Mateu Villaret

A Study on Implied Constraints in a MaxSAT Approach to B2B Problems

POS 2016

The B2B Scheduling Optimization Problem (B2BSOP) consists in finding the schedule of a set of meetings between persons minimizing the waiting time periods between meetings of the participants. Recent results have shown that a SAT-based approach is the-state-of-the-art. One of the interesting features of such approach is the use of implied constraints. In this work, we provide an experimental setting to study the effectiveness of using those implied constraints. Since there exists a reduced number of real-world B2B instances, we propose a random B2B instances generator, which reproduces certain features of these known to date real-world instances. We show the usefulness of some implied constraints depending on the characteristics of the problem, and the benefits of combining them. Finally, we give some insights on the exploitation of these implied constraints by the solver.