Generazione di Colonne nella Programmazione Lineare e il Problema del Taglio di Stock

Column Generation in Linear Programming and the Stock Cutting Problem

Come risolvere i problemi lineari con un grande numero di variabili decisionali illustrato con un esempio in Python

Foto di Jean Vella su Unsplash

Alcuni problemi di Programmazione Lineare (LP) derivanti da problemi combinatori diventano intrattabili a causa del grande numero di variabili coinvolte (Gilmore & Gomory, 1961). In tali problemi, il ritardo nell’implementazione delle colonne è una possibile alternativa di soluzione in quanto non include tutte le possibili variabili decisionali nel problema dall’inizio. Una classica applicazione è il problema di taglio di stock, in cui si deve decidere come tagliare un rotolo di una data larghezza in pezzi più piccoli per soddisfare le richieste di taglio determinate.

In questo articolo, alcuni degli aspetti teorici principali della generazione di colonne verranno presentati e illustrati con il problema di taglio di stock unidimensionale. Nella soluzione, sarà utilizzata la libreria Python scipy. Per chi fosse interessato, il codice completo può essere trovato in questo repository git.

In caso non si fosse ancora familiari con la Programmazione Lineare, potrebbe essere utile leggere la mia precedente introduzione sull’argomento per una migliore comprensione di questo articolo.

Programmazione lineare: Teoria e applicazioni

Concetti principali di ottimizzazione lineare e implementazione in Python

towardsdatascience.com

Se siete pronti per concetti più approfonditi insieme ad un esempio pratico, benvenuti a bordo.

Generazione di colonne: una panoramica

Quando si utilizza il ritardo nell’implementazione delle colonne per risolvere un LP, ad ogni iterazione, viene considerato un problema con solo un sottoinsieme di colonne. È chiamato il Problema Master Ristretto (RMP). Ad ogni iterazione, viene risolto il RMP e viene ottenuto il suo corrispondente vettore di variabili decisionali duali ottimali π. L’algoritmo utilizza quindi questo risultato per risolvere il sottoproblema o problema di pricing, che mira a trovare nuove variabili decisionali con costi ridotti negativi. Ricordiamo una definizione di costi ridotti.

Per qualsiasi variabile non di base, il costo ridotto per la variabile è l’importo di cui deve essere migliorato il coefficiente della funzione obiettivo della variabile non di base prima che tale variabile diventi una variabile di base in una soluzione ottimale dell’LP. Winston & Goldberg (2004)

Pertanto, includendo variabili con costi ridotti negativi, potremmo aspettarci contributi marginali al miglioramento del valore obiettivo. Ricordiamo l’interpretazione economica delle variabili duali come costi ombra. Una nuova variabile potrebbe potenzialmente comportare risparmi proporzionali al suo contributo al soddisfacimento dei vincoli dati i loro duali corrispondenti, aumentando il costo complessivo del suo coefficiente di costo.

Risolvendo il sottoproblema, identifichiamo un insieme S di colonne con il costo ridotto più basso dato i costi duali. Se non viene identificata alcuna colonna con costi ridotti negativi, ci fermiamo poiché π è una soluzione duale ottimale per il problema originale e, insieme alla soluzione primale ottimale del RMP, abbiamo una coppia primale/duale ottimale. In caso contrario, aggiungiamo le colonne in S al RMP e iteriamo (Klabjan, 2005). Questo processo è rappresentato dalla figura sottostante.

Schema di generazione di colonne. (Immagine dell'autore)

Si noti che il sottoproblema è specifico del problema e, in alcune situazioni, può essere piuttosto costoso computazionalmente per essere formulato come un problema di programmazione lineare mista intera. Potrebbe quindi essere utile considerare approcci di euristica e/o di programmazione dinamica che potrebbero restituire, in ogni iterazione, più di una colonna con costi ridotti negativi. Nel caso dei problemi di routing dei veicoli, spesso il sottoproblema è un problema di cammino più breve vincolato. Coloro che sono interessati a una disamina più approfondita possono fare riferimento a Irnich & Desaulniers (2005) per acquisire maggiore conoscenza sulle tecniche di soluzione.

Ricordiamo ora che l’approccio di ritardo nell’implementazione delle colonne presentato risolve un problema di Programmazione Lineare con variabili decisionali a valori reali. Con lo scopo di risolvere grandi programmi interi o misti interi, si potrebbe ricorrere a euristici dopo aver risolto il rilassamento o al Branch & Price per imporre i vincoli di integralità. In quest’ultimo approccio, si dovrebbero considerare non solo le colonne che sono state generate nella soluzione dell’LP iniziale, ma anche generare nuove colonne durante la soluzione degli LP lungo l’albero. Una discussione più approfondita sul Branch & Price è presentata da Barnhart et al. (1998). Gli autori esaminano questioni comuni, casi studio e interessanti intuizioni sulle regole di branch and bound.

Il Problema del Taglio di Stoffa

Consideriamo di avere un insieme di richieste I , ognuna per una quantità d di pezzi di larghezza w . Inoltre, consideriamo di avere una bobina di larghezza W da cui verranno prodotti i tagli. L’insieme di schemi di taglio noti sarà indicato con P . Ogni pezzo di un modello di taglio p consuma una unità della bobina ( c = 1) e produce aᵢₚ unità di larghezza wᵢ . Il nostro obiettivo è determinare la quantità di tagli x di ogni schema p che dovrebbe essere utilizzato per soddisfare le richieste minimizzando il numero di unità consumate. Possiamo formulare questo problema come segue.

Il problema del taglio di stoffa come un problema di copertura di insiemi. (Immagine dell'autore).

Le variabili decisionali duali associate ai vincoli di domanda π vengono quindi utilizzate nel problema di prezzo (sottoproblema) per trovare nuovi schemi con costi ridotti negativi. Nel caso del problema del taglio di stoffa, dobbiamo trovare un nuovo schema che combina pezzi di diverse larghezze che si adattano alla larghezza totale W e, aiutando a soddisfare le richieste di materiale, porterebbe a maggiori risparmi rispetto ai nuovi costi. Questo è un problema dello zaino, che può essere formulato come segue.

Problema di prezzo del taglio di stoffa. (Immagine dell'autore).

In cui yᵢ corrisponde al numero di pezzi di larghezza wᵢ prodotti nel nuovo schema di taglio.

Poiché sappiamo che ogni nuovo schema avrebbe un costo unitario c di 1, possiamo calcolare il costo ridotto del nuovo schema come:

Costo ridotto del nuovo schema di taglio. (Immagine dell'autore).

Il che, nel caso di valori non negativi, dovrebbe fermare l’algoritmo di generazione di colonne.

Per ottenere soluzioni intere per il problema del taglio di stoffa, un semplice metodo euristico consiste nel semplicemente arrotondare i valori frazionari ottenuti nella rilassamento lineare. In alternativa, si potrebbe anche risolvere il problema lineare con l’insieme di schemi prodotti nella rilassamento lineare imponendo vincoli di integralità. Utilizzeremo entrambe le strategie in questo articolo. Per istanze in cui il rilassamento lineare è vicino al modello intero completo, queste strategie possono essere molto efficaci. Alcune differenze potrebbero sorgere in altre istanze in cui il numero di richieste per ogni schema è relativamente piccolo.

Se si mira ad ottenere soluzioni intere esatte, Branch & Price può essere una buona alternativa. In questo approccio, dopo aver effettuato il branching su alcune delle variabili iniziali, potrebbero essere inclusi nuovi colonne con costi ridotti nel nodo corrente. Chi è interessato a maggiori dettagli può fare riferimento a Carvalho (1998) e a Vance (1998).

Ora mettiamoci all’opera!

Soluzione

Iniziamo l’implementazione Python del problema del taglio di stoffa, in cui la rilassamento lineare viene risolta con l’ottimalità, e un modello intero con gli schemi prodotti finora viene risolto. Utilizzeremo numpy per operazioni di algebra lineare, pandas per lavorare con i dataframes, scipy per gli algoritmi di ottimizzazione e matplotlib per visualizzare gli schemi di taglio in un grafico.

import numpy as npimport pandas as pdfrom scipy.optimize import linprogimport matplotlib.pyplot as plt

Importiamo un dataset che è una versione modificata del problema proposto nella documentazione di JuMP.

dataset = pd.read_csv("data.txt", sep=" ")

E istanziamo i parametri del problema

# Larghezza totaleW = 100.0# Larghezza e quantità associate ad ogni richiestaw = dataset.w.valuesd = dataset.d.values# Parametri LPA = np.eye(dataset.shape[0]) * (W // w)c = np.ones_like(w)

Si noti che per inizializzare la matrice A, ho introdotto semplici schemi di taglio che producono il massimo numero di rotoli fattibili per ogni larghezza dalle richieste. Supponiamo che ci sia una richiesta di rotoli di larghezza 24. Ciò porterebbe ad uno schema di taglio iniziale con un coefficiente di 4 dato la larghezza totale W di 100.

Ora definiamo una funzione per risolvere il sottoproblema dato il valore della larghezza totale W, un vettore di larghezze associate a ogni richiesta w e il vettore corrente di variabili duali duals.

def solve_knapsack(W, w, duals):    return linprog(        -duals, A_ub=np.atleast_2d(w), b_ub=np.atleast_1d(W),        bounds=(0, np.inf), integrality=1,    )

Nel ciclo principale, per ogni soluzione del problema principale ristretto, utilizzeremo la funzione linprog di scipy. La matrice A e il vettore di richieste sono passati come negativi poiché per convenzione scipy considera solo le disuguaglianze “minore o uguale a”.

linprog(c, A_ub=-A, b_ub=-d, bounds=(0, None))

La soluzione dovrebbe avere il negativo delle variabili duali associate alle richieste memorizzate nell’attributo ineqlin.marginals.

Esplorando i concetti di dualità, si potrebbero ottenere le variabili duali risolvendo il seguente LP.

linprog(-d, A_ub=A.T, b_ub=c, bounds=(0, None))

E mettiamo tutto insieme nel ciclo principale.

# Soluzioni inizialiol = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, None))sol_dual = linprog(-d, A_ub=A.T, b_ub=c, bounds=(0, None))diff = np.abs(sol_dual.x + sol.ineqlin.marginals).sum()print(f"Confronta la differenza di dualità: {diff}")# Iteriamofor _ in range(1000):    duals = -sol.ineqlin.marginals    price_sol = solve_knapsack(W, w, duals)    y = price_sol.x    if 1 + price_sol.fun < -1e-4:        print(f"Iterazione: {_}; Costo ridotto: {(1 + price_sol.fun):.3f}")        A = np.hstack((A, y.reshape((-1, 1))))        c = np.append(c, 1)        sol = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, None))    else:        break

Alla fine, proviamo a arrotondare la soluzione del rilassamento lineare e a ottenere la soluzione intera considerando solo le colonne prodotte nell’LP.

sol_round = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, np.inf), integrality=0)print(f"Soluzione arrotondata {np.ceil(sol_round.x).sum()}")sol = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, np.inf), integrality=1)print(f"Soluzione intera: {sol.x.sum()}")

Ciò dovrebbe restituire:

  • Soluzione arrotondata 339.0
  • Soluzione intera: 334.0

In questo caso, potremmo migliorare il risultato di quasi il 2% semplicemente imponendo vincoli di interezza all’LP anziché arrotondare il rilassamento. Solo uno spoiler per coloro che vogliono provare Branch & Price: 334 è la soluzione esatta per questa istanza.

Infine, proviamo a visualizzare i nuovi schemi di taglio:

fig, ax = plt.subplots(figsize=[7, 3], dpi=100)hmap = ax.imshow(A > 1e-6, cmap="Blues")plt.axis('off')fig.tight_layout()plt.show()
Schemi di taglio prodotti nel problema di taglio di stock. (Immagine dell'autore).

E abbiamo risolto il problema di taglio di stock utilizzando la generazione di colonne.

Per approfondire

Il problema del routing del veicolo capacitato (CVRP) è stato proposto per la prima volta da Dantzig & Ramser (1959) ed è particolarmente impegnativo a causa della sua natura combinatoria. Gli autori mostrano nel loro articolo originale che anche per problemi di piccole dimensioni il numero di possibili percorsi è incredibilmente grande. Ad esempio, un problema simmetrico con 15 punti di domanda ha più di 6 × 10⁹ possibili percorsi. Trovo particolarmente interessante vedere come la generazione di colonne sia stata esplorata nel tempo in questo e in problemi correlati.

Anche se per il problema del routing dei veicoli con finestre temporali strettamente vincolate, la generazione di colonne era già stata ben stabilizzata dal lavoro di Desrochers et al. (1992), Branch & Price spesso falliva su istanze meno vincolate. Pertanto, la generazione di colonne pura non è stata considerata un approccio promettente per il CVRP. Tuttavia, Fukasawa et al. (2006) hanno combinato la generazione di colonne in un algoritmo Branch & Cut, dimostrando l’ottimalità di diverse istanze della letteratura. Branch-cut-and-Price per il CVRP è stato ulteriormente migliorato da altri autori e ritengo che il lavoro di Pecin et al. (2017) possa essere particolarmente affascinante per il lettore interessato.

Conclusioni

In questo articolo, la generazione di colonne ritardata è stata introdotta come strategia per risolvere i programmi lineari con un grande numero di variabili di decisione senza considerare tutte le variabili in modo esplicito. Il classico problema di taglio monodimensionale è stato presentato per illustrare il metodo e una soluzione alternativa è stata implementata in Python. Il codice completo è disponibile in questo repository git.

Riferimenti

Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W., & Vance, P. H., 1998. Branch-and-price: Column generation for solving huge integer programs. Operations research , 46 (3), 316–329.

de Carvalho, J. V., 1998. Exact solution of cutting stock problems using column generation and branch-and-bound. International Transactions in Operational Research , 5 (1), 35–44.

Dantzig, G. B., & Ramser, J. H., 1959. The truck dispatching problem. Management science , 6 (1), 80–91.

Desrochers, M., Desrosiers, J., & Solomon, M., 1992. A new optimization algorithm for the vehicle routing problem with time windows. Operations research , 40 (2), 342–354.

Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P. D., Reis, M., Uchoa, E., & Werneck, R. F., 2006. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical programming , 106 , 491–511.

Gilmore, P. C., & Gomory, R. E., 1961. A linear programming approach to the cutting-stock problem. Operations research , 9 (6), 849–859.

Irnich, S., & Desaulniers, G., 2005. Shortest path problems with resource constraints (pp. 33–65). Springer US.

Klabjan, D., 2005. Large-scale models in the airline industry. Column generation , 163–195.

Pecin, D., Pessoa, A., Poggi, M., & Uchoa, E., 2017. Improved branch-cut-and-price for capacitated vehicle routing. Mathematical Programming Computation , 9 , 61–100.

Vance, P. H., 1998. Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational optimization and applications , 9 , 211–228.

Winston, W. L. & Goldberg, J. B., 2004. Operations research: applications and algorithms. 4th ed. Belmont, CA: Thomson Brooks/Cole Belmont.