Autore Topic: Rilassamenti (Esame 17/2/2010)  (Letto 417 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Mithrandir

  • Maestro Geek
  • *
  • *
  • *
  • Post: 1.157
  • Reputazione: 44
  • Sesso: Maschio
  • Battlemage
Rilassamenti (Esame 17/2/2010)
« il: 12 Febbraio 2011, 16:21:36 »
Partendo dal primo esercizio dell'esame del 17/2/2010 vorrei cercare di manifestare tutti i miei dubbi sui rilassamenti Lagrangiano e Surrogato.
La soluzione postata da Cosmos è molto di alto livello e non so se i miei passaggi intermedi sono corretti.

Problema iniziale
min \sum_{i\in I}c_ix_i

\sum_{i\in I}a_i^1x_i\ge b_1
\sum_{i\in I}a_i^2x_i = b_2
x_i\in \mathbb{Z}^{+}, \forall i \in I

Rilassamento Lagrangiano
Scelgo un sottoinsieme di vincoli "difficili" (in questo caso il testo diceva tutti). Associo ai vincoli di uguaglianza coefficienti moltiplicativi u_i \in \mathbb{R} e ai vincoli di disuguaglianza variabili \mu_i \ge 0. Porto poi i vincoli in funzione obiettivo:

L(\bar x,u,\mu) = \sum_{i\in I}c_ix_i - \mu\left\(\sum_{i\in I}a_i^1x_i - b_1\right\) - u\left\(\sum_{i\in I}a_i^2x_i - b_2\right\)
@Cosmos: Mi viene diversa dalla tua soluzione, come faccio a far sparire b1 e b2?

Lagrangiano primale
\min L(\bar x,u,\mu)

x_i \in \mathbb{Z}^{+}, \forall i \in I \quad u \in \mathbb{R} \quad \mu \ge 0

Lagrangiano duale Molti dubbi...
\max L(u,\mu) e la x dove finisce? Viene fissata?

u \in \mathbb{R} \quad \mu \ge 0

Rilassamento surrogato
Teoricamente occorrerebbe fare una combinazione lineare dei vincoli. Come si fa visto che uno è di uguaglianza e l'altro di disuguaglianza?
Spoiler (click to show/hide)
Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now - at the turn of the tide.


Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Rilassamenti (Esame 17/2/2010)
« Risposta #1 il: 12 Febbraio 2011, 17:53:46 »
I coefficienti b non li fai sparire. Molto semplicemente non fai come il sottoscritto che si è dimenticato di riportarli!

Nel duale la x diventa un parametro implicito, poiché le vere variabili del problema sono i moltiplicatori di Lagrange.
Nella pratica si risolve questo dettaglio fissando effettivamente il valore di x, determinato da una prima risoluzione del primale (con variabili duali scelte a piacere).

Per quanto riguarda il surrogato, effettivamente non ho trovato dettagli circa il caso con vincoli di uguaglianza e disuguaglianza, ma se dal S si può passare al L, e noi abbiamo sappiamo che forma ha tale L perché l'abbiamo individuato all'inizio dell'esercizio, secondo me potremmo ricondurre i due vincoli ad un solo vincolo di disuguaglianza coincidente con gli ultimi due addendi della f.o. del L stesso.
Io sceglierei la disuguaglianza poiché in teoria è la versione 'meno stringente'. Se portassimo anche i vincoli di disuguaglianza presenti in origine all'uguaglianza credo finiremmo per ridurre notevolmente lo spazio di soluzione del problema originale, e non è questo il nostro scopo (nella mia mente vedo un semipiano che collassa in una retta per ogni vincolo in cui si passa da disuguaglianza a uguaglianza stretta, poi magari è follia...).

Infine, se non toccassimo i due vincoli del problema fondendoli, non attueremmo di fatto nessun rilassamento.



Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline Mithrandir

  • Maestro Geek
  • *
  • *
  • *
  • Post: 1.157
  • Reputazione: 44
  • Sesso: Maschio
  • Battlemage
Re:Rilassamenti (Esame 17/2/2010)
« Risposta #2 il: 12 Febbraio 2011, 18:25:15 »
Grazie per i chiarimenti!

Quindi il surrogato diventerebbe un problema con la stessa funzione obiettivo ed il seguente vincolo:
\mu\sum_{i\in I}a_i^1x_i + u \sum_{i\in I}a_i^2x_i \ge \mu\cdot b_1 + u\cdot b_2
dove u e µ sono i coefficienti della combinazione lineare.
Portando il vincolo in funzione obiettivo si ottiene direttamente il Lagrangiano Primale.

Sono d'accordo con quanto dici sulla scelta del vincolo di disuguaglianza poiché meno stringente. Ha senso.

 :ciao:
Spoiler (click to show/hide)
Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now - at the turn of the tide.


Offline Dex

  • Utente Fidato
  • *
  • *
  • *
  • Post: 412
  • Reputazione: 12
  • Sesso: Maschio
Re:Rilassamenti (Esame 17/2/2010)
« Risposta #3 il: 23 Febbraio 2011, 18:19:31 »
Riutilizzo questo topic per scrivere il mio dubbio.

Quando c'era stato mostrato per la prima volta il rilassamento Lagrangiano il professore quando andava ad inserire i vincoli nella funzione obiettivo li inseriva andando effettuando una sottrazione tra la funzione obiettivo originale e i vincoli (Es. f(x)-vincoli), quando però si è andati a fare esempi concreti come il multicommodity e l'UFL quando ha effettuato il rilassamento questi vincoli sono stati sommati, il mio dubbio è c'è una regola generale o si può inserire i vincoli sommandoli o sottraendoli alla funzione obiettivo senza starci a pensare più di tanto?

Offline Raptor

  • Utente Fidato
  • *
  • *
  • *
  • Post: 489
  • Reputazione: 11
  • Sesso: Maschio
    • rpt@altervista
Re:Rilassamenti (Esame 17/2/2010)
« Risposta #4 il: 23 Febbraio 2011, 18:31:38 »
mi pare che questo dubbio fosse stato sollevato anche a lezione.
dipende da che valore diamo ai coefficienti (positivi o negativi), quindi è lo stesso  :si:

Offline Mithrandir

  • Maestro Geek
  • *
  • *
  • *
  • Post: 1.157
  • Reputazione: 44
  • Sesso: Maschio
  • Battlemage
Re:Rilassamenti (Esame 17/2/2010)
« Risposta #5 il: 23 Febbraio 2011, 18:40:05 »
dipende da che valore diamo ai coefficienti (positivi o negativi), quindi è lo stesso  :si:
Questo vale nel caso di vincoli di uguaglianza, in cui i coefficienti possono essere sia positivi che negativi per cui la somma diventa algebrica. Non tutti i coefficienti, però, possono assumere valori negativi (vedi vincoli di disuguaglianza).

~ EDIT
Ok, ho cancellato quello che avevo scritto. Rileggendolo e confrontando con gli appunti mi sono reso conto di non avere una risposta. So che avevo risolto questo mio dubbio in qualche modo, ma non riesco più a ricordarmelo.
« Ultima modifica: 23 Febbraio 2011, 18:53:56 da Mithrandir »
Spoiler (click to show/hide)
Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now - at the turn of the tide.


Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Rilassamenti (Esame 17/2/2010)
« Risposta #6 il: 23 Febbraio 2011, 20:18:11 »
Se il vincolo è di uguaglianza le variabili che andiamo ad introdurre sono libere, quindi potendo assumere valori sia positivi che negativi non c'è "problema" con la scelta del segno.
Se il vincolo è di disuguaglianza, allora le variabili duali sono vincolate ad essere maggiori o uguali a zero. In questo caso siamo sempre andati a sottrarre (in problemi di minimo).
Nel rilassamento del MCNF il vincolo appare sommato, ma è anche scritto al contrario. Anziché portare a destra il termine con la sommatoria (come si è sempre visto), abbiamo spostato a sinistra il termine di capacità (gli ukij), quindi sostanzialmente il risultato è il medesimo.
Nel UFL invece sommiamo anche per il vincolo di disuguaglianza, ma credo poiché siamo in un problema di massimo.

Temo non ci sia una regola d'oro per affrontare questo argomento, ma sia necessario andare ad analizzare ogni volta se quanto si sia scritto sia coerente con quello che si vuole ottenere.

Col il rilassamento sappiamo di dover ottenere dei LB/UP migliori dell'ottimo a seconda che si sia in min/max, ma allo stesso tempo deve essere in grado di fornire il fattore di penalizzazione sul vincolo non rispettato.
La scelta del segno credo quindi derivi direttamente da cosa si stia andando ad integrare nella f.o. del problema originale.

So che non è granché come spiegazione, ma anche leggendo su altri documenti sull'argomento non appare citato da nessuna parte qualcosa di più specifico.
« Ultima modifica: 24 Febbraio 2011, 01:46:01 da Cosmos »
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"