R il a ss a m e n to la g ra n g ia n o p e r u n p ro b le m a d i sc h e d u li n g ( I p a rt e )

(1)

DipartimentodiInformatica UniversitàdegliStudi–L’Aquila –Italy salvatore.nocella@di.univaq.it http://www.oil.di.univaq.it

R il a ss a m e n to la g ra n g ia n o p e r u n p ro b le m a d i sc h e d u li n g ( I p a rt e )

Salvatore Nocella Sistemi Organizzativi(A.A. 2005-2006)

(2)

S o m m a ri o

»Problemidiottimizzazione ›Euristichee rilassamenti »Rilassamentolagrangiano ›Generalità ›Proprietà ›Subgradientoptimization »Un casodistudio: euristicalagrangianaper 1|r j|Σw jC j(II parte)

(3)

R if e ri m e n ti b ib li o g ra fi c i

»Colin R. Reeves edt. Modern Heuristic Techniques for Combinatorial Problems, McGraw-Hill, 1995 (chap. 6) »DimitrisBertsimas, John N. Tsitsiklis Introduction to Linear Optimization, Athena Scientific, 1997 (chap. 11) »P. Avella, M. Boccia, B. D’AuriaNear- Optimal Solutions of Large-Scale Single Machine Scheduling Problems,Technical ReportDIIMA -Universitàdi Salerno, 2002 http://www.optimization-online.org/DB_FILE/2002/05/479.pdf

(4)

Nozioniteorichepreliminari: problemadiottimizzazione »Einsiemeambiente(insiemedisoluzioni, decisionio alternative) »F⊆Einsiemeammissibiledefinitotramite un insiemedivincoli »f : E Rfunzioneobiettivo »Direzionediottimizzazione: minimoo massimo Problemadiottimizzazione(min) Trovareun elementox∈Ftale chef(x) <f(y) ∀y∈F. v = f(x)valoreottimo xsoluzioneottima

(5)

Nozioniteorichepreliminari: problemadiottimizzazionecombinatoria »Dati ›NinsiemefinitoN={1,…,n} ›cvettoredipesic jper ognij∈N ›Insiemeambiente U= {tuttii possibili2|N| sottoinsiemidiN} ›Insiemeammissibile FamigliaFdisottoinsiemiFdiU ProblemadiOttimizzazioneCombinatoria(min) min: SNj jScS ⊆ ∈

 ∈ ∑F

(6)

R is o lu z io n e d i p ro b le m i d i O .C .

»Metodiesatti: certificanol’ottimalitàdella soluzionerestituita(branch-and-bound, branch-and- cut, branch-and-price). ›Nelcasopeggiorehannocomplessitàesponenziale. »Metodiapprossimati: certificanola “distanza” massimatrala soluzionerestituitae quellaottima. ›Hanno complessitàpolinomialeo pseudo-polinomiale. »Metodieuristici: fornisconosoluzionisub-ottimedi cui non sicertificala qualità(local search, simulated annealing, genetic algorithms, lagrangean heuristic). ›Ha sensoprogettarlidicomplessitàpolinomiale.

(7)

V a lu ta z io n e d e ll e e u ri st ic h e

»Siadata un’istanzadiun problema(di minimizzazione) NP-hard »Applicandoun’euristicaa tale problema, la domandalegittimachesorgeè: «Quantoèrealmentebuonala soluzione restituita?»

(8)

V a lu ta z io n e d e ll e e u ri st ic h e

»La soluzioneottimadivide lo spaziodeivaloriin due regioni: ›I valorial disopradell’ottimo (upper bounds) sonogeneratida metodieuristici ›I valoriinferioriall’ottimo (lower bounds) sonoprodotti dallarisoluzionedirilassamenti »Desideratum: minima distanza trai “migliori”bound prodotti (lower e upper)

soluzioneottima del problema(min)

UPPER BOUNDS LOWER BOUNDS

(9)

R il a ss a m e n ti

»Datoilseguenteproblemadiottimizzazione »un suorilassamentoèilseguenteproblema in cui: 1. 2.

( )

minfx x∈R

( )

mingx x∈Q ⊇QR

( ) ( )

,xfxgx∀∈≥R

(10)

E se m p i

»Rilassamentolineare »Rilassamento

{}

11 11

maxmax 0,11,,011,,

nn iiii ii nn iiii ii ii

pxpx wxBwxB xinxin

== ==≤→≤ ∈=≤≤=

∑∑ ∑∑ …… {}{}

1 1 1

min min 11,, 0,11,, 0,11,,

n jj j n n jj j ijj j j j

cx cx axim xjn xjn

= = =≥=→ ∈= ∈=

∑ ∑ ∑

… … …

(11)

R il a ss a m e n to la g ra n g ia n o

»Unoschema moooltointroduttivo: ›Si prendeunaformulazionediper un qualsiasi problemadiottimizzazionecombinatoria; ›Si “attaccano”deimoltiplicatoriad un sottoinsiemedivincoli, rilassandolidalla formulazionee inserendolinellafunzione obiettivo ›Si risolve(all’ottimo) ilproblemarisultante »Requisito: ilproblemarilassatoè“facile”

(12)

Rilassamentolagrangiano: motivazioni »Rilassamentolagrangianomolto usato perché: ›MoltiproblemidiO.C. sonocostituitidaun problemafacile (ossiarisolvibileall’ottimodaun algoritmopolinomiale) complicatodaun certo numerodiulteriorivincoli(side-constraints). Portandoquest’ultimogruppodivincolinella funzioneobiettivoilproblemarisultantediventa facile. ›La praticaindicachequestoapprocciofornisce buonilower bounds con sforzicomputazionali contenuti.

(13)

Rilassamentolagrangiano: fondamenti »Siadatoilseguenteproblema »ilsuorilassamentolagrangiano, rispettoal primo gruppodivincoli, è

() {}

min st P 0,1

cx Axb Cxd x

≥ ≥ ∈ ()() {}

min LLBPst 0,1

cxbAx Cxd x

λ+− ≥ ∈

(14)

Rilassamentolagrangiano: fondamenti »I valoriin sonodettimoltiplicatoridi Lagrange »Comunquesisceglieλ, la soluzioneZ R(λ) del problema(LLBP)ètale che Z LLBP(λ) <Z P ovvero(LLBP)èun rilassamentodi(P).

0λ≥

(15)

Rilassamentolagrangiano: due questioni »Problemastrategico: come sceglierei vincolidarilassare? »Problematattico: qualisonoi valoridei moltiplicatorichemassimizzanoilvaloredel lower bound trovato? »Quest’ultimopuntoimplicala risoluzionedel seguenteproblema(dualelagrangiano) () {}

0

min max 0,1

cxbAx stCxd x

λ

λ ≥

+−  ≥   ∈ 

(16)

Rilassamentolagrangiano: proprietà »Prop. 1: Se la soluzionediLLBP non cambia (∀λ) rimpiazzandoi vincolidiinterezza [x∈{0,1}] con illororilassamentolineare [0<x<1] allorailrilassamento/lower bound lagrangianosidice goderedellaintegrality property. »Prop. 2: Quandoun rilassamento lagrangianogodedell’integralityproperty, il massimolower bound ottenibileèparial valoredel rilassamentolineare; viceversa, i lower bound ottenibilidaaltririlassamenti possonoanchemigliorarlo.

(17)

Rilassamentolagrangiano: problema strategico »Se un problemaha diversiinsiemidivincoli alloraesistonoanchediversirilassamenti lagrangianipossibili »Nell’affrontareilproblemastrategicosideve tenerconto: ›Integrality property diciascunrilassamento ›Complessitàdel rilassamento: sarannoconsiderati solo queirilassamenticheportinoa problemi risolubiliin un numeropolinomiale(o pseudopolinomiale) dioperazioni ›Numerodimoltiplicatori: a paritàdiqualitàdel bound prodottoèdapreferireilrilassamentocon ilminor numerodimoltiplicatori

(18)

Rilassamentolagrangiano: problema tattico »Datoun particolarerilassamento(problema strategico), come determinareilmigliorset dimoltiplicatori? »Due approccipossibili: ›Subgradientoptimization ›Multiplier adjustment

(19)

S u b g ra d ie n t o p ti m iz a ti o n

»Proceduraiterativache, a partiredaun set inizialedimoltiplicatori, negenera altriin manierasistematica. »Puòesserevista come unaprocedurache tentadimassimizzareillower bound ottenutoscegliendoopportunamentei moltiplicatori. »Non èun processomonotóno: tra un’iterazionee la successivapuòaccadere cheilbound peggiori.

(20)

S u b g ra d ie n t o p ti m iz a ti o n

»Descrizionedellaprocedura 1.Siaπun parametrodefinitodall’utentetale che 0<π<2. Si inizializziZ UBe ilvettoredei moltiplicatoriinizialiλ 2.Si risolvaLLBP con ilset correntedi moltiplicatori. SiaX = [X 1, …, X j, …, X n]la soluzionetrovatadivaloreZ LB 3.Si determiniilvettoreGdeisubgradienticome: 11,,

n iiijj jGbaXim ==−= ∑

…

(21)

S u b g ra d ie n t o p ti m iz a ti o n

4.Si definiscalo step-size T: 5.Si aggiorniilvettoredeimoltiplicatoriλ: »Per questaproceduraènecessario, infine, definireunaregoladiarresto

() 2 1

UBLB m i i

ZZ T G

π =

− = ∑ ()max0, iiiTGλλ=+

(22)

U n e se m p io : S e t c o v e ri n g p ro b le m

»Data unamatricecompostadam righeed n colonne, trovareilsottoinsiemedicolonnedi costominimochecopranole righedella matrice »Esempio: 0 1 1 1 0 A = 1 1 0 1 0 1 0 0 0 1

(23)

S e t c o v e ri n g : m o d e ll o d i IL P (0 ,1 )

»Variabiledidecisione »Formulazione {}

1 1

min 11,, 0,11,,

n jj j n ijj j j

cx staxim xjn

= =≥= ∈=

∑ ∑

… …

1se la colonna è nella soluzione 0altrimentijj x = 