Logica e Programmazione Lineare

Vincoli Logici

• Il rilassamento lineare del nodo produce una soluzione a variabili intere (ottimalità).
• Il rilassamento lineare del nodo è privo di soluzioni ammissibili (inammissibilità).
• Il rilassamento lineare del nodo produce una soluzione a variabili continue che è peggiore della miglior soluzione intera finora trovata (bound).

Criteri di Chiusura dei Nodi (B&B)

• Condizione: x1 ∨ x2 → x1 + x2 ≥ 1
• Condizione: x =⇒ y → x ≤ y
• Condizione: x1 ∧ x2 =⇒ y → x1 + x2 − 1 ≤ y
• Condizione: x1 ∧ x2 ∧ ... ∧ xk =⇒ y → ∑i=1k xi − (k − 1) ≤ y
• Condizione: x1 ∨ x2 ∨ ... ∨ xk =⇒ y → ∑i=1k xi ≤ ky
• Condizione: x1 ∨ x2 =⇒ y → x1 + x2 ≤ 2y

Regole di Pivoting (Cambio di Base)

• Si consideri un programma lineare in forma standard riformulato rispetto a una base B ⊆ {x1, x2, ..., xn}
• N = {xi : xi ∉ B} è l'insieme di variabili fuori base
• max z = z(B) + ∑j∈N rj xj
• xi = βi + ∑j∈N αij xj ∀xi ∈ B

Dualità

• Il duale di un programma lineare è min{w = u b : u A ≥ c}
• Condizioni di complementarietà primale-duale: x∗ e u∗ sono soluzioni ottime, v∗ T x∗ = 0

Simplesso

• Si sceglie la variabile entrante xq ∈ N tale che rq = max{rk : xk ∈ N } > 0
• Si sceglie la variabile uscente xp ∈ B tale che βp = min{βi : xi ∈ B} < 0

Condizioni di Bellman (SPT)

• La soluzione ammissibile per il problema SPT su un grafo orientato e pesato G = (N, A) individuata dal generico albero di copertura T è ottima se e solo se:
  • du + cuv = dv ∀(u, v) ∈ T
  • du + cuv ≥ dv ∀(u, v) ∉ T