Gap di Ottimalità

Il gap di ottimalità quantifica la distanza tra il valore della migliore soluzione ammissibile trovata (upper bound UB nella minimizzazione) e il miglior bound duale ottenuto finora (lower bound LB); esistono due definizioni standard. Gap assoluto = |UB - LB|. Gap relativo (la variante canonica nel MILP) = |UB - LB| / max(ε, |UB|), oppure in alcuni solver |UB - LB| / max(ε, |LB|) — la scelta del denominatore varia per fornitore, con ε a protezione dalla divisione per zero. Un gap nullo certifica l'incumbent come ottimo e termina l'algoritmo; in pratica i solver si fermano con bandiera 'quasi-ottimo' appena il gap scende sotto una tolleranza definita dall'utente (tipicamente 0,01-1%). Il fondamento logico è la dualità: in LP la dualità debole fornisce UB ≥ LB per ogni coppia primale-duale ammissibile, e la dualità forte la trasforma in uguaglianza. Nel MILP il rilassamento LP produce LB, il branch-and-bound lo aggiorna nodo per nodo e le euristiche primali insieme all'esplorazione per ramificazione aggiornano UB. Interpretazione: un gap del 5% significa 'il valore della soluzione è al più 5% peggiore dell'ottimo' — nessun ulteriore miglioramento è matematicamente possibile al di sotto del LB noto. Usi pratici: comunicazione del rischio al management, decisioni di terminazione anticipata (trade-off tempo-qualità in lunghe esecuzioni di branch-and-cut) e benchmarking di euristiche. Il gap di dualità di Lagrange nella programmazione convessa non lineare e il gap di rilassamento nella programmazione non convessa sono concetti analoghi. Riferimenti canonici: Nemhauser e Wolsey (1988) e Wolsey (1998).