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

Miquel Bofill, Jordi Coll, Marc Garcia, Jesús Giráldez-Cru, Gilles Pesant, Josep Suy, Mateu VillaretIJCAI 2023 · DOI

TL;DR

This paper tackles the complex problem of scheduling business-to-business (B2B) meetings efficiently, aiming to minimize participant idle time while respecting availability and venue constraints. They present a comparative study of Constraint Programming (CP), Mixed Integer Programming (MIP), and Maximum Satisfiability (MaxSAT) approaches, finding MaxSAT to be the most performant, often outperforming others by orders of magnitude.

What Problem Does This Paper Address?

Organizing B2B events, like trade shows or conferences, involves scheduling numerous one-on-one meetings between participants who want to connect. This isn't just about finding a time slot; it's a hard combinatorial problem due to several factors:

  • Participant Availability: Individuals have their own schedules and cannot attend meetings at all times.
  • Accommodation Capacity: Venues or meeting rooms have limited space, restricting how many meetings can occur simultaneously.
  • Minimizing Idle Time: A crucial goal is to keep participants' schedules as packed as possible, reducing unproductive gaps between meetings. This is often framed as an optimization problem (B2BSOP) where the total idle time is minimized, subject to fairness constraints on idle time differences between participants.

Traditionally, this scheduling is done manually, which is time-consuming and often results in sub-optimal schedules. This paper explores computational techniques to find optimal solutions.

Methods

The authors present a comparative analysis of three primary model-and-solve approaches for the B2B Meeting Scheduling Optimization Problem (B2BSOP):

  • Constraint Programming (CP): This approach leverages global constraints and was implemented using MiniZinc to compare different CP solving technologies, including Lazy Clause Generation.
  • Mixed Integer Programming (MIP): A pure MIP encoding was developed.
  • Maximum Satisfiability (MaxSAT): This approach offers an alternative perspective, framing the problem in terms of satisfying as many constraints as possible, particularly useful when dealing with complex or implied constraints.

The work builds upon and extends previous research by providing a thorough evaluation of these methods on both real-world and crafted instances, including extensions to the problem such as time restrictions and meeting precedences.

Datasets

The experimental analysis in this paper uses a dataset consisting of:

  • Industrial B2B instances: These are real-world examples of B2B meeting scheduling problems.
  • Variants of these instances: These include additional complexities like precedences between meetings and forbidden time slots.
  • 180 new B2B instances: These were contributed as part of the study, incorporating extensions to the problem formulation.

Key Insights and Ideas

  • MaxSAT Shines: The MaxSAT approach emerged as the state-of-the-art for this problem, consistently delivering better solving times, often significantly faster than CP and MIP.
  • Implied Constraints are Key: Incorporating implied constraints into the MaxSAT and MIP models demonstrably improved their performance, enabling them to solve all benchmark instances.
  • CP Variants Matter: Within CP, Lazy Clause Generation proved to be the dominant solving technology.
  • Gecode Struggles: The Gecode solver, a popular CP solver, was not competitive on the considered dataset, failing to solve instances within the given time limits.
  • MIP vs. CP: Using a commercial solver like Cplex to solve the CP formulation yielded worse performance than using a native MIP model.

Key Results

The experimental results highlight the superior performance of the MaxSAT approach, achieving solving times that are sometimes "orders of magnitude smaller" than CP and MIP. The enhanced MaxSAT model was capable of solving all existing B2B benchmarks. For CP, using the smallest automaton on reified schedules was found to be the optimal configuration for all solvers.

Limitations and Future Work

The authors acknowledge that their work is an extended abstract of a more comprehensive study. Future work planned includes:

  • Investigating variants of B2BSOP with more than two participants per meeting.
  • Exploring scenarios where a participant can attend multiple meetings simultaneously (e.g., a company sending multiple representatives).
  • Considering the minimization of location changes for participants, a property that was preliminarily studied but could benefit from a more integrated approach.

Summary updated

BibTeX
@inproceedings{bofill2023constraint,
  author = {Miquel Bofill and Jordi Coll and Marc Garcia and Jesús Giráldez-Cru and Gilles Pesant and Josep Suy and Mateu Villaret},
  title = {{Constraint Solving Approaches to the Business-to-Business Meeting Scheduling Problem (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/768},
}
Figure