Compact SAT and MaxSAT Encodings for Business-to-Business Meeting Scheduling with Idle-Time Balancing

summary

The gist

Business-to-business meeting scheduling assigns requested pairwise meetings to time slots and locations under availability, capacity, conflict…

In short

This research developed compact SAT and MaxSAT encodings for scheduling business-to-business meetings while balancing participants' internal idle time. The new method reduces clause count by over 40% and peak memory usage by nearly 56% compared to existing formulations. This means the resulting models are much smaller and faster to solve, improving efficiency for complex scheduling problems.

Key concepts

Objective Function (∆I)
The goal is to minimize the range of internal idle-slot totals among participants who have at least two meetings. This is calculated as the difference between the maximum and minimum internal idle times across all relevant participants. Minimizing this range ensures a more balanced schedule where no participant has excessively long periods of free time compared to others.
Aggregate Idle Time (IΣ(S))
This metric sums up the total idle time for all participants in a given schedule S. It is reported alongside the range of internal idle times. This aggregate measure helps describe the overall quality of the schedule's load balancing, showing how much total free time exists across the entire group.
SPARSESUFFIX Encoding
This technique is a sparse shared suffix encoding used to represent precedence constraints. Instead of listing every possible predecessor-domain cut point, this method only materializes selected cut points and reuses variables for equal cuts. This keeps the resulting model representation compact by reusing variables where constraints are identical.
Domain Reduction
This involves reducing the set of possible values (domains) for scheduling variables. The study found that domain reduction was a major source of formula size reduction, specifically cutting assignment-variable count by 24.1% and clauses by 16.2%, demonstrating how simplifying variable choices significantly shrinks the resulting mathematical model.

Terminology used across episodes

This episode discusses

The paper

Compact SAT and MaxSAT Encodings for Business-to-Business Meeting Scheduling with Idle-Time Balancing · Read on arXiv

Long Duc Nguyen, Tuyen Van Kieu, Khanh Van To

Faculty of Information Technology VNU University of Engineering and Technology

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Compact SAT and MaxSAT Encodings for Business-to-Business Meeting Scheduling with Idle-Time Balancing".

Paper summary: Tom: So, looking at the paper "Compact SAT and MaxSAT Encodings for Business-to-Business Meeting Scheduling with Idle-Time Balancing", the main thing is that they've developed a compact way to schedule meetings using SAT and MaxSAT.

Jane: They focused on minimizing the range of internal idle-slot totals for participants with at least two meetings, which is quantified by ∆I sub S. The paper shows that their proposed encoding reduces clause count by forty point three percent and peak memory usage by fifty-five point nine percent compared to a published MaxSAT formulation.

Lu: They achieved this compact encoding by using solution-preserving domain filtering, variables shared at selected precedence boundaries, and an objective that minimizes the range of participants’ internal idle-slot totals.

Meng: The implication is that we can probably solve these scheduling problems on smaller computational resources than before, especially when dealing with high densities of meetings.

Tom: They also showed that their methods beat Gurobi in median total time for every official instance tested, and INCREMENTAL SAT had the fastest median among the complete methods they compared.

Jane: Ultimately, this work gives us a more compact way to model B2B meeting scheduling that is still solution-preserving, which is a really important balance to strike.

Conclusion: Tom: So, we're wrapping up on this paper about compact SAT and MaxSAT encodings for business-to-business meeting scheduling with idle-time balancing.

Jane: It boils down to them finding a way to pack a lot of complex scheduling rules into a much smaller formula.

Lu: They used techniques like domain filtering and sharing variables at specific points in the schedule to keep the encoding size down.

Meng: From my side, it means we can handle bigger meeting schedules on less powerful hardware because the memory usage drops by fifty-five point nine percent compared to what was published before.

Lalam: I confirm that their proposed approach reduces the median clause count by forty point three percent and peak memory usage by fifty-five point nine percent against an adapted MaxSAT formulation.

Tom: That's a big win for deployability, right? It’s about making these kinds of scheduling problems practical for real-world systems.

Jane: Yeah, and they also showed that their methods beat Gurobi in total time on every official test case they ran.

Lu: INCREMENTAL SAT was the fastest median among the complete methods because it uses a specific type of encoding called SPARSESUFFIX.

Meng: I'm interested in that SPARSESUFFIX part; if you only cut at certain boundaries, that sounds like something we could try on our next large-scale deployment.

Tom: Exactly, it’s about finding the right trade-off between model complexity and solving power.

Jane: It shows that even with all those constraints—pairwise meetings and idle time balancing—you can still get a tight encoding that doesn't make the problem unsolvable in practice.

Lu: The authors confirmed that their objective, minimizing the range of participant internal idle-slot totals, works even when there is positive aggregate idle time present.

Tom: That's important because it means we aren't forcing perfect balance if the underlying schedule structure just can't support it perfectly.

Jane: So, what does this mean for future work? They are looking at how different filter relations and precedence representations affect convergence.

Lu: They compared filtering algorithms and precedence representations to see which ones give the best results across different encoding styles.

Meng: I’m curious if the domain reduction part actually helps when you have a very high number of participants in the schedule.

Tom: Definitely, that’s where we need more data on how that scaling performs under extreme load scenarios.

More episodes

← Home