L’approccio risolutivo proposto si compone di 3 fasi, la prima delle quali ha il compito di trovare una soluzione iniziale mediante una qualsiasi euristica. In questa sede è stata approfondita e sperimentata la tecnica euristica della Feasibility Pump (FP), proposta da Lodi and Fischetti (2005). Dovendo determinare una soluzione iniziale “feasible”, nel passo 1 dell’algoritmo si risolve il rilassato lineare del problema in esame. Tale risoluzione fornisce, in generale, una soluzione con componenti frazionarie (che, però, rispetta tutti gli altri vincoli del problema). Nel passo successivo (il 2) ogni componente della soluzione viene arrotondata ad un valore intero (ad es.: se il valore della variabile è minore di 0.5 la variabile assume il valore zero altrimenti assume il valore 1). Come gli stessi autori suggeriscono, per accelerare il processo di risoluzione, il passo 1 può essere sostituito con la generazione di una soluzione completamente casuale, dove ogni componente viene inizializzata con un numero casuale compreso tra zero ed uno che, in seguito, dovrà essere arrotondato (step 2), per ottenere una soluzione intera di riferimento, n , con tutte le componenti intere. A questo punto entra in gioco la funzione ∆ , n , chiamata anche distanza di Hamming, che è definita come segue:
∆< , ̅ = = op − ̅ p ∈q
Tale espressione sarà la funzione obbiettivo nel problema che dovrà essere risolto ad ogni iterazione, nella euristica FP. Il problema avrà la stessa regione ammissibile del problema originario, i vincoli d’interezza saranno sempre rilassati mentre l’obbiettivo diventerà quello di trovare una soluzione frazionaria, , ammissibile e che minimizzi la distanza dalla soluzione n (che non è ammissibile, perché in generale non rispetta i vincoli imposti dal problema, pur avendo tutte componenti intere). Dopo aver determinato una nuova soluzione, se dovesse accadere che le sue componenti non siano intere occorrerà ripetere l’operazione di arrotondamento. L’algoritmo sarà arrestato quando la distanza di Hamming diventerà nulla, ovvero quando la soluzione di riferimento, n, risulterà non solo intera ma pure ammissibile. Potrebbero verificarsi alcuni piccoli inconvenienti durante la determinazione di una soluzione iniziale per il problema originario, poiché il processo potrebbe entrare in un ciclo e rimanerci all’infinito. Sono due le cause che potrebbero determinare un ciclo infinito: la prima è legata ad un non variazione della soluzione di riferimento, n, cioè la soluzione di riferimento, n, è la stessa del passo precedente; la seconda causa è legata al verificarsi di un ciclo di soluzioni, ovvero alla riproposizione delle stesse soluzioni negli ultimi passi dell’algoritmo. La prima situazione di ciclo è facilmente identificabile e l’azione che si adopera per uscire da una simile condizione di stallo è quella di perturbare la soluzione di riferimento facendo cambiare il valore di una o più variabili da zero ad uno; oppure è possibile compiere un’azione di restart del processo, che consiste nel generare una soluzione completamente casuale e poi successivamente arrotondarla, facendo così ripartire il processo di ricerca. La seconda condizione di stallo viene controllata euristicamente, cioè se nelle ultime KK (gli autori suggeriscono 70) iterazioni il valore H della distanza di Hamming non è migliorato allora viene eseguita un’azione di restart come descritto in precedenza. L’algoritmo proposto dagli autori è completamente generale ed indipendente dal modello da risolvere. Dopo aver trovato una soluzione iniziale con la feasibility pump (o attraverso un’altra euristica), è stato sviluppato un algoritmo di local branching indipendente dal problema da risolvere. Tale algoritmo viene iterato fintanto che la soluzione corrente può essere migliorata. In tale algoritmo nessuna fase di intensificazione viene intrapresa poiché è stato osservato sperimentalmente che l’intensificazione non apporta, quasi sempre, alcun miglioramento alla soluzione corrente. Se il processo principale non riesce a trovare una soluzione migliore di quella corrente (che fornisce un UB al nostro problema) viene compiuta una fase di diversificazione, che si compone di un certo numero di iterazioni fissato dall’utente (nel nostro caso è uguale a 3), nella quale si esplorano differenti partizioni della regione ammissibile in modo da focalizzare la ricerca in determinate aree che potrebbero essere più promettenti. Quando, in una delle iterazioni della diversificazione, si riesce a trovare una soluzione migliore l’algoritmo si arresta e continua ad esplorare la regione ammissibile con le stesse regole usate prima nella fase di diversificazione, riprendendo la sua nomale esecuzione; altrimenti, se nessuna iterazione nella fase di diversificazione trova una soluzione migliore, l’algoritmo si arresta. Ogni nodo dell’albero del local branching viene risolto entro un certo limite di tempo ed imponendo che la funzione obbiettivo sia compresa tra un lower bound ed un upper bound:
r# ≤ . ]. ≤ s#
Al fine di non riscontrare soluzioni peggiori rispetto a quella corrente, grazie al lower bound, si restringe la regione da esplorare. Una delle varianti proposte è sperimentate in questo lavoro è stata quella di usare la migliore soluzione ottenuta dal processo FP+LB come soluzione di riferimento per un ulteriore algoritmo di LB specializzato ad una formulazione matematica diversa da quella originaria, nel senso che presenta una regione ammissibile più ampia di quella precedente e la ingloba totalmente. Lo pseudo codice dell’algoritmo per il local branching implementato è il seguente: (1) Modello m=createModel(); (2) sol=inizialize(m); (3) while (true){ (4) addToModelFirstCut(m,sol); (5) addToModelSecondCut(m,sol); (6) addToModel_LB_&_UB(m,lowerBound,objectiveValue(sol)); (7) if(solve(m)){ (8) sol=getCurrentSolution(m); (9) }else{ (10) boolean noImprovements=true; (11) for(int iter=0;iter<maxDivesificationIter;iter++){ (12) addToModelFirstDiversificationCut(m,sol,iter); (13) addToModelSecondDiversificationCut(m,sol,iter); (14) addToModel_LB_&_UB(m,lowerBound,objectiveValue(sol)) (15) if(solve(m)){ (16) sol=getCurrentSolution(m); (17) noImprovements=false; (18) break; (19) } (20) } (21) if(noImprovements){ (22) break; (23) } (24) } (25) }
Dopo aver formulato il modello matematico su cui sarà applicata la tecnica del local branching (passo 1), occorre determinare una soluzione ammissibile per inizializzare l’euristica basata sul local branching. E si hanno tre possibilità. La prima, come già anticipato, prevede una chiamata ricorsiva ad un ulteriore metodo di local branching strutturato su un diverso problema le cui soluzioni sono un sotto insieme del problema che si vuole risolvere. La seconda alternativa è quella di risolvere il problema in modo euristico/meta euristico ed usare tale soluzione per inizializzare il local branching. La terza alternativa, che si può usare in qualsiasi circostanza e soprattutto quando non si dispone di un’euristica per il problema, prevede l’utilizzo della feasibility pump . L’algoritmo di local branching continua ad iterare (passo 3) fino a che a soluzione corrente sarà migliorata, altrimenti l’algoritmo si arresta grazie ai passi 21-23. Nel passo 4 si applica, al problema originario, il taglio di primo livello costruito sulla base della soluzione corrente, mentre nel passo 5 si applica al modello il taglio di secondo livello costruito sempre sulla base della soluzione corrente. Infine, al passo 6, si persegue la ricerca di una soluzione migliore utilizzando il lower bound e l’upper bound a disposizione per il problema, in modo da restringere la regione d’interesse. Al passo 7 viene risolto il modello derivante dal problema originale più i tagli di local branching. Se l’esito è positivo allora la soluzione corrente viene aggiornata e l’algoritmo continua con i passi da 4 a 7. Se al passo 7 non si dovesse trovare una soluzione migliorativa rispetto a quella corrente allora si deve diversificare la ricerca. I passi della diversificazione sono un numero finito che coincide con maxDiversificationIter (imposto dall’utilizzatore); inoltre la regione d’interesse viene sempre ristretta applicando i
migliori lower bound e l’upper bound conosciuti. Se in una delle fasi della diversificazione viene trovata una soluzione migliore la fase di diversificazione si arresta e l’algoritmo procede con i passi da 4 a 7. Come detto in precedenza, se alla fine della fase di diversificazione non è stata trovata una soluzione migliore allora l’algoritmo di local branching si arresta.