A robust fix-and-optimize matheuristic for timetabling problems with uncertain renewable energy production

International audienceThis work presents a fix-and-optimize matheuristic to solve timetabling problems under uncertainty. Specifically, a combined university timetabling and electricity storage scheduling problem is considered, subject to uncertainty stemming from renewable energy production and electricity demand. The problem is formulated as a large Mixed Integer Program (MIP) and the proposed solution combines Large Neighborhood Search coupled with scenario-based robust optimization for handling uncertainty in the objective function. First, an adequate feasible schedule is derived considering only hard problem constraints, in this case scheduling of recurring lecture activities. Next, the solution is improved with a fix-and-optimize heuristic search. In each iteration, the MIP solver explores a large neighborhood by fixing a subset of variables and optimizing over the remaining free variables. The process is repeated several times until a stopping criterion is met. To address uncertainty in the objective, probabilistic scenarios are derived from interval forecasts and the worst-case energy cost is minimized. The results derived from the participation in a technical challenge show that the proposed approach provides competitive solutions relatively fast, even for large problem instances, while also hedging against large forecast errors. Index Terms-fix-and-optimize, local neighborhood search, renewable energy forecasting, robust optimization, university timetabling