Solver

Un solver è la categoria di software che legge un modello di ottimizzazione matematica — tipicamente tramite un formato di file come LP, MPS, NL, OPL o CNF, oppure tramite un binding di linguaggio di modellazione/API — e produce algoritmicamente una soluzione ottima (o quasi ottima entro una tolleranza), valori primali e duali, costi ridotti, informazioni di sensitività e un report di ammissibilità. Nell'ecosistema RO i solver si dividono per classe di problema: programmazione lineare (LP), intera mista lineare (MILP), quadratica (QP), intera mista quadratica (MIQP), conica del second'ordine (SOCP), semidefinita (SDP), non lineare generale (NLP), programmazione a vincoli (CP) e ottimizzazione globale. I motori algoritmici si raggruppano in famiglie: per LP il metodo simplex di Dantzig (1947) e la famiglia dei punti interni di Karmarkar (1984) con varianti barrier-predictor-corrector; per MILP branch-and-cut (Padberg e Rinaldi 1991) su branch-and-bound (Land e Doig 1960), branch-and-price (Barnhart et al. 1998), presolving, euristiche di ammissibilità, Gomory e altri livelli di generazione di tagli; per NLP sequential quadratic programming, punti interni e varianti trust-region. I solver si dividono in due grandi gruppi: **solver commerciali** — prodotti licenziati ad alta performance con ampio supporto enterprise e aggressivi strati euristici; **solver open-source** — progetti liberamente utilizzabili, sufficienti per carichi accademici e di PMI, 2-10x più lenti dei pari commerciali su alcune classi di problema. I modelli si passano via formati di file standard (LP, MPS, NL e simili) o tramite linguaggi algebrici di modellazione e i pacchetti di modellazione matematica di linguaggi di calcolo scientifico. Le performance comparative si seguono in serie indipendenti di benchmark accademici. Bixby (2002) e Achterberg (2007) documentano l'accelerazione dei solver MILP negli ultimi trent'anni — non solo hardware ma presolving, simplex duale, generazione di tagli ed euristiche apportano insieme un fattore di accelerazione dell'ordine di 10⁶.