FIC/DK-P exhibits combinatorial explosion making exact solving intractable beyond small problem sizes¶

Claim · All claims
Evidence · 1 study · theoretical r3 · q2
Currency · newest study 2024 · not yet checked against its sources · not reviewed by a person

Subclaims¶

q2 i? Exact constraint-based solving of FIC/DK-P becomes generally not tractable in reasonable time as the pool of available courses per semester increases, with course-per-semester count S and number of academic terms T having strong effects on difficulty. → Lebis 2024

Evidence¶

Lebis 2024¶

Lebis, A., Humeau, J., Fleury, A., Lucas, F., & Vermeulen, M. (2024). Fully Individualized Curriculum with Decaying Knowledge, a New Hard Problem: Investigation and Recommendations. International Journal of Artificial Intelligence in Education. https://doi.org/10.1007/s40593-023-00376-9

q2 · i? · theoretical · r3

Exact solving experiment using two Prolog constraint-based solvers on reduced simulated datasets (C ∈ [24;100], K ∈ {10;20;30}, S ∈ {2;3}), with a 12-hour time limit per instance. Results show combinatorial explosion: "around N = 15, FIC/DK-P becomes generally not tractable in a reasonable time."

"we quickly observe a combinatorial explosion: around N = 15, FIC/DK-P becomes generally not tractable in a reasonable time."

Discussion¶

Related Claims¶

• A genetic algorithm can find near-faultless curricula for full-scale FIC/DK-P instances despite intractability of exact methods — related
• Increasing the number of courses per semester does not necessarily make FIC/DK-P easier to solve well — related
• Problem instance variability strongly affects FIC/DK-P solvability — related
• Using decay prediction as a search heuristic improves computational efficiency of exact solving over full evaluation — related