[Rule] TimetableDesign to ILP

[GiggleLiu]

Source

TimetableDesign

Target

ILP (binary)

Motivation

• Connects the orphan TimetableDesign problem to the main reduction graph via ILP (which has 15+ inbound reductions and connects to QUBO)
• Enables solving TimetableDesign instances using any ILP solver through the standard reduction graph path
• The natural ILP formulation — each constraint of TimetableDesign maps directly to a linear (in)equality
• Enables removing the native solver hook in src/solvers/ilp/solver.rs:185 that currently bypasses the reduction graph for TimetableDesign (added in PR Fix #511: [Model] TimetableDesign #719 as a workaround). Once this rule lands, the hook should be removed and the existing solver dispatch test (test_timetable_design_issue_example_is_solved_via_ilp_solver_dispatch) should be reinforced as a standard closed-loop reduction test that exercises reduce_to() → BruteForce solve on ILP → extract_solution() → verify with evaluate().

Reference

Even, S., Itai, A., & Shamir, A. (1976). On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing, 5(4), 691–703. DOI: 10.1137/0205048

The ILP formulation is the direct translation of the four constraints in the problem definition into linear (in)equalities over binary variables — a standard technique described in de Werra, D. (1985). "An introduction to timetabling," European Journal of Operational Research, 19(2), 151–162. DOI: 10.1016/0377-2217(85)90167-5

Reduction Algorithm

Given a TimetableDesign instance with $|C|$ craftsmen, $|T|$ tasks, $|H|$ work periods, availability sets $A_C(c) \subseteq H$ and $A_T(t) \subseteq H$, and requirements $R(c,t) \in \mathbb{Z}_{\geq 0}$:

1. Variables. Create one binary variable $x_{c,t,h} \in {0,1}$ for each triple $(c, t, h)$ where $h \in A_C(c) \cap A_T(t)$. Index the variables in craftsman-major, task-next, period-last order (matching the source model's configuration layout). Let $n$ be the total number of variables created.

2. Craftsman exclusivity. For each craftsman $c \in C$ and period $h \in H$, add the constraint:
   $$\sum_{t \in T : h \in A_T(t)} x_{c,t,h} \leq 1$$
   (each craftsman works on at most one task per period). Total: $|C| \cdot |H|$ constraints.

3. Task exclusivity. For each task $t \in T$ and period $h \in H$, add the constraint:
   $$\sum_{c \in C : h \in A_C(c)} x_{c,t,h} \leq 1$$
   (each task has at most one craftsman per period). Total: $|T| \cdot |H|$ constraints.

4. Requirement satisfaction. For each pair $(c, t) \in C \times T$, add the equality constraint:
   $$\sum_{h \in A_C(c) \cap A_T(t)} x_{c,t,h} = R(c,t)$$
   Total: $|C| \cdot |T|$ constraints.

5. Objective. Set the objective to minimize $0$ (satisfaction problem — any feasible solution suffices).

Solution extraction. The binary vector $(x_{c,t,h})$ maps directly back to the source configuration: set $f(c,t,h) = x_{c,t,h}$ for available triples and $f(c,t,h) = 0$ otherwise.

Size Overhead

Target metric	Formula
num_vars	num_craftsmen * num_tasks * num_periods
num_constraints	num_craftsmen * num_periods + num_tasks * num_periods + num_craftsmen * num_tasks

Note: num_vars is the worst case (all triples available). The actual count may be smaller when availability restricts some triples.

Validation Method

Closed-loop test: construct a small TimetableDesign instance, reduce to ILP, solve ILP with brute force, extract solution back to TimetableDesign, and verify with evaluate(). The test instance must be small enough for brute-force on the resulting ILP (e.g., 2×2×2 giving 8 ILP vars → 256 configs).

Example

Source (TimetableDesign): 3 craftsmen, 4 tasks, 3 periods.

$C = {c_1, c_2, c_3}$, $T = {t_1, t_2, t_3, t_4}$, $H = {h_1, h_2, h_3}$

Craftsman availability:

• $A_C(c_1) = {h_1, h_2, h_3}$, $A_C(c_2) = {h_1, h_2}$, $A_C(c_3) = {h_1, h_2, h_3}$

Task availability:

• $A_T(t_1) = {h_1, h_2}$, $A_T(t_2) = {h_2, h_3}$, $A_T(t_3) = {h_1, h_2, h_3}$, $A_T(t_4) = {h_1, h_3}$

Requirements $R(c,t)$:

	$t_1$	$t_2$	$t_3$	$t_4$
$c_1$	1	1	0	1
$c_2$	0	0	2	0
$c_3$	0	1	0	0

Construction:

Available triples (24 of 36): for each $(c,t)$, only periods in $A_C(c) \cap A_T(t)$ yield variables. This gives 24 binary ILP variables.

Key constraints:

• Craftsman exclusivity: 9 constraints ($3 \times 3$)
• Task exclusivity: 12 constraints ($4 \times 3$)
• Requirements: 12 equality constraints ($3 \times 4$)
• Objective: minimize 0

Constraint cascade: $R(c_2, t_3) = 2$ with only 2 available periods forces $x_{c_2,t_3,h_1} = x_{c_2,t_3,h_2} = 1$. Craftsman exclusivity then fully books $c_2$ in both $h_1$ and $h_2$. Task exclusivity for $t_3$ blocks $c_1$ and $c_3$ from $t_3$ in those periods. Craftsman $c_1$ must fit tasks $t_1$, $t_2$, $t_4$ (each requiring 1 period) into the 3 available periods — one per period. Task exclusivity for $t_2$ then forces $c_3$ into whichever period $c_1$ doesn't use.

ILP solution (one of two valid): $c_1$: $t_1 \to h_1$, $t_2 \to h_2$, $t_4 \to h_3$; $c_2$: $t_3 \to h_1$, $t_3 \to h_2$; $c_3$: $t_2 \to h_3$.

Extracted timetable:

• $h_1$: $f(c_1, t_1, h_1) = 1$, $f(c_2, t_3, h_1) = 1$
• $h_2$: $f(c_1, t_2, h_2) = 1$, $f(c_2, t_3, h_2) = 1$
• $h_3$: $f(c_1, t_4, h_3) = 1$, $f(c_3, t_2, h_3) = 1$

All 4 constraints satisfied: availability respected, no double booking, all requirements met. Answer: YES.

This example is non-trivial because $R(c_2, t_3) = 2$ forces a multi-period assignment, creating a constraint cascade through craftsman and task exclusivity that determines most of the solution.

Extra Remark

Native solver hook cleanup (from PR #719 review): PR #719 added a native backtracking solver for TimetableDesign inside ILPSolver::solve_dyn (src/solvers/ilp/solver.rs:185) because no ILP reduction path existed. Once this rule is implemented:

1. Remove the TimetableDesign branch from solve_dyn in src/solvers/ilp/solver.rs
2. Remove solve_via_required_assignments() from src/models/misc/timetable_design.rs
3. Convert test_timetable_design_issue_example_is_solved_via_ilp_solver_dispatch into a standard closed-loop reduction test (test_timetabledesign_to_ilp_closed_loop) that exercises reduce_to() → BruteForce solve on ILP → extract_solution() → evaluate(). Use a small instance (e.g., 2×2×2) for brute-force feasibility.
4. Verify that pred inspect correctly reports ILP as a supported solver and pred solve output accurately reflects the reduction path

BibTeX

@article{evenItaiShamir1976,
  author  = {Shimon Even and Alon Itai and Adi Shamir},
  title   = {On the Complexity of Timetable and Multicommodity Flow Problems},
  journal = {SIAM Journal on Computing},
  volume  = {5},
  number  = {4},
  pages   = {691--703},
  year    = {1976},
  doi     = {10.1137/0205048},
}

@article{deWerra1985,
  author  = {Dominique de Werra},
  title   = {An Introduction to Timetabling},
  journal = {European Journal of Operational Research},
  volume  = {19},
  number  = {2},
  pages   = {151--162},
  year    = {1985},
  doi     = {10.1016/0377-2217(85)90167-5},
}

[zazabap]

timetabledesign_ilp.rs already implemented, issue close.