Surrogate models for schedule evaluation
Objective
Objective: Testing the performance of an XGBoost model trained for predicting objective values and ranking pairwise schedules.
Background: To find optimal solutions for appointment scheduling problems one approach is to create local search neighborhoods and evaluate the schedules in that set. A better search method either (1) - creates smaller search neighborhoods or (2) - evaluates faster.
One approach for speeding up evaluation is to create surrogate models, or metamodels. These are simplified representations of complex systems that are often created using machine learning techniques. When evaluating a complex system is computationally expensive, it’s more efficient to use a method that quickly identifies a subset of solutions with a high likelihood of containing the optimal or near-optimal solution. By focusing computational resources on refining the search within this promising subset, rather than across the entire solution space, we can significantly reduce the overall computational burden (Ho et al. 2000).
We will test two approaches:
- Cardinal model - Directly assessing the objective values from a given sample schedule using an XGBoost regressor.
- Ordinal model - Predicting the preferred schedule from a pair of sampled schedules using an XGBoost classifier.
| Model | Cardinal (Regressor) | Ordinal (Classifier) |
|---|---|---|
| Evaluation (approx.) | \(f: S \rightarrow Objective, \\ f(S) \in \mathbb{R}^{18}\) | \(g: (S_0,S_1) \rightarrow \text{\{0, if } S_0 \text{ is better; otherwise 1\}}, \\ g(S_0, S_1) \in \mathbb{R}^{2 \times 18}\) |
| Comparison (schedules \(S_0, S_1\)) | \(f(S_0)\) vs. \(f(S_1)\) | \(g(S_0, S_1)\) |
| Parameter Tuning | Optuna | Optuna |
| Training Data | 40k rows | 20k rows |