Vai al contenuto

Indice completo

Modelli e bound

  1. La programmazione lineare intera
    • 1.1 Forma canonica di massimizzazione
    • 1.2 Esiti possibili
    • 1.3 Enumerazione completa
    • 1.4 Errori tipici
    • 1.5 In sintesi
  2. Bound primali e duali
    • 2.1 Bound primali e bound duali
    • 2.2 Bound primali: soluzioni euristiche
    • 2.3 Il rilassamento lineare
    • 2.4 Arrotondare la soluzione del rilassamento lineare
    • 2.5 Upper bound sulle variabili
    • 2.6 Bound duali
    • 2.7 Errori tipici
    • 2.8 In sintesi

Rafforzare la formulazione

  1. Formulazioni ideali
    • 3.1 L'inviluppo convesso
    • 3.2 Formulazioni e formulazioni ideali
    • 3.3 Confronto tra formulazioni
    • 3.4 Esistenza delle formulazioni ideali
    • 3.5 Errori tipici
    • 3.6 In sintesi
  2. Disuguaglianze valide
    • 4.1 Disuguaglianze valide
    • 4.2 Ricavare disuguaglianze valide per arrotondamento
    • 4.3 Migliorare una disuguaglianza valida
    • 4.4 Famiglie di disuguaglianze valide e tagli
    • 4.5 Errori tipici
    • 4.6 In sintesi
  3. Disuguaglianze di cover
    • 5.1 Un vincolo con coefficienti positivi e il suo rilassamento lineare
    • 5.2 Coperture e disuguaglianze di copertura
    • 5.3 Interpretazione geometrica
    • 5.4 Separazione delle disuguaglianze di copertura
    • 5.5 Dal CSP a un problema complementare
    • 5.6 Disuguaglianze di copertura estese
    • 5.7 Violazione e distanza da una disuguaglianza di copertura
    • 5.8 Errori tipici
    • 5.9 In sintesi

Metodi esatti

  1. L'algoritmo dei piani di taglio con i tagli frazionari di Gomory
    • 6.1 Tagli frazionari di Gomory
    • 6.2 Un algoritmo dei piani di taglio basato sui tagli frazionari di Gomory
    • 6.3 L'esempio dell'auto
    • 6.4 Errori tipici
    • 6.5 In sintesi
  2. Il branch-and-bound basato sulla programmazione lineare
    • 7.1 L'idea in parole e in una figura
    • 7.2 Definizioni e notazione
    • 7.3 L'algoritmo
    • 7.4 Breve riepilogo dell'algoritmo del simplesso duale
    • 7.5 Strategie di selezione della variabile di branching
    • 7.6 Strategie di selezione del nodo di branching
    • 7.7 Esempi svolti sull'esempio dell'auto
    • 7.8 Errori tipici
    • 7.9 Estensioni
    • 7.10 In sintesi
  3. Il branch-and-cut
    • 8.1 Algoritmi branch-and-cut
    • 8.2 Disuguaglianze valide globali e locali
    • 8.3 Cut-and-branch e branch-and-cut
    • 8.4 Esempio svolto: cut-and-branch con tagli di Gomory
    • 8.5 Tagli locali: un esempio
    • 8.6 Aspetti pratici
    • 8.7 Errori tipici
    • 8.8 In sintesi

I solver MIP

  1. I solver MIP: che cosa fanno
    • 9.1 Dall'algoritmo branch-and-cut a un solver MIP
    • 9.2 I componenti di un solver MIP
    • 9.3 Come si legge il log di Gurobi
    • 9.4 Errori tipici
    • 9.5 In sintesi

Euristiche MIP

  1. Euristiche MIP
    • 10.1 Euristiche basate sulla PLI
    • 10.2 Gli esempi del capitolo
    • 10.3 Arrotondamento
    • 10.4 Diving
    • 10.5 La feasibility pump
    • 10.6 Migliorare l'incumbent con un sotto-MIP
    • 10.7 Relax-and-fix e fix-and-optimize
    • 10.8 Le euristiche dentro il solver
    • 10.9 Che cosa danno le euristiche basate sulla PLI
    • 10.10 Implementazione in Python
    • 10.11 Errori tipici
    • 10.12 In sintesi