Perché sto scommettendo sui solver euristici per l'ottimizzazione combinatoria

17 settembre 2026

La parola “solver” nell’ottimizzazione combinatoria evoca quasi automaticamente il mondo della programmazione lineare intera (MILP). È un riflesso pavloviano di cui soffriamo un po’ tutti, e che attribuisco al nostro comune background accademico: il primo solver che molti di noi abbiamo visto nella nostra vita risolveva un MILP, con ogni probabilità formulato mediante una libreria di modellazione algebrica.

Negli ultimi anni ho osservato, quantomeno nella mia rete, una crescente attenzione verso solver basati su euristiche, ad es. Timefold, Hexaly, Seeker. Non che i solver MILP non impieghino metodi di esplorazione diretta dello spazio delle soluzioni, le cosiddette euristiche primali, ma vengono impiegati a supporto di un algoritmo esatto. Nei solver euristici, invece, la ricerca nello spazio primale è il motore principale, spesso basato su paradigmi molto più semplici come la ricerca locale.

Scrivo questo articolo per cercare di sistematizzare quanto ho appreso relativamente alle differenze di progettazione e di approccio mentale fra solver tradizionali e solver euristici, e per spiegare perché sono diventato un grande fan di questi ultimi.

Le ragioni principali del mio ottimismo sono due. La prima riguarda il presente: questi solver allargano notevolmente il perimetro dei problemi attaccabili con uno strumento general-purpose. Il motore risolutivo non pretende quasi nulla dal modello: non serve la linearità o una specifica struttura algebrica, ma serve soltanto poter valutare l’effetto di una modifica sulla soluzione. Nella pratica, la maggior parte dei problemi si possono scrivere “così come sono”, e il tempo del modellatore finisce sul problema di business anziché in acrobazie per compiacere il solver. La seconda riguarda il futuro: mi aspetto che nel giro di pochi anni una quota crescente di problemi, oggi appannaggio esclusivo di algoritmi scritti ad hoc, diventi terreno di solver general-purpose.

I MILP solver sono una tecnologia straordinaria. Hanno raggiunto livelli di altissima sofisticazione grazie a decenni di ricerca e sviluppo, le librerie di modellazione sono estremamente mature, e qualsiasi specialista di ricerca operativa è in grado di utilizzarli efficacemente per modellare e risolvere i problemi più disparati. Sono ad oggi lo stato dell’arte per problemi di tipo network flow, unit commitment, supply chain network design, eccetera, in generale tutte le classi di problemi in cui il rilassamento continuo è forte.

L’approccio di modellazione di un MILP solver è di natura algebrica: tutto ciò che dipende da una decisione diventa una variabile, e la consistenza reciproca delle variabili viene imposta mediante vincoli. Funzione obiettivo e vincoli devono essere espressioni lineari: svariate famiglie di non linearità comuni (predicati logici, funzioni lineari a tratti) si possono modellare, ma la performance del modello spesso ne risente in modo significativo, tipicamente perché il rilassamento continuo diventa molto più debole. In pratica, è molto facile rovinare un modello efficiente aggiungendo una singola classe di vincoli brutti. Altre famiglie di non linearità, ad es. funzioni continue generiche o a scatola nera, non si possono proprio modellare.

Consideriamo, a titolo di esempio, un CVRP classico. In una formulazione MILP, la struttura combinatoria del problema, ovvero il fatto che una soluzione sia un insieme di sequenze, resta dispersa in una costellazione di binarie che il solver deve faticosamente ricomporre. Va detto che allo stato dell’arte, mediante tecniche avanzate di branch-and-price-and-cut, è possibile risolvere all’ottimo istanze di qualche centinaio di clienti, risultato tutt’altro che modesto. Il mio punto è un altro: nel momento in cui il problema del cliente si porta dietro i suoi n-mila vincoli reali, quella strada richiede di scrivere un algoritmo su misura, che è esattamente ciò che in un mio post precedente ho definito essere l’ultima spiaggia, a causa degli elevati costi di sviluppo e manutenzione.¹

A questo punto, è ragionevole domandarsi se le strutture combinatorie che appaiono più frequentemente possano essere dichiarate anziché ricostruite. Questo approccio è da lungo tempo praticato nel mondo della programmazione a vincoli (CP). Un vincolo globale come AllDifferent, Cumulative, NoOverlap o Circuit è un’astrazione che si porta dietro un algoritmo specializzato alla gestione della struttura combinatoria di quel vincolo. Nell’esempio di AllDifferent, il modellatore dichiara che quelle variabili devono essere tutte diverse, e il solver attiva un propagatore specializzato che sfronda l’albero di ricerca molto più efficientemente di una riformulazione lineare. In generale, quanto più la struttura combinatoria del problema è catturata da vincoli globali, tanto più efficace è la propagazione, e quindi la ricerca.²

C’è però una seconda linea di ricerca nella programmazione a vincoli che, a mio avviso, non gode di tutta la fama che meriterebbe. A cavallo fra la fine degli anni ’90 e i primi anni 2000, Pascal Van Hentenryck e Laurent Michel si sono posti una domanda (che suona ovvia soltanto col senno di poi): se la programmazione a vincoli ha reso dichiarativa la ricerca ad albero, perché non fare lo stesso con la ricerca locale? Ne sono usciti prima Localizer, poi il linguaggio Comet, e infine il libro “Constraint-Based Local Search”, in cui questo filone viene sistematizzato.³

Le due idee centrali della Constraint-Based Local Search (CBLS) sono esattamente quelle che troviamo oggi sotto il cofano dei solver euristici. La prima sono gli invarianti, ovvero vincoli a senso unico del tipo “questa quantità è per definizione la somma di quelle altre”, che il sistema si impegna a mantenere aggiornati a ogni modifica della soluzione. La seconda sono gli oggetti differenziabili, ovvero vincoli e funzioni obiettivo capaci di dire quanto costerebbe una mossa prima che la mossa venga eseguita.⁴ Messe insieme, permettono di valutare centinaia di migliaia di mosse al secondo anziché ricostruire la valutazione della soluzione da capo ogni volta.

Veniamo quindi all’architettura dei moderni solver euristici. Gli ingredienti principali che ho identificato sono i seguenti: astrazioni di modellazione di alto livello oltre le classiche variabili intere e continue, mosse di ricerca specializzate per quelle astrazioni, gestione di alcune classi di vincoli mediante penalità in funzione obiettivo, e un motore di ricalcolo incrementale dello stato della soluzione.

Le astrazioni decisionali di alto livello sono un’introduzione relativamente recente, e a mio avviso rappresentano lo sviluppo più interessante sul fronte dei solver euristici. Ad esempio, Timefold e Hexaly supportano la definizione di liste di dimensione variabile come variabile decisionale. Questa astrazione è l’ideale per modellare efficientemente problemi le cui decisioni sono delle permutazioni. Nell’esempio di un CVRP, possiamo modellare le visite effettuate da un veicolo con una singola lista, e i vincoli di capacità diventano una somma calcolata scorrendo la lista con un ciclo for. Il solver sa che quell’oggetto è una sequenza, e può quindi applicare operatori specializzati per quella struttura dati, ad es. invertire una sottosequenza o spostare un segmento da una lista all’altra, anziché limitarsi a cambiare il valore di una binaria (e sperare che ne esca qualcosa di sensato). Possiamo fare dei discorsi analoghi sugli insiemi non ordinati e sugli intervalli.⁵ Il risultato non è soltanto eleganza espressiva: sfruttando queste astrazioni, i solver euristici riportano numeri che fino a poco tempo fa erano fuori discussione per un solver general-purpose.⁶

Ne consegue un approccio di modellazione che definirei orientato alla computazione, anziché algebrico. Si dichiara un insieme limitato di variabili decisionali, e tutte le quantità che dipendono da esse si calcolano mediante procedure familiari a qualsiasi programmatore: cicli, espressioni condizionali, accessi indicizzati ad array. Il risultato non è soltanto un insieme molto più ristretto di variabili decisionali (e quindi una ricerca più efficiente), ma anche che il modellatore viene obbligato a ragionare su quali siano i reali gradi di libertà del problema di business, il che è un esercizio estremamente salutare. Nella mia esperienza, la domanda “quali sono le decisioni?” produce conversazioni con gli esperti di dominio di gran lunga più utili della domanda “quali sono le variabili?”.

Le mosse di ricerca specializzate su certe classi di strutture dati e vincoli sono, a mio avviso, l’analogo dei vincoli globali della programmazione a vincoli. Si tratta dello stesso principio, ma con un fine diverso. In programmazione a vincoli la codifica della struttura combinatoria serve a potare efficientemente l’albero di ricerca, mentre nella ricerca locale serve a muoversi da una soluzione all’altra senza violare la fattibilità.

Infine, il motore di calcolo incrementale e la gestione dei vincoli mediante penalità sono eredità diretta della Constraint-Based Local Search. In particolare, per quelle classi di vincoli che rendono complicato passare da una soluzione all’altra senza rompere la fattibilità, risulta estremamente più efficiente formulare una funzione costo ad alta priorità e lasciare che il solver utilizzi questo gradiente per guidare la ricerca. Tuttavia, affinché questo approccio sia efficace, è necessario che parte della struttura combinatoria del problema sia codificata dalle appropriate strutture e vincoli globali. Questa frase dalla documentazione di Hexaly riassume chiaramente il concetto:

Turning too many constraints into objectives will lead to a model without any structure, whereas one of the strengths of Hexaly Optimizer is to perform moves preserving the feasibility and thus “making sense”.

Vorrei spendere qualche parola anche sulla scalabilità rispetto all’hardware a disposizione. Questo è un argomento su cui ho cambiato idea più volte mentre scrivevo questo articolo, per cui spero che quello che sto per dire possa risultare sensato (anche perché qualsiasi cosa io scriva sull’argomento mi sembra di fare un torto a qualcuno). Partiamo dal fatto che i solver MILP sono notoriamente difficili da parallelizzare, e nella mia esperienza, su carichi di lavoro generici, si osservano speedup vicini al logaritmo del numero di core.⁶ Ma neanche la ricerca locale scala arbitrariamente: le ricerche indipendenti in stile portfolio riducono la varianza dell’esito più che il tempo alla soluzione, e la valutazione parallela delle mosse si scontra con il fatto che la ricerca resta sequenziale. La grossa differenza risiede, a mio avviso, in dove finisce il collo di bottiglia. Nei solver euristici è il throughput di valutazioni incrementali, che è un problema di località dei dati, di layout in memoria, eccetera, mentre nel branch-and-cut è la struttura logica della ricerca, su cui l’hardware aiuta meno. In altre parole, la mia impressione di altissimo livello è che vi siano molte più opportunità di ingegnerizzazione e miglioramento delle performance nei solver euristici.

A questo punto, dopo aver tessuto le lodi dei solver euristici per una ventina di paragrafi, passiamo al lato duale (heh heh) della questione.

Una limitazione dei solver euristici è che generalmente non forniscono alcun bound duale, e non sono in grado di dimostrare che un problema è infattibile. Il gap di ottimalità è utile come criterio di terminazione ben definito, sicuramente più comprensibile di un limite di tempo arbitrario. Lo trovo invece meno utile come certificato della qualità della soluzione, perché certifica l’ottimalità rispetto a un modello della realtà, mentre nei problemi industriali le approssimazioni di modellazione e gli errori sui dati dominano di parecchi ordini di grandezza. In particolare, un dato può essere vecchio, approssimato, stimato o semplicemente sporco, e a fronte di un dato imperfetto un gap dello 0% non porta particolare valore. Inoltre, la baseline con cui ci confrontiamo non è quasi mai l’ottimo, ma è il piano che oggi viene fatto a mano o con un sistema di semplici regole statiche, e il delta rispetto a quello è la metrica che il cliente effettivamente compra. La dimostrazione di infattibilità di un problema è al contrario molto più utile, perché spesso e volentieri segnala un problema nei dati di input che altrimenti sarebbe stato complicato identificare.

Un altro aspetto da non sottovalutare è il cambiamento mentale richiesto per utilizzare efficacemente questo tipo di solver. I solver MILP hanno una penetrazione di mercato enorme, e qualsiasi specialista di ricerca operativa è in grado di metterci le mani. Niente di tutto questo vale (ancora) per i solver euristici. Il modellatore deve imparare a pensare in termini di decisioni e quantità derivate anziché di variabili e vincoli, deve decidere quali vincoli siano struttura (e vadano dichiarati) e quali siano penalità (e vadano in funzione obiettivo), e deve avere un’idea di alto livello di quali mosse il solver sia in grado di fare. La letteratura è meno abbondante e i modelli non sono facilmente portabili da un solver all’altro. Non è una barriera insormontabile, ma è una barriera, e per alcune aziende può essere un ostacolo significativo all’adozione.

Infine, ci sono classi di problemi per cui la ricerca locale non è per forza lo strumento giusto. Il caso più evidente l’ho già citato all’inizio: problemi in cui il rilassamento continuo è forte, dove un MILP solver arriva all’ottimo dimostrato in tempi ragionevoli. Meno ovvio è il caso dei problemi fortemente vincolati in cui trovare una qualsiasi soluzione ammissibile è la parte difficile, e l’approccio a penalità in funzione obiettivo non risulta efficace. Aggiungerei anche i problemi prevalentemente continui, dove simplesso e punto interno difficilmente hanno rivali.

Alcune di queste limitazioni si stanno attenuando grazie a un’ibridazione sempre più spinta fra metodi esatti ed euristici. Hexaly, ad esempio, attiva strategie risolutive specializzate (MILP, punto interno, eccetera) quando riconosce determinate strutture nel modello, ed è quindi in grado di fornire bound duali o di dimostrare l’infattibilità di un problema. È interessante notare come questa ibridazione sia speculare rispetto a quella dei solver MILP. In un MILP solver l’algoritmo esatto è il motore principale e le euristiche lavorano al suo servizio. In Hexaly succede il contrario: la ricerca locale è il motore principale, e gli algoritmi esatti vengono invocati soltanto quando il solver riconosce nel modello una struttura su cui sanno lavorare bene. Non sarei stupito se nel prossimo futuro vedessimo questo tipo di ibridazione applicato anche ad altri solver euristici.

Per concludere, provo a tirare le somme. Le idee alla base dei solver euristici esistono da decenni e hanno una letteratura solida alle spalle, ma è negli ultimi anni che l’ingegnerizzazione dei prodotti ha fatto veramente il salto di qualità. Il risultato è che classi di problemi fino a poco tempo fa fuori dalla portata di un solver generico oggi sono trattabili, con risultati ampiamente soddisfacenti. Tutti i segnali che vedo mi fanno pensare che questa traiettoria continuerà. In tal senso, mi aspetto che il lavoro del ricercatore operativo nell’industria si sposti sempre di più dal progettare algoritmi specializzati al capire a fondo i problemi di business. Per me è un’ottima notizia! Vuol dire che potrò passare più tempo a ragionare sul problema del cliente e a iterare più in fretta. Infatti, il valore di un progetto di ottimizzazione si crea per la maggior parte nel dialogo continuativo con gli esperti di dominio, nel continuo affinamento del processo decisionale. Ogni ora che il solver mi fa risparmiare è un’ora che posso spendere a capire meglio il dominio.

Fatemi sapere le vostre esperienze nell’uso dei solver, se siete d’accordo con le mie impressioni, o se ho omesso qualcosa.