Problemi misti
Classe: BIP / MILP · Script: uno script e un notebook per problema
(python/fam10_1_premi.py … fam10_9_scaffali.py).
Le tre famiglie precedenti hanno una struttura riconoscibile: si assegna, si localizza, si pianifica. I nove problemi di questo capitolo non ce l'hanno, e non gliene va imposta una: ciascuno mette insieme pezzi diversi, e il lavoro di modellazione consiste proprio nel riconoscere quali.
- Selezione con modalità alternative (10.1 e 10.2): si sceglie un sottoinsieme, ma ogni oggetto ha più di un modo di essere scelto, e i modi si escludono a vicenda.
- Quantità con lotto minimo (10.3): accanto alle binarie ci sono quantità continue, e una quantità può stare a zero oppure fra una soglia e un tetto.
- Copertura con contenitori (10.4 e 10.5): un fabbisogno va coperto acquistando confezioni di composizione fissa, e la quantità in eccesso si paga o si spreca.
- Divisione e bilanciamento (10.6–10.9): un insieme va diviso fra più contenitori e la qualità si misura su quanto i contenitori si somigliano.
Quattro di questi problemi hanno in comune un tratto che nelle tre famiglie non si era presentato: il rilassamento LP è debole, e in due casi vale esattamente zero. La ragione è sempre la stessa: una soluzione frazionaria può spezzare a metà ogni oggetto e metterne una metà in ciascun contenitore, pareggiando tutto.
Dove cercare un bound combinatorio quando il rilassamento non basta
Parità: un conteggio che non può che essere pari. Numero di contenitori: quanti ne servono al minimo, letto dalle capacità. Dominanza di una classe: una classe di oggetti che da sola impone il valore. Sono argomenti combinatori: nascono dall'interezza, e il duale del rilassamento non può vederli.
I nove problemi
-
10.1 Premi acquistabili con due modalità
Set packing su quattro variabili invece di due: la quantità \(x_i + y_i\) è l'indicatore «premio \(i\) preso».
-
10.2 Asta combinatoria
Un set packing sulle offerte: due offerte che condividono un lotto non possono essere accettate entrambe.
-
10.3 Dieta con lotto minimo
Quantità continue con lotto minimo: un alimento si compra a zero oppure fra la sua soglia e il suo tetto.
-
10.4 Scatole di luci per gli alberi
Configurazioni di composizione fissa e un vincolo di varietà: quante scatole di ciascun tipo comprare.
-
10.5 Spedizioni in scatole
Copertura di una domanda con contenitori di taglia diversa, uno per tipo di prodotto.
-
10.6 Bambini fra campi estivi
Conteggi interi e vincoli di composizione. Il rilassamento LP non vede la parità: il bound utile è combinatorio.
-
10.7 Filiali fra due società
Min-max sullo squilibrio peggiore. Il rilassamento vale zero: si spezza ogni filiale a metà.
-
10.8 Brani fra CD
Valore assoluto e pareggio delle durate. Anche qui il rilassamento vale zero.
-
10.9 Libri fra scaffali
Variabile di massimo: l'altezza di uno scaffale è quella del libro più alto, imposta con \(y_s \ge h_b\, x_{bs}\).
Modelli numerici della famiglia
Quattro modelli brevi con dati espliciti: una selezione con implicazione, un lotto minimo, un packing e dei conteggi interi a lotti.
| Modello | Che cosa mette in gioco | \(z(\mathit{MILP})\) |
|---|---|---|
| EX 1 — Il furgone da otto posti | selezione con capacità e un'implicazione fra gruppi | 120 |
| EX 5 — Fondi acquistabili a lotti | conteggi interi a lotti, con un vincolo di proporzione | 16 |
| EX 6 — Veicoli con quantità minima | lotto minimo: una quantità minima se il tipo si produce | 25 250 |
| EX 9 — Le regine sulla scacchiera | packing su scacchiera: righe, colonne e diagonali | 4 |