💻 computer science

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

This paper introduces compact SAT and MaxSAT encodings for business-to-business meeting scheduling that utilize domain filtering and shared variables to significantly reduce clause counts and memory usage while minimizing participant idle-time ranges, outperforming both a published MaxSAT formulation and the commercial solver Gurobi in solving efficiency.

Original authors: Long Duc Nguyen, Tuyen Van Kieu, Khanh Van To

Published 2026-08-04

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Long Duc Nguyen, Tuyen Van Kieu, Khanh Van To

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the ultimate party planner for a massive, high-stakes business convention. You have hundreds of people who need to have one-on-one meetings, but everyone has different schedules, some rooms are tiny while others are huge, and certain meetings must happen before others can start. Your goal isn't just to get everyone a meeting; it's to make sure no one is sitting around bored for too long between their appointments. This is the chaotic puzzle of "Business-to-Business (B2B) meeting scheduling."

To solve this, computer scientists use a special kind of logic game called SAT (Satisfiability). Think of SAT as a super-smart detective that checks if a set of rules can ever be true at the same time. If you tell the detective, "Meeting A must be before Meeting B, but Meeting B must be before Meeting A," the detective instantly says, "Impossible!" But if the rules are tricky but possible, the detective finds a valid schedule. Another version, MaxSAT, is like a detective who not only finds a valid schedule but also tries to make it perfect by minimizing how much time people spend waiting around. This paper dives into how we can make these logic detectives faster and smarter when organizing these complex business events.

The Problem: A Tangled Web of Meetings

In the world of business meetings, things get messy fast. You have a list of meetings, a list of time slots, and a list of rooms. The rules are strict:

No Overlap: A person can't be in two places at once.
Room Limits: A room can't hold more meetings than its capacity.
Precedence: Some meetings must happen before others (like a morning briefing before an afternoon workshop).
The "Idle" Problem: The real headache is "idle time." If a participant has a meeting at 9:00 AM and their next one isn't until 11:00 AM, they have two hours of "idle time." The goal of this research is to balance this so that no one is waiting around for hours while others only wait a few minutes. It's about fairness and efficiency.

The Old Way vs. The New Way

The researchers looked at an existing method (called ORG-MAXSAT) that was already pretty good. However, they noticed it was like trying to organize a party by writing down every single possible combination of guests and times, even the ones that were obviously impossible. It was bulky, slow, and used up a lot of computer memory.

The team at VNU University of Engineering and Technology in Vietnam decided to build a "compact" version. They introduced three main tricks to shrink the problem down:

The "Pre-Check" Filter (Domain Filtering): Before even asking the computer detective to solve the puzzle, they added a smart filter. This filter looks at the rules and immediately crosses out impossible options. For example, if a meeting must happen after another one that ends at 2:00 PM, the filter instantly removes any time slots before 2:00 PM from the list of possibilities. This is like clearing the clutter off a desk before trying to find a specific pen. They proved this filter never throws away a valid solution; it only removes the garbage.
The "Shared Staircase" (Sparse Shared-Suffix Encoding): When dealing with the "must happen before" rules, the old method wrote a separate note for every single pair of meetings. If you had 100 meetings, that was thousands of notes. The new method noticed that many of these notes were saying the same thing. Instead of writing "Meeting A before B," "Meeting A before C," and "Meeting A before D" separately, they created a shared "staircase" of logic. They reuse variables for similar situations, like using one master key for several doors instead of making a new key for every single lock.
The "Fairness" Score (Idle-Time Balancing): Instead of just counting how many breaks people have, they created a new way to measure "idle time." They looked at the time between a person's first meeting and their last meeting. If someone has meetings at 9:00 and 11:00, their "span" is two hours. If they only had one meeting, they have zero idle time. The goal is to make sure the difference between the most-busy person's idle time and the least-busy person's idle time is as small as possible.

What They Found

The researchers tested their new "Compact" method against the old one and against some very powerful commercial software (like Gurobi and CPLEX) on 126 official test cases and 100 extra "stress test" cases with even more meetings.

Here are the results, which are quite impressive:

Smaller Size: The new method reduced the number of logical "clauses" (the rules the computer has to check) by 40.3% on average.
Less Memory: It used 55.9% less peak memory. Imagine needing half the RAM to solve the same puzzle.
Faster Speed: The total time to solve the problems dropped by 14.0%.
The Power of Filtering: Just using the "Pre-Check" filter alone cut the number of variables by 24.1% and the rules by 16.2%.
The Power of Sharing: The "Shared Staircase" trick shaved off another 0.5% to 5.5% of the rules, depending on how crowded the schedule was.

The Verdict

The most exciting part is that their new, compact SAT and MaxSAT methods were able to solve every single one of the 126 official test cases. Even better, they did it faster than the leading commercial solver, Gurobi, in terms of median time. While other commercial tools (like CPLEX and CP Optimizer) struggled to solve all the cases within the time limit, the new SAT-based approach handled them all.

The paper doesn't claim to have solved the universe's scheduling problems forever, but it has definitely shown that by cleaning up the rules and sharing the work smarter, we can make computers much better at organizing our busy lives. It turns a massive, tangled knot of meetings into a neat, balanced schedule where everyone gets their fair share of time, and no one is left waiting in the hallway for too long.

Technical Summary: Compact SAT and MaxSAT Encodings for B2B Meeting Scheduling with Idle-Time Balancing

Problem Definition

The paper addresses Business-to-Business (B2B) meeting scheduling, a combinatorial optimization problem where requested pairwise meetings must be assigned to specific time slots and locations. The scheduling must satisfy several constraints:

Participant Non-overlap: A participant cannot attend two meetings simultaneously.
Location Capacity: The number of meetings in any time slot cannot exceed the number of available locations ( $K$ ).
Availability & Restrictions: Meetings must occur within requested sessions, fixed slots, or forbidden slots.
Precedence: Directed arcs $(i, j)$ enforce that meeting $i$ must occur before meeting $j$ .

The objective proposed in this work differs from prior formulations (which often minimize "break groups" or bound disparity in break counts). Instead, this study minimizes the range of internal idle-slot totals ( $\Delta I$ ) among participants with at least two meetings. Internal idle slots are defined as unoccupied time strictly between a participant's first and last assigned meetings. This metric distinguishes between short interruptions and longer waits, aiming for a balanced load distribution similar to the Balanced Academic Curriculum Problem (BACP). An aggregate idle time measure ( $I_\Sigma$ ) is also reported as a complementary metric.

Methodology

The authors propose a compact SAT (Boolean Satisfiability) and MaxSAT encoding that integrates three primary modeling improvements over existing published formulations:

Solution-Preserving Domain Filtering (Preprocessing):
Before generating the Conjunctive Normal Form (CNF), the authors apply a preprocessing algorithm (Algorithm 1) that removes unsupported assignments. This integrates:
- Endpoint-bound filters: Propagating precedence constraints along paths (using either direct arcs or transitive closure).
- Per-participant matching: Removing assignments that cannot be part of a conflict-free schedule for a specific participant.
- Saturated-slot propagation: Eliminating slots where capacity is already fully utilized by forced assignments.
- Claim: This process preserves all feasible schedules while reducing the domain size, thereby reducing the number of variables and clauses.
Sparse Shared-Suffix Precedence Encoding (SPARSESUFFIX):
Instead of encoding precedence relations using pairwise clauses (which can be quadratic in domain size), the authors introduce a sparse encoding.
- It materializes only the distinct "cut points" in the predecessor domain where the constraint becomes active.
- It reuses auxiliary variables for equal cuts across different relations.
- This approach is proven equivalent to pairwise clauses but significantly reduces the clause count, particularly when combined with domain reduction.
Range-Based Idle-Time Objective:
The paper introduces an exact encoding to minimize the range of internal idle slots ( $\Delta I$ ).
- It derives the first and last occupied slots for each participant.
- It uses a linear number of auxiliary variables to compute the difference between the maximum and minimum idle counts across all relevant participants.

The study evaluates these components against a baseline ORG-MAXSAT formulation (an adaptation of a published model) and commercial solvers (Gurobi, CPLEX, CP Optimizer). The evaluation covers 126 official benchmark instances and 100 derived "Stress" instances with varying precedence densities.

Key Contributions

The paper identifies three specific contributions:

Preprocessing Procedure: A filter integration that removes unsupported assignments before CNF generation. Proposition 1 proves this preserves feasibility, and empirical results show it reduces assignment variables by 24.1% and clauses by 16.2%.
Sparse Shared-Suffix Representation: An exact encoding (SPARSESUFFIX) that materializes only required predecessor-domain cut points. Proposition 3 proves its equivalence to pairwise clauses. The study demonstrates that while domain reduction lowers variable counts, suffix sharing independently lowers clause counts.
B2B-Specific Objective: A range-based idle-time objective that measures disparity in internal waiting times, encoded with a linear number of auxiliary variables.

Experimental Results

The experiments were conducted on a 4-core machine with a 7,200-second time limit. Key findings include:

Formula Size and Memory: Compared to the adapted ORG-MAXSAT baseline, the proposed compact encoding reduced the median clause count by 40.3% and median peak memory usage by 55.9%.
Domain Reduction Impact: Domain filtering alone reduced assignment variables by 24.1% and clauses by 16.2%, contributing the largest share of formula size reduction.
Precedence Encoding: The SPARSESUFFIX encoding reduced the median clause count by 0.5%–1.0% on official precedence instances and up to 5.5% on the highest density derived instances (when combined with transitive closure).
Solver Performance:
- All three proposed SAT/MaxSAT methods (Incremental SAT, Non-Incremental SAT, and UWrMaxSAT) solved all 126 official instances.
- Compared to Gurobi (the only commercial solver to solve all instances), the proposed SAT/MaxSAT methods achieved lower median total times.
- Incremental SAT achieved the lowest median time (0.227s) among the complete methods.
- CP Optimizer had the lowest median time (0.110s) but failed to solve 11 instances within the time limit.

Significance and Claims

The paper claims that the proposed compact encoding offers a significant efficiency improvement over existing Boolean formulations for B2B meeting scheduling. By separating domain filtering from precedence representation, the authors demonstrate that domain reduction is the primary driver for reducing formula size, while sparse shared-suffix encoding provides additional clause reduction independent of the relation set.

The study asserts that the new idle-time range objective provides a more nuanced measure of schedule quality than previous "break group" metrics, distinguishing between short interruptions and long waits. Furthermore, the results indicate that modern SAT and MaxSAT solvers, when equipped with these compact encodings, can outperform leading commercial MIP and CP solvers in terms of median solving time for this specific problem class, solving all benchmark instances where some commercial solvers timed out.

The authors remain modest regarding future work, noting that the current study focuses on single-run timing and that future research could explore repeated timing runs and lexicographic objectives (minimizing $\Delta I$ before $I_\Sigma$ ).