Solving a large oral examination timetabling problem using a multidimensional knapsack MILP formulation

Cyrille Briand (UT3; Jean-Pierre Belaud (LGC); LAAS-ROC)

arxiv: 2605.18402 · v1 · pith:PCGX7UX2new · submitted 2026-05-18 · 🧮 math.OC

Solving a large oral examination timetabling problem using a multidimensional knapsack MILP formulation

Cyrille Briand (UT3 , LAAS-ROC) , Jean-Pierre Belaud (LGC) This is my paper

Pith reviewed 2026-05-20 08:54 UTC · model grok-4.3

classification 🧮 math.OC

keywords oral examination timetablingmultidimensional knapsackMILP formulationpre-validated schedulescandidate assignmentlarge-scale schedulingSCIP solvercombinatorial reduction

0 comments

The pith

Reducing oral exam timetabling to a multidimensional knapsack MILP lets a solver assign nearly all candidates to pre-validated schedules.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the oral examination timetabling problem for more than 7,000 candidates becomes tractable when first a collection of valid schedules is generated and candidates are then assigned to those schedules rather than to individual time slots. A sympathetic reader cares because the full set of possible slot combinations creates too many variables and constraints for direct optimization at this scale. The MILP formulation encodes the assignment as a multidimensional knapsack problem that respects overlaps, geographic origins, and visa rules. On the 2025 real instance the approach produces a feasible schedule for 7,796 of the 7,804 candidates inside a 20-minute run of the SCIP solver.

Core claim

By generating a predetermined set of pre-validated schedules and modeling the assignment of candidates to these schedules as a multidimensional knapsack problem, the mixed-integer linear programming formulation reduces the combinatorial complexity of the oral examination timetabling problem enough that a standard solver finds a near-complete feasible solution on a real instance containing 7,804 candidates.

What carries the argument

Multidimensional knapsack MILP that assigns each candidate to one of a fixed collection of pre-validated schedules while enforcing multiple resource and compatibility constraints.

If this is right

7,796 of 7,804 candidates receive feasible schedules on the real 2025 instance.
The computation finishes inside a 20-minute limit using the SCIP solver.
Constraints on exam overlaps, geographic origin, and visa status are satisfied through the pre-validated schedules.
The same reduction strategy applies to other large institutional scheduling tasks that share similar resource and compatibility limits.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same pre-validation step could be applied to other timetabling domains such as conference sessions or medical appointments where full slot enumeration is intractable.
Systematic generation of the pre-validated schedule set itself could be tuned to increase coverage beyond the reported 99.9 percent.
Hybrid methods that combine this MILP with local search on the few unassigned candidates might close the remaining gap without enlarging the model.

Load-bearing premise

The collection of pre-validated schedules is assumed to be rich enough that assigning candidates to them produces feasible high-quality timetables without needing to choose time slots directly.

What would settle it

Running a direct MILP formulation that chooses individual time slots for each candidate on the same 2025 data instance either exhausts memory or requires far longer than 20 minutes to reach comparable coverage.

Figures

Figures reproduced from arXiv: 2605.18402 by Cyrille Briand (UT3, Jean-Pierre Belaud (LGC), LAAS-ROC).

read the original abstract

This paper addresses the Oral Examination Timetabling Problem (OETP) for France's prestigious engineering schools, an organization managed by the Service des Concours Communs Polytechniques (SCCP). The scheduling is highly complex, involving over 7,000 candidates across a four-week period while accounting for constraints such as exam overlaps, geographic origin, and visa requirements. To manage this scale, the paper shows how to model the problem as a Multidimensional Knapsack Problem (MKP) using a Mixed-Integer Linear Programming (MILP) formulation. Their strategy reduces combinatorial complexity by assigning candidates to a predetermined set of pre-validated schedules rather than individual time slots. Experimental results using the SCIP solver on a real 2025 data instance successfully accommodated 7,796 out of 7,804 candidates within a 20-minute time limit.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper shows a practical MILP reduction for a real 7800-candidate oral exam scheduling problem that works on 2025 data by assigning to pre-validated schedules.

read the letter

The punchline is that they model the SCCP oral exam timetabling as a multidimensional knapsack MILP and solve a full 2025 instance with 7796 out of 7804 candidates placed inside a 20-minute run. The key move is restricting the search to a fixed set of pre-validated schedules instead of optimizing every time slot from scratch, which keeps the model tractable at this scale while still folding in overlaps, geography, and visa rules through the pre-validation step. That is the concrete new piece: a working encoding and solve for this specific large French concours instance using real data and the SCIP solver. It is a straightforward but effective application of established MILP techniques to a messy practical problem, and the reported coverage rate plus runtime give evidence that the reduction pays off here. The formulation itself looks direct—no obvious circularity—and the empirical outcome is an actual solve result rather than a fitted claim. The main soft spot is the dependence on the pre-validated schedule set being comprehensive enough. If that set leaves out feasible combinations that would have allowed better packing or coverage, the MILP cannot find them because it never looks outside the templates. The abstract gives no detail on how the set was generated or tested for completeness, so it is hard to judge how much of the success is due to good upfront schedule design versus the solver itself. There is also no baseline comparison to other heuristics or direct slot-based models, which leaves the performance claim plausible but not fully benchmarked. This is the kind of paper that belongs in an applied operations research venue or a scheduling special issue. Readers who build large assignment models for education or public logistics will find the concrete encoding and the scale it handles useful to see. It is not reshaping the field, but the real-instance result is worth a careful look. I would send it to peer review so the details on schedule generation and any sensitivity checks can be examined.

Referee Report

1 major / 2 minor

Summary. The paper models the Oral Examination Timetabling Problem (OETP) as a multidimensional knapsack problem via MILP, assigning candidates to a predetermined set of pre-validated schedules to enforce constraints on overlaps, geography, and visas. On a real 2025 instance with 7,804 candidates, the SCIP solver accommodates 7,796 candidates in under 20 minutes.

Significance. If the pre-validated schedule set is shown to be comprehensive, the work provides a scalable MILP approach for large educational timetabling instances that reduces the search space while respecting real-world constraints; the concrete runtime and coverage numbers on authentic data constitute a practical contribution to applied optimization.

major comments (1)

[strategy paragraph / formulation] The strategy paragraph (and corresponding formulation section) treats the pre-validated schedule set as given and sufficiently complete, yet provides no quantification of its coverage (e.g., fraction of constraint-satisfying combinations that are included for overlap, geographic, or visa constraints). Because the MILP only selects from this fixed set, the reported 7,796/7,804 success rate is conditional on that coverage; without explicit verification or a bound on missed feasible assignments, the central claim that the formulation “successfully accommodates” the instance rests on an untested assumption.

minor comments (2)

[Abstract / results] The abstract and results section would benefit from an explicit statement of the objective function (e.g., maximize number of assigned candidates, or a weighted combination) and from a brief comparison, even if only qualitative, against a direct time-slot MILP or a heuristic baseline.
[formulation] Notation for the multidimensional knapsack dimensions (candidate attributes, schedule attributes) should be introduced once with a small table or list to improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their constructive feedback. We address the major comment point by point below.

read point-by-point responses

Referee: The strategy paragraph (and corresponding formulation section) treats the pre-validated schedule set as given and sufficiently complete, yet provides no quantification of its coverage (e.g., fraction of constraint-satisfying combinations that are included for overlap, geographic, or visa constraints). Because the MILP only selects from this fixed set, the reported 7,796/7,804 success rate is conditional on that coverage; without explicit verification or a bound on missed feasible assignments, the central claim that the formulation “successfully accommodates” the instance rests on an untested assumption.

Authors: We agree that the manuscript would benefit from a clearer description of how the pre-validated schedule set is constructed and why it can be considered comprehensive. The set is obtained by generating all possible assignments of candidates to time slots and locations that satisfy the overlap, geographic, and visa constraints. This generation process is exhaustive with respect to the hard constraints, meaning that any feasible schedule meeting these requirements is included in the set. Consequently, the MILP formulation selects from the complete set of valid options, and the reported coverage of 7,796 out of 7,804 candidates reflects the best possible assignment under these constraints. We will revise the strategy paragraph and the formulation section to include a detailed explanation of the schedule generation procedure, thereby addressing the concern about untested assumptions. However, providing a precise numerical fraction of all conceivable combinations is not feasible, as the total space without constraints is astronomically large; our approach deliberately avoids enumerating infeasible combinations. revision: partial

Circularity Check

0 steps flagged

No circularity: direct MILP formulation and empirical solve result

full rationale

The paper translates the oral examination timetabling constraints directly into a multidimensional knapsack MILP model that assigns candidates to a fixed set of pre-validated schedules. The reported outcome (accommodating 7,796 of 7,804 candidates) is the result of running the SCIP solver on a concrete 2025 instance within a 20-minute limit. This is an empirical feasibility result, not a prediction or derivation that reduces to the inputs by construction. No self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations appear in the derivation chain. The completeness of the pre-validated schedule set is an explicit modeling choice and assumption, but it does not create circularity because the MILP solve remains an independent computation on the chosen input set.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities are identifiable. The approach relies on standard MILP modeling assumptions for assignment problems.

pith-pipeline@v0.9.0 · 5683 in / 1115 out tokens · 50964 ms · 2026-05-20T08:54:20.264516+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

1 extracted references · 1 canonical work pages

[1]

Examination timetabling: Algorithmic strategies and applications

Carter M. W., G. Laporte, D. H. Lee, 1996, “Examination timetabling: Algorithmic strategies and applications", Journal of Operational Research Society, , Vol. 47(3), pp. 373-383. Müller T., 2016, “Real-life examination timetabling",Journal of Scheduling , Vol. 19, pp. 257-270. QuR.,E.K.Burke,B.McCollum,I.Batyrshin,A.Meisels,2009,“Asurveyofsearchmethodolog...

work page 1996

[1] [1]

Examination timetabling: Algorithmic strategies and applications

Carter M. W., G. Laporte, D. H. Lee, 1996, “Examination timetabling: Algorithmic strategies and applications", Journal of Operational Research Society, , Vol. 47(3), pp. 373-383. Müller T., 2016, “Real-life examination timetabling",Journal of Scheduling , Vol. 19, pp. 257-270. QuR.,E.K.Burke,B.McCollum,I.Batyrshin,A.Meisels,2009,“Asurveyofsearchmethodolog...

work page 1996