A non-intrusive approach to infeasibility diagnosis in semi-diagonal scheduling problems

Optimization-based scheduling and planning problems play a critical role in many industrial and operational contexts. In some applications, practitioners are required to provide input values that are used to define the constraints of a specific problem instance, while the overall model structure and logic of the optimization model are predefined. Depending on the selected values, these instance-specific constraints may lead to an infeasible optimization problem. In such situations, understanding the causes of infeasibility becomes essential in order to support the recovery of a feasible formulation. Existing diagnostic techniques are often intrusive, requiring modifications to the original optimization model, constraint relaxations, or the repeated solution of auxiliary optimization problems in order to identify feasible alternatives increasing both the computational complexity and the implementation effort required by the method. To address these limitations, this thesis proposes a non-intrusive machine learning framework for infeasibility diagnosis. The proposed approach exploits the semi-diagonal structure of the constraint matrix and trains a classifier to identify the underlying causes of infeasibility. The proposed framework is evaluated on two scheduling problems of increasing complexity: a Worker Allocation Problem and a Flight and Maintenance Planning problem. For each case study, infeasibility classes are defined, and datasets of infeasible instances are generated to train and evaluate the classifier. Experimental results show that the proposed approach achieves high classification accuracy and effectively learns infeasibility patterns from data.

I problemi di scheduling e planning basati sull'ottimizzazione rivestono un ruolo fondamentale in numerosi contesti industriali e operativi. In alcune applicazioni, ai practitioner è richiesto di fornire alcuni valori di input utilizzati per definire i vincoli di una specifica istanza del problema, mentre la struttura e la logica generale del modello di ottimizzazione sono predefinite. A seconda dei valori selezionati, tali vincoli possono risultare tra loro incompatibili e rendere il problema di ottimizzazione infeasible. In queste situazioni, comprendere le cause dell'infeasibilità è essenziale per supportare il ripristino di una formulazione ammissibile. Le tecniche di diagnostica esistenti sono spesso intrusive, poiché richiedono modifiche al modello originale, il rilassamento di vincoli oppure la risoluzione ripetuta di problemi di ottimizzazione ausiliari per individuare possibili alternative ammissibili, aumentando sia la complessità computazionale sia lo sforzo implementativo richiesto. Per affrontare queste limitazioni, questa tesi propone un framework non intrusivo basato su tecniche di machine learning per la diagnostica dell'infeasibilità. L'approccio sfrutta la struttura semi-diagonale della matrice dei vincoli e addestra un classificatore con l'obiettivo di identificare le cause sottostanti dell'infeasibilità. Il framework proposto viene valutato su due problemi di scheduling di complessità crescente: un Worker Allocation Problem e un Flight and Maintenance Planning Problem. Per ciascun caso di studio vengono definite specifiche classi di infeasibilità e generati dataset di istanze infeasible utilizzati per l'addestramento e la valutazione del classificatore. I risultati sperimentali mostrano che l'approccio proposto raggiunge elevati livelli di accuratezza ed è in grado di apprendere efficacemente i pattern di infeasibilità presenti nei dati.