Selezionare un sottoinsieme di N elementi candidati, ognuno con un valore e un peso, in modo che il peso totale non superi una capacità (budget, ore-uomo, ore-macchina) e il valore totale sia massimo. In letteratura è il Knapsack Problem — l'antenato dei problemi di selezione discreta.
In breve
Ti suona familiare?
- Comitato di investimento annuale con 50-200 progetti candidati e un budget totale fisso di 50-500M TRY — l'ordine è intuitivo e politico; esiste una tabella 'NPV/investimento' ma l'ottimalità matematica non è garantita.
- Per ogni candidato sono disponibili stima NPV, investimento richiesto, ore-uomo richieste e ore-macchina richieste (tre dimensioni di vincolo) — ma non abbiamo mai costruito un modello di selezione che le rispetti tutte simultaneamente.
- La pianificazione di budget usa 'ordinare e scegliere dall'alto' — ma piccoli progetti ad alto rapporto NPV/unità che entrerebbero nell'ultimo 5-10% del budget tipicamente non passano.
- Selezione delle campagne di marketing digitale: 30-80 proposte, budget mensile o trimestrale fisso; quale sottoinsieme massimizza reach/conversion?
- Esistono dipendenze tra candidati (progetto A riduce il costo di B se scelto; progetti C e D sono mutualmente esclusivi) — lo knapsack classico non le cattura e servono vincoli aggiuntivi.
- Lato logistica: aereo cargo o container a capacità limitata — ogni collo ha valore e peso; massimizzare il valore totale senza superare la capacità.
- Gestore di fondo small-cap: universo di 200-500 azioni, dimensione del fondo fissa, ogni azione con rendimento atteso e lotto minimo; quale sottoinsieme scegliere?
- Contratto con i fornitori: 100+ candidati, budget annuale di acquisto fisso; ogni fornitore con minimo e massimo ordine; quale sottoinsieme massimizza il valore totale?
Perché è importante
Come si risolve
Profondità tecnica
Come si risolve
Profondità tecnicaIn una frase: Ordina i candidati per valore per unità di peso come inizio greedy; per la risposta esatta esegui programmazione dinamica (capacità sotto 10K) o MIP (soprattutto con vincoli multidimensionali o dipendenze) — il miglior sottoinsieme esce in minuti.
Nella letteratura di Ricerca Operativa (disciplina che usa matematica e informatica per risolvere decisioni di business) e informatica il problema è studiato come Knapsack Problem (problema dello zaino) — N elementi candidati con valore (vᵢ) e peso (wᵢ); capacità W; quale sottoinsieme massimizza Σvᵢ soggetto a Σwᵢ ≤ W? Problema classico studiato dagli anni 1950, con soluzioni industry-standard tramite programmazione dinamica, branch-and-bound e solver MIP moderni. Soluzione in tre fasi:
1. Modellazione — scelta della variante e input. La famiglia di problemi è ampia; l’applicazione determina la variante:
- 0/1 Knapsack (binario): ogni elemento è scelto o no, senza duplicati. Selezione classica di progetti d’investimento. xᵢ ∈ {0, 1}.
- Bounded Knapsack: numero limitato di copie per elemento (xᵢ ∈ {0, 1, …, cᵢ}). Contratti con lotti per fornitore.
- Unbounded Knapsack: copie illimitate (xᵢ ≥ 0 intero). Produzione con capacità, lotti di azioni interi.
- Multi-Dimensional Knapsack (MKP): m vincoli; ogni elemento con pesi in m dimensioni (budget + ore-uomo + ore-macchina + …). Σⱼwᵢⱼxᵢ ≤ Wⱼ per ogni j. Molto più difficile.
- Quadratic Knapsack (QKP): obiettivo quadratico con sinergie tra elementi.
- Multiple-Choice Multi-Dimensional Knapsack: elementi raggruppati; esattamente uno per gruppo.
- Subset-Sum: valore obiettivo uguale al peso; totale il più vicino possibile alla capacità.
- Knapsack con Set-Up: scegliere un elemento comporta un costo fisso di set-up (gruppo).
Input: lista candidati N, stime di valore e peso (NPV e investimento; nel marketing valore stimato di conversione e costo della campagna), capacità W (budget annuale, mensile, carico aereo), vincoli multidimensionali (ore-uomo, ore-macchina, sub-budget per categoria), struttura delle dipendenze.
2. Soluzione — strumenti algoritmici.
- Greedy + rilassazione LP: approccio più semplice — ordinare per rapporto valore/peso e scegliere dall’alto fino a riempire la capacità. Non garantisce ottimalità (controesempio classico: capacità 10, tre elementi (v,w) = (6,5), (5,4), (4,3) — greedy 6+5=11, ottimo 5+4+3=12); la rilassazione LP fornisce il limite superiore per branch-and-bound. Utile come quick check one-shot.
- Programmazione Dinamica (DP): algoritmo pseudo-polinomiale classico (il tempo dipende dal valore numerico della capacità W). Stato dp[i][w] = valore massimo con i primi i elementi senza superare il peso w. Transizione dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ). Complessità O(N×W). N = 1000, W = 100.000 TRY-unità = 10⁸ operazioni, secondi su hardware moderno. Realtà pratica: istanze moderate (N ≤ 1000, W ≤ 10⁶) si risolvono all’ottimo in minuti; l’intuizione ‘NP-hard, irrisolvibile’ è sbagliata.
- Branch-and-bound (ricerca ad albero con potatura dei rami non promettenti): con potatura tramite limite LP. Una tecnica di nucleo di variabili è lo stato dell’arte pratico per 0/1 knapsack da milioni di elementi.
- MIP (Mixed-Integer Linear Programming — ottimizzazione con alcune variabili 0/1 e altre continue): strumento naturale per MKP e istanze ricche di dipendenze. Solver MIP open-source o commerciali risolvono MKP da 100-1000 elementi all’ottimo (o con piccolo gap) in minuti-ore.
- FPTAS (Fully Polynomial-Time Approximation Scheme — per ogni ε > 0, una (1-ε)-approssimazione in tempo polinomiale): con ε = 0.01 garantisce il 99% dell’ottimo.
- Metaeuristiche (genetico, tabù, simulated annealing): per MKP molto grandi o ricchi di dipendenze; nessuna garanzia di ottimalità, qualità pratica.
Selezione di progetti di investimento (50-200 elementi, un budget o 2-4 vincoli): MIP o DP 0/1 restituisce l’ottimo in secondi. MKP molto grande (500+ elementi, 5+ vincoli): MIP vicino all’ottimo o FPTAS. In pratica MIP basta nella maggior parte degli scenari aziendali; un algoritmo knapsack specializzato è raramente necessario.
3. Integrazione sul campo e analisi di sensibilità. Output: sottoinsieme scelto, valore totale, utilizzo per vincolo, sensibilità basata su rilassazione LP (quale progetto è entrato per un soffio, quale è rimasto fuori per un soffio). Report al comitato di investimento: proposta di selezione, scenari alternativi (quale progetto cambia se budget ±10%, quale entra se il vincolo ore-uomo si allenta), reporting esplicito di dipendenze e vincoli politico-strategici. Ripianificazione trimestrale: nuove proposte aggiunte, NPV reale vs previsto confrontato, modello risolto di nuovo.
Alternative
Manuale + foglio elettronico
GratuitoNessuna licenza
Per chi: Piccola scala, 10-30 candidati, un budget, dipendenze semplici
- + Nessun setup
- + Facile per interventi politico-strategici del comitato
- + Sufficiente per una rapida discussione top-N
- − Ordinare-e-scegliere non garantisce il miglior sottoinsieme — 5-15% di perdita di valore tipica
- − Vincoli multidimensionali non rispettabili a mano
- − Struttura delle dipendenze grossolana (progetti prioritari, coppie mutualmente escludenti)
- − Nessuna analisi di sensibilità (budget ±10%)
Solver MIP open-source + modello interno
Open SourceLicenza gratuita; sviluppo interno 4-12 settimane o 200K-600K TRY di consulenza
Per chi: Organizzazione con team OR/analytics, budget annuale 50M+ TRY
- + Nessun costo di licenza
- + I modelli di selezione progetti si mappano bene su solver open-source
- + Analisi rapida di scenari (budget, ore-uomo, capacità)
- + Proprietà interna — modello trasparente, ipotesi verificabili
- − Richiede specialista in ottimizzazione e ingegnere dei dati
- − Manutenzione del modello in casa
- − Il rumore nella stima del rendimento persiste — la qualità dell'input è decisiva
Solver MIP commerciale + modello interno
AziendaleLicenza annuale 200K-1.5M TRY (osservazione mercato TR); grande impresa 2-5M TRY
Per chi: Grande holding, budget annuale 500M+ TRY, vincoli multidimensionali
- + Motore di risoluzione ottima di livello industriale
- + Risoluzione parallela ad alte prestazioni
- + Interfaccia di modellazione matura (scripting più supporto a linguaggi di modellazione)
- + Supporto industriale
- − Licenza elevata
- − Sviluppo e manutenzione interni richiedono comunque uno specialista in ottimizzazione
- − Rischio di dipendenza dal fornitore — migrazione ad altro solver 4-12 settimane
Software enterprise di project portfolio management
AziendaleLicenza annuale 500K-3M TRY (osservazione mercato TR), per scala
Per chi: Multi-portafoglio, multi-categoria, multi-geografia
- + Flusso integrato da proposta a selezione
- + Dipendenze (progetti prioritari, coppie escludenti, sconto da sinergia) modellabili nella UI
- + Ripianificazione trimestrale e confronto con rendimento reale integrati
- + Report di comitato pronti
- − Licenza elevata più 6-12 mesi di implementazione
- − Modulo di risoluzione integrato spesso limitato — insufficiente per portafogli grandi
- − Dipendenza dal fornitore
- − La personalizzazione settoriale allunga il progetto
Raccomandazione
Chiedi nell'incontro
- Quali varianti supporta il modulo di selezione progetti — 0/1, numero limitato di lotti, budget unico, vincoli multidimensionali, selezione a gruppi, costo di set-up?
- Quale metodo guida il solver — solver con garanzia di ottimo, programma dinamico, approssimazione, ricerca avanzata? Tempo tipico di risoluzione per un portafoglio multi-vincolo da 200-1.000 progetti?
- La struttura delle dipendenze (progetti prioritari, coppie escludenti, sconto da sinergia, costi di set-up) è modellabile nella UI o le regole vanno scritte a mano?
- Analisi di sensibilità — negli scenari budget ±10% o ore-uomo ±20%, quali progetti cambiano e il reporting è automatizzato?
- L'incertezza negli input di rendimento è modellabile (selezione sotto incertezza) o solo stima puntuale?
- Per soluzioni multi-vincolo, è riportata la percentuale di scostamento tra valore ottenuto e limite teorico superiore così che l'utente sappia se il risultato è ottimo o vicino all'ottimo?
- L'output produce direttamente un report per il comitato di investimento — sottoinsieme scelto, percentuale di budget usato, decisioni 'al pelo'?
- A fine contratto, in quale formato standard si possono esportare dati dei progetti candidati, input del modello, storico delle soluzioni e analisi di sensibilità?
Dettagli tecnici
Nota della redazione
In linguaggio comune il problema si chiama “selezione di progetti”, “allocazione di budget” o “prioritizzazione di investimenti”. In letteratura il nome è Knapsack Problem (problema dello zaino) — dalla metafora di riempire uno zaino di capacità limitata con il carico più prezioso (Dantzig 1957). È l’antenato dei problemi di selezione discreta. Non va confuso con il problema di ottimizzazione di portafoglio (#018 Markowitz media-varianza): Markowitz dà pesi continui (a ciascun asset una frazione reale tra 0% e 100% del portafoglio) e modella il rischio tramite varianza e correlazione; lo knapsack è una decisione discreta scegli-o-no (xᵢ ∈ {0, 1}) e massimizza il valore soggetto a budget e NPV. Dietro la maggior parte dei problemi decisionali classici c’è uno knapsack — selezione di progetti d’investimento, selezione di campagne, carico aereo, selezione di sottoinsiemi di fornitori. Cutting stock (#005, taglio geometrico multidimensionale) e 3D bin packing (#015, packing volumetrico) sono parenti stretti ma problemi diversi: lo knapsack massimizza il valore, il cutting stock minimizza il numero di rotoli, il 3D bin packing sistema i colli nei contenitori. L’assortment planning (#017, selezione di scaffale al dettaglio) è una variante specializzata dello knapsack — accoppiata a un modello di domanda per prodotto.
Punto più trascurato nel settore: la differenza tra DP pseudo-polinomiale e l’etichetta di classe di complessità. Lo knapsack è NP-hard — non si conosce un algoritmo polinomiale nella lunghezza in bit dell’input. Il professionista lo legge come ‘irrisolvibile’ — sbagliato. La DP di Bellman gira in O(N×W) — W è la capacità. In un budget di capitale W = 50M TRY, ma si modella in migliaia di TRY (W = 50.000); con N = 200 progetti sono 10⁷ operazioni, secondi su hardware moderno. Pseudo-polinomiale: il tempo è polinomiale nel valore di W (ed esponenziale nella sua lunghezza in bit). Conseguenza: quando W è moderato (migliaia, decine di migliaia), la DP risolve istanze di milioni di elementi all’ottimo in minuti. Nel comitato non bisogna saltare a ’l’ottimo matematico è irraggiungibile, decidiamo a intuito’ — gli strumenti pratici (MIP, DP) sono alla portata di tutti.
Secondo punto trascurato: l’incertezza negli input NPV/valore. La matematica dello knapsack assume input deterministici. In realtà le stime NPV poggiano su proiezioni a 5 anni con ±20-40% di scostamento; nei progetti di nuova tecnologia e trasformazione digitale l’incertezza è ancora maggiore. Un solver classico di knapsack assorbe quell’incertezza e restituisce un singolo sottoinsieme ‘ottimo’; con NPV ±20% il sottoinsieme può cambiare completamente. Rimedi: knapsack stocastico (Bertsimas e Sim 2003 ottimizzazione robusta, ottimo worst-case su un insieme di incertezza dell’NPV), chance-constrained knapsack (probabilità di sforare il budget al più 5%) o una semplice analisi di sensibilità (progetti stabili attraverso scenari NPV ±20%). Terzo punto trascurato: struttura delle dipendenze. Lo knapsack classico assume indipendenza degli elementi — i valori si sommano. In pratica ci sono sinergie (A + B insieme valgono di più), esclusione mutua (A xor B), precedenza (A → B), sconto di capacità (A rende B più economico). Si modellano come vincoli MIP; bisogna uscire dall’interfaccia standard dello knapsack e passare a un MIP più ricco.
Passo per passo — per la PMI
Fase 1 — Misurare prima, pianificare poi. Gli ultimi 3-5 anni di progetti candidati (accettati e respinti): stima NPV proposta, NPV realizzato (per gli accettati), importo di investimento, ore-uomo, ore-macchina. Statistica di scostamento NPV per categoria (ampliamento, modernizzazione, digitale, IT) e per dimensione, rapporto previsto/realizzato, banda ±%. Documentare in quale punto della pianificazione annuale budget e altri vincoli (ore-uomo, ore-macchina, sub-budget per categoria) vengono fissati.
Fase 2 — Emergere il capitale di conoscenza. Struttura tipica delle dipendenze tra candidati (catene di precedenza, coppie mutualmente esclusive, sinergie di sconto). Bande di affidabilità dell’NPV: piccolo progetto standard ±10%, trasformazione digitale ±30-40%, R&S ±50%. Requisiti politici di sub-budget per categoria (bilanciamento regionale, diversificazione settoriale).
Fase 3 — Pilota. 6-10 settimane. In un ciclo annuale del comitato, eseguire in parallelo alla selezione intuitiva esistente un MIP open-source. Riportare entrambi gli output uno accanto all’altro per lo stesso set di candidati; spiegare le differenze (quale progetto ha scelto il greedy, quale il MIP, perché). La decisione resta al comitato; il MIP è una raccomandazione. Criterio di successo stabilito in anticipo: portafoglio raccomandato dal MIP almeno il 5% sopra l’NPV greedy.
Fase 4 — Roll-out. 6-12 mesi fino al processo completo del comitato con MIP. Ripianificazione trimestrale (nuove proposte aggiunte, progetti cancellati rimossi). Analisi annuale di sensibilità (scenari budget ±10%). Knapsack stocastico o robusto solo dopo aver consolidato la base di incertezza NPV. Comitato trimestrale di investimento: raccomandazione MIP vs portafoglio approvato, decisioni ‘al pelo’, calibrazione previsto/realizzato dell’NPV.
Rischi — cosa può andare storto
- Errore di stima NPV/rendimento. La soluzione è matematicamente ottima sugli NPV dati; se NPV ±20-40%, il sottoinsieme ottimo può cambiare. Estensione robusta o stocastica o almeno analisi di sensibilità (progetti stabili a NPV ±20%) sono obbligatorie. Per calibrare le previsioni, tracciare nel tempo NPV realizzato / NPV previsto per categoria.
- Assunzione di indipendenza dei progetti. Lo knapsack classico somma i valori degli elementi; in pratica ci sono sinergie (A + B insieme valgono di più), esclusione mutua (A xor B), precedenza (A → B), sconto di capacità (A rende B più economico). Servono vincoli MIP; bisogna abbandonare l’interfaccia standard dello knapsack.
- Distribuzione del rischio ignorata. Lo knapsack puro massimizza il valore totale; non modella il rischio di portafoglio (varianza, covarianza, rischio di coda). Scegliere cinque progetti nello stesso settore può dare alto NPV ma rendere il portafoglio fragile a uno shock settoriale. Aggiungere vincoli di sub-budget per settore / geografia / categoria o accoppiare la selezione con una misura di rischio tipo CVaR (#063).
- Lock-in su un singolo fornitore di software di pianificazione degli investimenti. Senza una clausola contrattuale di esportazione annuale di dati dei candidati, input del modello, storico delle soluzioni e analisi di sensibilità in formato standard, cambiare fornitore significa azzerare la memoria istituzionale di pianificazione. MIP open-source + modello interno dà indipendenza dal fornitore a scala media.
Uno sguardo tecnico alla soluzione
| Approccio | Scala tipica | Tempo di risoluzione | Garanzia di ottimalità? |
|---|---|---|---|
| Greedy (ordinare per NPV/investimento) | Qualsiasi | istantaneo | No (85-95% dell’ottimo tipico) |
| Limite superiore LP | Qualsiasi | istantaneo | No (limite superiore) |
| Programmazione Dinamica (Bellman 1957) | Moderata (N≤1000, W≤10⁶) | secondi-minuti | Sì |
| Branch-and-Bound (Martello-Toth 1990) | Media-grande 0/1 KP | minuti-ore | Sì |
| Expanding Core di Pisinger (1997) | Molto grande 0/1 KP | minuti | Sì |
| MIP (solver generico) | Generale (MKP, QKP, set-up) | secondi-ore | Sì (entro gap) |
| FPTAS (Ibarra-Kim 1975) | Molto grande, ε-approx ammessa | minuti | (1-ε) dell’ottimo |
| Metaeuristica (genetico, tabù, SA) | MKP molto grande, denso di dipendenze | minuti-ore | No, buona qualità pratica |
Confronto varianti dello knapsack:
- 0/1 Knapsack: ogni elemento scelto o no. Capital budgeting classico.
- Bounded Knapsack: copie limitate. Lotti con fornitori.
- Unbounded Knapsack: copie illimitate. Produzione con capacità, lotti interi di azioni.
- Multi-Dimensional Knapsack (MKP): m vincoli — budget + lavoro + macchina + categoria.
- Quadratic Knapsack (QKP): sinergia o interazione a coppie.
- Multiple-Choice MKP: elementi raggruppati, esattamente uno per gruppo.
- Subset-Sum: obiettivo = peso; totale il più vicino possibile alla capacità.
- Knapsack con Set-Up: costo fisso di set-up per gruppo.
Scelta della funzione obiettivo:
- Obiettivo 1 — Valore totale massimo (NPV, valore di conversione): classico.
- Obiettivo 2 — Massimo utilizzo del budget (vicino al subset-sum): disciplina del consumo totale.
- Obiettivo 3 — Valore worst-case massimo (su insieme di incertezza NPV): ottimizzazione robusta Bertsimas-Sim.
- Obiettivo 4 — Valore atteso meno penalità di varianza (stocastico): knapsack media-varianza.
Modellazione delle dipendenze (in MIP):
- Precedenza (A → B): xB ≤ xA.
- Esclusione mutua (A xor B): xA + xB ≤ 1.
- Sconto di sinergia: decisione aggiuntiva yA·B.
- Costo di set-up: decisione aggiuntiva yk per gruppo.
- Sub-budget per categoria: Σᵢ∈Cwᵢxᵢ ≤ Wc per categoria C.
Fonti accademiche
Elencate nel frontmatter sotto sources.
Fonti
- Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2), 266-288. Fonte fondativa della formulazione LP/IP dello knapsack.
- Bellman, R. (1957). Dynamic Programming. Princeton University Press. Libro fondativo della programmazione dinamica; lo knapsack è l’esempio canonico.
- Martello, S. e Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley. Libro classico; algoritmi branch-and-bound, confronti sperimentali.
- Kellerer, H., Pferschy, U. e Pisinger, D. (2004). Knapsack Problems. Springer. Riferimento moderno completo; tutte le varianti, FPTAS, MKP, QKP.
- Pisinger, D. (1997). A minimal algorithm for the 0-1 knapsack problem. Operations Research, 45(5), 758-767. Algoritmo expanding-core, stato dell’arte pratico.
- Ibarra, O. H. e Kim, C. E. (1975). Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4), 463-468. Fonte fondativa dello FPTAS dello knapsack.
- Centro Tesi YÖK — parole chiave ‘sırt çantası’, ‘knapsack’ o ‘proje seçimi’ — 25+ tesi dall’accademia turca. tez.yok.gov.tr
Glossario
- Knapsack Problem
- Il problema fondativo di ottimizzazione discreta di selezionare un sottoinsieme di N elementi, ognuno con valore e peso, per massimizzare il valore totale sotto un vincolo di capacità sul peso totale.
- Dynamic Programming
- La tecnica di OR / informatica per risolvere problemi decisionali multistadio tramite decomposizione ricorsiva in sottoproblemi sovrapposti con risultati intermedi memorizzati; introdotta da Bellman (1957).
- MIP
- Modello di ottimizzazione in cui alcune variabili decisionali devono essere numeri interi (es. numero di camion, numero di turni).
Problemi correlati
Che percentuale del mio denaro va in quale investimento?
Una delle domande fondamentali per una PMI o un investitore privato: c'è del capitale e diverse opzioni di investimento (azioni, obbligazioni, valute, materie prime, depositi, immobili, reinvestimento nell'azienda), ognuna con rendimento atteso e rischio diversi, con correlazioni tra loro. Quale percentuale del capitale va dove? Il nome matematico è Portfolio Optimization Problem. Nel 1952 Harry Markowitz formalizzò il quadro mean-variance — fondazione, premio Nobel, della teoria moderna del portafoglio. Massimizzare il rendimento atteso minimizzando la varianza (rischio) è un problema di programmazione quadratica.
Più input + più output — come misuro l'efficienza relativa delle mie filiali o unità?
Questa pagina è per voi se gestite una banca con 100-500 filiali, una catena ospedaliera multi-sito con 200-1.500 letti, una direzione scolastica con centinaia di scuole o un ente pubblico che confronta provincia per provincia. La domanda di fondo: quale filiale/ospedale/scuola è efficiente e quale no — e per quelle che non lo sono, quale unità 'peer' devono prendere a riferimento e di quanto devono migliorare? Ogni unità consuma più input alla volta (personale, superficie, budget) e produce più output (ricavi, clienti/pazienti/studenti, qualità); un singolo rapporto come 'ricavi per dipendente' non rappresenta questa realtà e può etichettare come debole un'unità efficiente o viceversa. Applicato correttamente — poiché il peer benchmark fornisce un riferimento concreto di miglioramento — l'accettazione dei piani di miglioramento per le unità deboli cresce del 40-70%, pari grosso modo a 10-50 milioni TRY all'anno di margine operativo in una rete media di filiali.