Deep neural networks for solving time prediction in mixed-integer linear programming: an experimental study

Risolvere alcuni problemi di Mixed-Integer Linear programming (MILP) è ancora una sfida per i solver attuali e può richiedere ore di computazione. Ci sono poche indicazioni a priori su quanto possa essere difficile il problema da risolvere. In pratica, potrebbe essere utile una stima del numero di nodi (tempo di computazione) necessari al branch and bound. Potrebbe aiutare a capire se il solver sta lavorando bene e magari, attivare degli algoritmi durante la procedura di risoluzione in modo da ottenere performance migliori. Osservando l’evoluzione di un albero parziale generato durante il branch and bound per un MILP, il nostro obiettivo è quello di predire quanto il problema sia difficile, ovvero quanti nodi mancano alla fine. Predire la difficoltà di un problema tenendo conto della grandezza e della forma dell’albero è una delle aeree in cui il machine learning può avere un sostanziale impatto pratico nell’ottimizzazione combinatoria. Il nostro dataset include 100000 samples ed è stato realizzato estraendo alberi parzialmente completi durante il processo risolutivo del branch and bound su 10000 instanze tramite SCIP (Solving Constraint Integer Programs). Per sviluppare il nostro modello, abbiamo studiato le deep neural networks, in particolare le convolutional e recurrent neural networks comparandole e cercando di ottenere la migliore combinazione possibile per il nostro scopo. I risultati di questa tesi hanno mostrato che le 1D convolutional neural networks possono essere usate con successo per questi tipi di task ed avere performance migliori delle recurrent networks. Questa scoperta, inoltre, mostra che le 1D CNN sono molto efficienti per fare time series prediction, il quale è un campo dove di solito le RNN non hanno rivali. Quest'ultima osservazione potrebbe essere molto promettente considerando che le 1D CNN sono meno complesse e più veloci rispetto alle RNN.