Compact SAT and MaxSAT Encodings for Business-to-Business Meeting Scheduling with Idle-Time Balancing
Listen
Radio episode about this paper
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.
Long Duc Nguyen, Tuyen Van Kieu, Khanh Van To
Faculty of Information Technology VNU University of Engineering and Technology
cs.LO
Submitted: 2026-08-01
Updated: 2026-11-18
Comments: 6 pages, 2 figures, 5 tables. Revised version incorporating reviewer feedback; accepted for presentation at RIVF 2026
Code: https://github.com/Longnguyen1555/Business-Meeting-Scheduling-Problem
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 92/100
The gist: Business-to-business meeting scheduling assigns requested pairwise meetings to time slots and locations under availability, capacity, conflict…
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
Summary
Business-to-business meeting scheduling assigns requested pairwise meetings to time slots and locations under availability, capacity, conflict, and precedence constraints The proposed encoding reduces the median clause count by 40. p. 03% and median peak memory usage by 55. p. 09% compared to an adapted published MaxSAT formulation using the same objective This study presents compact SAT and MaxSAT encodings based on solution-preserving domain filtering, variables shared at selected precedence boundaries, and an objective that minimizes the range of participants’ internal idle-slot totals
Model Definition and Objective
The optimization minimizes the range of participants’ internal idle-slot totals among participants with at least two meetings, defined as ∆I (S) = max p∈P ⋆ Ip(S) − min p∈P ⋆ Ip(S) Aggregate idle time IΣ(S) = P p∈P Ip(S) is reported alongside ∆I, where the range of participant internal idle-slot counts expresses the desired balance directly The objective is motivated by normbased load balancing in the Balanced Academic Curriculum Problem (BACP)
Encoding Techniques
The encoding integrates precedence-bound propagation, per-participant matching, and saturated-slot propagation before CNF generation to remove unsupported assignments A sparse shared suffix encoding, denoted by SPARSESUFFIX in tables, materializes only selected predecessor-domain cut points and reuses variables for equal cuts This representation proves equivalence to pairwise clauses
Performance and Comparison
Compared with Gurobi, a leading commercial solver, all three SAT and MaxSAT methods solve every official instance with lower median total times The compact model achieves median paired reductions of 40.3% in clauses, 55. p. 09% in peak memory, and 14. p. 00% in total time relative to ORG-MAXSAT INCREMENTAL SAT has the lowest median among the complete methods
Experimental Methodology
The evaluation covers four research questions: RQ1 (effect of domain reduction), RQ2 (filter relation, precedence representation, and encoded relation set), RQ3 (SAT and MaxSAT method comparison), and RQ4 (comparison with Gurobi, CPLEX, and CP Optimizer) RQ2 compares the convergence of the FILTER-E versus FILTER-E⋆ filter relation, PAIRWISE versus SPARSESUFFIX precedence representation, and DIRECT-E versus CLOSURE-E⋆ relation set
Conclusion on Effectiveness
Domain reduction gives the largest measured source of formula-size reduction, reducing the assignment-variable count by 24.1% and clauses by 16. p. 02% SPARSESUFFIX reduces the median clause count at every evaluated density, reaching 5. p. 55% under CLOSURE-E⋆ at prec60 All three SAT and MaxSAT methods solve All-126 and have lower median total times than Gurobi, the only commercial method to solve every instance INCREMENTAL SAT has the lowest median among the complete methods The zero value of ∆I can coexist with positive aggregate idle time, confirming that ∆I and IΣ describe complementary aspects of schedule quality
REFERENCES
[1] G. Pesant, G. Rix, and L. p. 5-M. Rousseau, “A comparative study of MIP and CP formulations for the B2B scheduling optimization problem,” in Integration of AI and OR Techniques in Constraint Programming, 2015, pp. p. 5 306–321, doi: 10. p. 51007/978-3-319-18008-3 21
[2] M. Bofill, J. Coll, M. Garcia, J. Giraldez-Cru, G. p. 5 Pesant, J. Suy, and ´M Villaret, “Constraint solving approaches to the business-to-business meeting scheduling problem,” Journal of Artificial Intelligence Research, vol 74 pp 263–301 2022
[3] M. Bofill, M. Garcia, J. Suy, and M. p. 5 Villaret, “MaxSAT-based scheduling of B2B meetings,” in Integration of AI and OR Techniques in Constraint Programming, 2015 pp 65–73
[4] M. Bofill, M. Garcia, J. Giraldez-Cru, and M. p. 5 Villaret, “A study on ´implied constraints in a MaxSAT approach to B2B problems,” in Artificial Intelligence Research and Development, 2019 pp 183–192
[5] J.-C. Regin, “A filtering algorithm for constraints of difference in CSPs,” in Proc. p. 5 12th National Conf. p. 5 Artificial Intelligence (AAAI), 1994 pp 362–367
[6] C. Sinz, “Towards an optimal CNF encoding of Boolean cardinality constraints,” in Principles and Practice of Constraint Programming, 2005 pp 827–831
[7] I. Ab´ıo, R. p. 5 Nieuwenhuis, A. p. 5 Oliveras, and E. p. 5 Rodr´ıguez-Carbonell, “A parametric approach for smaller and better encodings of cardinality constraints,” in Principles and Practice of Constraint Programming, 2013 pp 80–96
[8] H. X. Truong, T. Van Kieu, and K. p. 0 Van To, “Sequential counter encoding for staircase at-most-one constraints,” in Proc. p. 5 17th Int. Conf. Agents and Artificial Intelligence (ICAART), vol 2, 2025 pp 164–175
[9] T. Van Kieu, P. p. 0 C. Nguyen, B. G. Hoang, and K Van To, “Compact SAT encoding for power peak minimization in assembly line balancing,” arXiv:2512. p. 511435 2025
[10] M. Chiarandini, L Di Gaspero, S Gualandi, and A Schaerf, “The balanced academic curriculum problem revisited,” Journal of Heuristics, vol 18 no 1 pp 119–148 2012
[11] M. Gebser, T Glase, O Sabuncu, and T Schaub, “Matchmaking with answer set programming,” in Logic Programming and Nonmonotonic Reasoning ser LNCS vol 8148 2013 pp 342–347
[12] M. Bofill, J. Coll, J Giraldez-Cru, J Suy, and M Villaret, “The impact ´of implied constraints on MaxSAT B2B instances,” International Journal of Computational Intelligence Systems vol 15 Art no 63 2022
[13] M. Bofill, J. Coll, P Nightingale, J Suy, F Ulrich-Oltean, and M Villaret, “SAT encodings for pseudo-Boolean constraints together with atmost-one constraints,” Artificial Intelligence vol 302 Art no 103604 2022
[14] M. Bofill, J. Coll, J Suy, and M Villaret, “SMT encodings for resource-constrained project scheduling problems,” Computers & Industrial Engineering vol 149 Art no 106777 2020
[15] W. Klieber and G Kwon, “Efficient CNF encoding for selecting 1 from N objects,” in Proc. p. 5
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Domain filtering improves formula size by removing assignments absent from any complete per-participant matching, as stated in Proposition 1:
The filters remove only values that violate a precedence bound, lack support in a complete per-participant matching, or use capacity already forced to other meetings.
This allows the system to generate smaller SAT and MaxSAT encodings while preserving every feasible schedule. -
Exact sparse shared-suffix representation enhances clause reduction by reusing variables for equal cuts:
SPARSESUFFIX creates variables only for the distinct interior cut indices that occur,
which leads to a median clause count reduction of 5.5% under CLOSURE-E star at prec60 compared to PAIRWISE encoding. -
The idle-time range objective provides a B2B-specific balancing measure:
Our idle-slot objective instead minimizes the range of participants’ internal idle-slot totals among participants with at least two meetings,
which allows the system to optimize load balance based on participant internal waiting, complementing aggregate idle time. -
The system can solve B2B meeting scheduling problems using SAT and MaxSAT methods with lower median total times than commercial solvers:
Compared with Gurobi, a leading commercial solver, all three SAT and MaxSAT methods solve every official instance with lower median total times.
Sources
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring