2025-11-13T22:16:11.184529

Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction

Li, Chen, Li et al.
By exploiting the correlation between the structure and the solution of Mixed-Integer Linear Programming (MILP), Machine Learning (ML) has become a promising method for solving large-scale MILP problems. Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high dimensionality of the solution space. Instead of directly learning the optimal solution, this paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. However, current approaches rely only on the optimal reduced model, overlooking the significant preference information of all reduced models. To address this issue, this paper proposes a preference-based model reduction learning method, which considers the relative performance (i.e., objective cost and constraint feasibility) of all reduced models on each MILP instance as preferences. We also introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks. Moreover, we propose a SetCover based pruning method to control the number of reduced models (i.e., labels), thereby simplifying the learning process. Evaluation on real-world MILP problems shows that 1) compared to the state-of-the-art model reduction ML methods, our method obtains nearly 20% improvement on solution accuracy, and 2) compared to the commercial solver Gurobi, two to four orders of magnitude speedups are achieved.
academic

Risoluzione veloce e interpretabile di programmi lineari interi misti mediante apprendimento della riduzione del modello

Informazioni di base

  • ID articolo: 2501.00307
  • Titolo: Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction
  • Autori: Yixuan Li, Can Chen, Jiajun Li, Jiahui Duan, Xiongwei Han, Tao Zhong, Vincent Chau, Weiwei Wu, Wanyuan Wang
  • Classificazione: cs.LG cs.AI
  • Data di pubblicazione: 31 dicembre 2024 (preprint arXiv)
  • Istituzioni: Scuola di Ingegneria Informatica dell'Università del Sud-Est, Laboratorio Noah's Ark di Huawei
  • Link articolo: https://arxiv.org/abs/2501.00307

Riassunto

Questo articolo propone un metodo di risoluzione basato su apprendimento automatico per problemi MILP (Mixed-Integer Linear Programming) su larga scala, sfruttando la correlazione tra la struttura e la soluzione dei MILP. A differenza dei metodi di apprendimento end-to-end esistenti, questo articolo apprende modelli equivalenti ridotti del MILP originale come fase intermedia. Il metodo propone un approccio di apprendimento della riduzione del modello basato su preferenze, considerando le prestazioni relative di tutti i modelli ridotti su ogni istanza MILP come informazione di preferenza, e introduce un meccanismo di attenzione per catturare tale informazione. I risultati sperimentali mostrano che, rispetto ai metodi ML di riduzione del modello all'avanguardia, questo metodo migliora la precisione della soluzione di quasi il 20%, e rispetto al risolutore commerciale Gurobi realizza un'accelerazione di 2-4 ordini di grandezza.

Contesto di ricerca e motivazione

Definizione del problema

La programmazione lineare intera mista (MILP) ha applicazioni diffuse in settori critici come la logistica della catena di approvvigionamento, la pianificazione dei servizi, la gestione dell'energia e la pianificazione dei trasporti. Nelle applicazioni industriali reali, le istanze MILP coinvolgono tipicamente decine di migliaia di variabili decisionali e vincoli. I risolutori commerciali esistenti si basano su metodi di soluzione esatti con costi computazionali elevati, incapaci di soddisfare i requisiti in tempo reale.

Motivazione della ricerca

  1. Problema di scalabilità: I metodi ML esistenti apprendono direttamente la mappatura dello spazio di soluzione ad alta dimensione, presentando problemi di scalabilità
  2. Mancanza di interpretabilità: Gli approcci end-to-end non forniscono soluzioni interpretabili o comprensione intuitiva
  3. Utilizzo insufficiente dell'informazione di preferenza: I metodi di riduzione del modello esistenti si concentrano solo sul modello ridotto ottimale, trascurando l'importante informazione di preferenza di tutti i modelli ridotti

Limitazioni dei metodi esistenti

  • Previsione end-to-end della soluzione: La bassa precisione di previsione dovuta alla dimensionalità dello spazio di soluzione
  • Apprendimento dell'ottimizzazione: Efficienza limitata dai vincoli dell'orizzonte decisionale
  • Metodi di riduzione del modello esistenti: Trattano i modelli ridotti fattibili come etichette ideali equivalenti, non sfruttando pienamente le informazioni comparative

Contributi principali

  1. Propone un metodo di apprendimento della riduzione del modello basato su preferenze: Converte le prestazioni dei modelli ridotti in informazioni di preferenza, sfruttando pienamente le informazioni comparative nello spazio istanza-strategia
  2. Progetta un'architettura con meccanismo di attenzione: Cattura la correlazione tra istanze e modelli ridotti preferiti, migliorando l'accuratezza dell'apprendimento
  3. Introduce la tecnica di potatura SETCOVER: Controlla il numero di modelli ridotti (etichette), generando l'insieme di etichette minimo fattibile per tutte le istanze
  4. Realizza miglioramenti significativi delle prestazioni: Verificato su problemi MILP reali, con miglioramento della precisione del 20% rispetto ai metodi esistenti e accelerazione di 2-4 ordini di grandezza rispetto a Gurobi

Dettagli del metodo

Definizione del compito

Dato un problema MILP parametrizzato:

min f(c, x)
s.t. g(A, x) ≤ b
     xI ∈ Z^d, x_{-I} ∈ R^{n-d}

dove θ = ⟨A, c, b⟩ rappresenta i parametri MILP.

Definizione della strategia ottimale: s*(θ) = (T(θ), x*_I(θ)), che include l'insieme dei vincoli stretti T(θ) e i valori delle variabili intere nella soluzione ottimale.

Obiettivo: Apprendere la mappatura dai parametri θ alla strategia ottimale s*(θ).

Architettura del modello

1. Fase di generazione e potatura della strategia

  • Generazione della strategia: Utilizza lo stimatore Good-Turing per determinare il numero di istanze fino a quando N₁/N scende al di sotto della soglia
  • Potatura della strategia: Costruisce un grafo bipartito istanza-strategia G(V_θ, V_s, E), trasformando il problema di potatura in un problema SETCOVER
  • Algoritmo greedy: Seleziona iterativamente il nodo strategia che copre il maggior numero di nodi istanza non coperti

2. Apprendimento della strategia basato su preferenze

Calcolo delle preferenze:

r(θᵢ, sⱼ) = -log(p(θᵢ, sⱼ) + d(θᵢ, sⱼ))

dove p(θᵢ, sⱼ) è l'infeasibility e d(θᵢ, sⱼ) è la suboptimality.

Definizione della preferenza:

(θᵢ, sⱼ) ≻ (θᵢ, sₖ) ⇔ r(θᵢ, sⱼ) > r(θᵢ, sₖ)

Codifica del meccanismo di attenzione:

A([θᵢ, S^P]) = softmax(QK^T/√d)V

Tratta ogni coppia istanza-strategia ⟨θᵢ, sⱼ⟩ come token, estraendo caratteristiche attraverso un meccanismo di attenzione multi-strato.

Punti di innovazione tecnica

1. Ottimizzazione del campionamento delle preferenze

Sfrutta la transitività delle preferenze, ordinando le strategie per preferenza, richiedendo solo M_P campioni di preferenza ordinati anziché (M_P choose 2) confronti accoppiati, riducendo la complessità del campione da quadratica a lineare.

2. Funzione di perdita doppia

  • Perdita di preferenza:
L_p(φ) = -1/N ∑∑[μᵢ,ⱼ log(pᵢ,ⱼ) + (1-μᵢ,ⱼ) log(1-pᵢ,ⱼ)]
  • Perdita di differenza di ricompensa:
L_d(φ) = 1/N ∑∑(r̂ᵢ,σ(j) - r̂ᵢ,σ(j+1) - δᵢ,ⱼ)²
  • Perdita totale: L_total(φ) = λ₁L_p(φ) + λ₂L_d(φ)

3. Inferenza della strategia Top-k

Nella fase online seleziona le strategie Top-k come candidati, valutando i modelli ridotti e selezionando la strategia con infeasibility più bassa.

Configurazione sperimentale

Dataset

  1. MIPLIB: Problemi MILP reali in 6 scenari, con scala e difficoltà di risoluzione variabili
  2. Problema di gestione dell'energia delle celle a combustibile: Regola la complessità del problema aumentando il passo temporale T
  3. Problema di gestione dell'inventario: 5 problemi industriali reali su larga scala, con una media di circa 100.000 vincoli

Metriche di valutazione

Metriche di accuratezza:

accuracy = 1/N |{θᵢ | p(θᵢ, ŝⱼ) ≤ ε₁ ∧ d(θᵢ, ŝⱼ) ≤ ε₂}|

dove la tolleranza di infeasibility e suboptimality sono entrambe impostate a 1×10⁻⁴.

Metodi di confronto

  1. Gurobi: Risolutore commerciale avanzato (con warm start abilitato)
  2. Gurobi Heuristic: Modalità euristica di Gurobi (limite di tempo 1 secondo)
  3. MLOPT: Metodo di apprendimento basato su riduzione del modello più applicabile
  4. Predict and Search: Metodo basato su previsione della soluzione

Dettagli di implementazione

  • Ottimizzatore: AdamW, tasso di apprendimento 0.0001-0.001
  • Decadimento del tasso di apprendimento: Decadimento lineare di 0.9 ogni 10 epoche, per 100 epoche totali
  • Dimensione del batch: 128
  • Parametro di coordinamento λ₁: 0.8-0.9

Risultati sperimentali

Risultati principali

Dataset MIPLIB

  • Nella maggior parte degli scenari, questo metodo mostra prestazioni simili a Gurobi in termini di suboptimality e feasibility
  • Rispetto a MLOPT, mostra un leggero vantaggio in feasibility e miglioramenti significativi in suboptimality
  • Il metodo euristico mostra prestazioni inferiori in più metriche a causa del limite di tempo

Gestione dell'energia delle celle a combustibile

  • Miglioramento dell'accuratezza di quasi il 39% sul problema più complesso
  • Effetto significativo della potatura della strategia, specialmente con l'aumento della scala del problema
  • Prestazioni Top-k: le prestazioni del modello migliorano con l'aumento di k, superando MLOPT con lo stesso valore di k

Problemi di gestione dell'inventario

  • Mantiene la feasibility su tutte le istanze, con accuratezza stabile intorno al 90%
  • Sul problema di massima scala P5 (oltre 270.000 vincoli), miglioramento di circa il 30% rispetto a MLOPT

Analisi del tempo di calcolo

  • Miglioramento del tempo di 3 ordini di grandezza rispetto a Gurobi
  • Il tempo rimane relativamente stabile con l'aumento della scala del problema
  • Differenza minima rispetto a MLOPT (con lo stesso valore di k)
  • Il calcolo Top-k può essere parallelizzato, migliorando ulteriormente la velocità

Esperimenti di ablazione

Apprendimento delle preferenze vs adattamento della ricompensa

Sul dataset delle celle a combustibile, il metodo delle preferenze mostra un miglioramento medio dell'accuratezza di circa il 9% rispetto all'adattamento diretto della ricompensa, con prestazioni superiori nelle metriche di infeasibility e suboptimality.

Campionamento ordinato vs campionamento tradizionale

Il metodo ordinato mostra un miglioramento medio dell'accuratezza di circa l'8% rispetto al campionamento di preferenza tradizionale su varie scale di problema, riducendo significativamente i costi di addestramento.

Lavori correlati

Classificazione dei metodi di risoluzione MILP basati su ML

  1. Previsione end-to-end della soluzione: Apprendimento diretto della mappatura da istanza MILP a soluzione
  2. Apprendimento dell'ottimizzazione: Apprendimento per accelerare metodi esatti/euristici tradizionali
  3. Apprendimento della semplificazione MILP: Apprendimento della preelaborazione o riduzione della scala MILP

Relazione di questo articolo con lavori esistenti

  • Rispetto ai metodi end-to-end: Evita il problema dell'apprendimento dello spazio di soluzione ad alta dimensione
  • Rispetto all'apprendimento dell'ottimizzazione: Non limitato dai vincoli dell'orizzonte decisionale
  • Rispetto alla riduzione del modello esistente: Sfrutta pienamente l'informazione di preferenza anziché considerare solo la strategia ottimale

Conclusioni e discussione

Conclusioni principali

  1. L'apprendimento della riduzione del modello basato su preferenze migliora significativamente le prestazioni di risoluzione MILP
  2. La tecnica di potatura SETCOVER controlla efficacemente il numero di strategie
  3. Il meccanismo di attenzione cattura con successo la correlazione istanza-strategia
  4. Realizza un'accelerazione significativa e un miglioramento dell'accuratezza su problemi industriali reali

Limitazioni

  1. Il metodo è applicabile a problemi MILP omogenei con struttura ripetitiva
  2. Richiede dati di addestramento sufficienti per apprendere un modello di preferenza efficace
  3. La fase di generazione della strategia richiede ancora un risolutore commerciale per ottenere la soluzione ottimale
  4. Lo spazio delle strategie potrebbe rimanere grande nei problemi su larga scala

Direzioni future

  1. Estensione a tipi di problemi di ottimizzazione più ampi
  2. Riduzione della dipendenza dai dati di addestramento
  3. Ulteriore miglioramento dell'efficienza della generazione della strategia
  4. Esplorazione di metodi di apprendimento non supervisionato o semi-supervisionato

Valutazione approfondita

Punti di forza

  1. Forte innovazione: Prima applicazione sistematica dell'apprendimento delle preferenze alla riduzione del modello MILP
  2. Fondamenti teorici solidi: Basato sul concetto di riduzione del modello della teoria della ricerca operativa
  3. Esperimenti completi: Verifica su più dataset reali, inclusi problemi a livello industriale
  4. Prestazioni significative: Realizza miglioramenti sostanziali rispetto ai metodi esistenti
  5. Buona interpretabilità: I modelli ridotti corrispondono a modalità operative interpretabili

Carenze

  1. Limitazione dell'ambito di applicazione: Principalmente applicabile a problemi MILP parametrizzati
  2. Costo di addestramento: Richiede ancora una grande quantità di dati etichettati (soluzioni ottimali)
  3. Analisi teorica insufficiente: Mancanza di garanzie teoriche sulla convergenza e sulla capacità di generalizzazione
  4. Linee di base di confronto limitate: Principalmente confrontato con un metodo di apprendimento (MLOPT)

Impatto

  1. Contributo accademico: Fornisce una nuova direzione di ricerca nel campo ML4CO
  2. Valore pratico: Potenziale di applicazione diretta nella risoluzione MILP industriale
  3. Riproducibilità: Descrizione del metodo dettagliata e configurazione sperimentale chiara
  4. Significato ispiratore: L'idea dell'apprendimento delle preferenze può essere estesa ad altri problemi di ottimizzazione

Scenari applicabili

  1. Pianificazione stocastica online: Necessità di risolvere rapidamente istanze MILP simili
  2. Ottimizzazione della catena di approvvigionamento: Problemi con parametri variabili ma struttura fissa
  3. Pianificazione in tempo reale: Applicazioni con requisiti rigorosi sul tempo di risoluzione
  4. Ottimizzazione industriale su larga scala: Problemi difficili da gestire per i risolutori commerciali

Riferimenti bibliografici

L'articolo cita importanti lavori nel campo, inclusi:

  • Bengio, Lodi, and Prouvost (2021): Sondaggio su ML per l'ottimizzazione combinatoria
  • Bertsimas and Stellato (2022): Ottimizzazione intera mista online
  • Misra, Roald, and Ng (2022): Apprendimento per l'ottimizzazione vincolata
  • E numerosi altri lavori correlati su apprendimento end-to-end e apprendimento dell'ottimizzazione

Valutazione complessiva: Questo è un articolo di ricerca di alta qualità che propone un metodo innovativo di apprendimento delle preferenze nel campo ML4CO. Sebbene presenti alcune limitazioni, i suoi contributi teorici e il valore pratico sono entrambi notevoli, fornendo un nuovo percorso efficace per la risoluzione di MILP su larga scala.