Constraint Solving Approaches to the Business-to-Business Meeting Scheduling Problem

Miquel Bofill (1) , Jordi Coll (2) , Marc Garcia (1) , Jesús Giráldez-Cru (3) , Gilles Pesant (4) , Josep Suy (1) , Mateu Villaret (1)

1 UdG - Universitat de Girona
2 COALA - COntraintes, ALgorithmes et Applications
3 UGR - Universidad de Granada = University of Granada
4 EPM - École Polytechnique de Montréal

The Business-to-Business Meeting Scheduling problem consists of scheduling a set of meetings between given pairs of participants to an event, while taking into account participants' availability and accommodation capacity. A crucial aspect of this problem is that breaks in participants' schedules should be avoided as much as possible. It constitutes a challenging combinatorial problem that needs to be solved for many real world brokerage events. In this paper we present a comparative study of Constraint Programming (CP), Mixed-Integer Programming (MIP) and Maximum Satisfiability (MaxSAT) approaches to this problem. The CP approach relies on using global constraints and has been implemented in MiniZinc to be able to compare CP, Lazy Clause Generation and MIP as solving technologies in this setting. We also present a pure MIP encoding. Finally, an alternative viewpoint is considered under MaxSAT, showing best performance when considering some implied constraints. Experiments conducted on real world instances, as well as on crafted ones, show that the MaxSAT approach is the one with the best performance for this problem, exhibiting better solving times, sometimes even orders of magnitude smaller than CP and MIP.

Domaines: Logique en informatique [cs.LO]

Miquel Bofill, Jordi Coll, Marc Garcia, Jesús Giráldez-Cru, Gilles Pesant, et al.. Constraint Solving Approaches to the Business-to-Business Meeting Scheduling Problem. Journal of Artificial Intelligence Research, 2022. ⟨hal-03775300⟩