Constraint Solving Approaches to the Business-to-Business Meeting Scheduling Problem (Extended Abstract)

1 Introduction

In business-to-business (B2B) events, its attendees hold pairwise meetings with other event participants having similar interests, giving them the opportunity to find investors, sell or buy products, share ideas and projects, etc. This pairwise configuration of meetings produces some constraints in the attendees' agendas. Also, these participants may have additional time availability restrictions, resulting in additional constraints. Moreover, these events are usually restricted to a certain accommodation capacity, which limits the possible configuration of meetings between its participants. Therefore, finding a feasible schedule for all the desired meetings can be seen as a hard combinatorial problem.

∗This work is an extended abstract of the manuscript Constraint Solving Approaches to the Business-to-Business Meeting Scheduling Problem, co-authored by Miquel Bofill, Jordi Coll, Marc Garcia, Jes´us Gir´aldez-Cru, Gilles Pesant, Josep Suy, and Mateu Villaret, and published in 2022 in the Journal of Artificial Intelligence Research, volume 73, with DOI https://doi.org/10.1613/jair.1.12670.

The organization of B2B events and their corresponding schedule of meetings is traditionally made by a matchmaker in a handmade process. Therefore, finding such a feasible schedule is usually a tough and very time-consuming task. Moreover, in addition to hard constraints representing the accommodation capacity, the participants' time availability, and other meeting collision constraints, other soft constraints, like avoiding unnecessary idle time periods between meetings of the same participant, can be defined as well. As a consequence, even when finding a feasible schedule by a human may be possible in small B2B events, experience shows that those handmade schedules are usually sub-optimal. In contrast, [Bofill et al., 2022] presents computational techniques to find optimal solutions to this problem, and extensively analyze them experimentally.

2 Formulation of the Problem

The B2B Meeting Scheduling Problem (B2BSP) 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 idle time periods in participants' schedules should be avoided as much as possible. To handle it, the B2B Scheduling Optimization Problem (B2BSOP) is defined. It is the optimization version of B2BSP, where the total number of idle time periods of the participants is minimal subject to some fairness constraints, i.e., the difference of idle time periods between any two participants does not exceed a given threshold. B2BSOP constitutes a challenging combinatorial problem that needs to be solved for many real world brokerage events.

3 Contributions

Model-and-solve approaches to the B2BSOP have been developed in recent works. Several Constraint Programming (CP), Mixed-Integer Programming (MIP), and Maximum Satisfiability (MaxSAT) based encodings have been studied in [Bofill et al., 2014], in [Pesant et al., 2015] and in [Bofill et al., 2015].

The work in [Bofill et al., 2022] extends and improves the state-of-the-art approaches for the B2BSOP previously introduced. In particular, it presents a comparative study of CP, MIP, and MaxSAT approaches to this problem. The CP approach relies on using global constraints and was implemented in MiniZinc to be able to compare CP, Lazy Clause Generation and MIP as solving technologies in this setting. A pure MIP encoding is also presented, and an alternative viewpoint is considered under the MaxSAT formulation of the problem. Moreover, [Bofill et al., 2022] also presents a thorough evaluation of these approaches, where their performance on real world instances, as well as on crafted instances, is analyzed. To this end, some extensions of the problem, such as time restrictions for meetings, meeting precedences, or prefixed meetings, are considered. Using these extensions, 180 new B2B instances were contributed. The CP, MIP, and MaxSAT codifications were reformulated in order to consider these extensions, and the MaxSAT and MIP models were improved by taking advantage of implied constraints occurring in the problem. Finally, an alternative way of identifying the idle time periods in participants' schedules is also provided.

4 Experimental Results

The dataset used in the experimental analysis presented in [Bofill et al., 2022] consists of industrial B2B instances, and some variants of them including precedences between meetings and forbidden time slots.

This experimental study reveals that the MaxSAT approach is state-of-the-art technology for this problem, exhibiting better solving times, sometimes even orders of magnitude smaller than CP and MIP. Moreover, it is worth mentioning that the use of implied constraints in the MaxSAT models improves their performance in general. In fact, this enhanced model is able to solve all the existing B2B benchmarks. For CP models, Lazy Clause Generation is the dominating approach, and using the smallest automaton on the reified schedules turns to be the best configuration for all solvers. Gecode is not competitive in the considered dataset, not being able to solve any instance within the given time limit. Using Cplex to solve the CP formulation provides a worse performance than using the native MIP model.

5 Conclusions and FutureWork

The work in [Bofill et al., 2022] provides a precise formulation of the Business-to-Business Meeting Scheduling Optimization problem (B2BSOP), and presents a comparative study of different model-and-solve exact approaches to this problem. In particular, it evaluates CP, MaxSAT and MIP formulations, and considers distinct CP solving technologies. These approaches are refinements and improvements of the best approaches as reported in [Pesant et al., 2015] and [Bofill et al., 2015].

As further work, it is planned to investigate other variants of the B2BSOP, such as considering meetings with more than two participants, or allowing a participant to have more than one meeting at a time (assuming, for instance, that a company is sending two representatives to the brokerage event). Another interesting property of the schedules is to minimize the number of location changes that participants have to do. This was preliminarily studied in [Bofill et al., 2014], but a more integrated approach may be considered.

Acknowledgments

Work partially supported by grants PID2019-111544GBC21, TED2021-129319B-I00, PID2021-122274OB-I00 and PID2021-122916NB-I00 funded by MCIN/AEI /10.13039/501100011033 and by ERDF "A way of making Europe", and fellowship IJC2019-040489-I (MICINN/Juan de la Cierva).