constraint programming con ilog solver
DESCRIPTION
Constraint Programming con ILOG Solver. Modellare e risolvere problemi con CP. Michele Lombardi . Cosa ci aspetta. Di cosa parleremo. Modellazione e soluzione di problemi con CP Strumenti per modellare (variabili, vincoli) Problematiche di modellazione - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/1.jpg)
Constraint Programming con ILOG Solver
Modellare e risolvere problemi con CP
Michele Lombardi <[email protected]>
![Page 2: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/2.jpg)
Cosa ci aspetta
2
Modellazione e soluzione di problemi con CP Strumenti per modellare (variabili, vincoli) Problematiche di modellazione Ottimizzazione del modello e del metodo di soluzione
Risolutore: ILOG solver
Di cosa parleremo...
...e come ne parleremo Considereremo un unico esempio di riferiento... ...e TANTE sue varianti ;-) Ad ogni passo sarà introdotto qualcosa di nuovo... ...e vi sarà proposto qualche esercizio
![Page 3: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/3.jpg)
Modellare un problemaModellare un problema con CP
Introduzione a ILOG Concert & Solver
![Page 4: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/4.jpg)
Il nostro esempio
4
Supponiamo di dover ottimizzare l’esecuzione di tasks su un sistema multiprocessore
T = {t0, t1, ..., tn-1} = insieme degli n tasks P = {p0, p1, ..., pp-1} = insieme dei p processori dur(ti) = durata del task i-mo
Siano:
> Ogni task esegue su un solo processore> Su ogni processore i task eseguono in sequenza> Il tempo totale di esecuzione non deve superare una
deadline
Obiettivo: usare il minimo numero di processori
Modellare un problema
![Page 5: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/5.jpg)
5 Modellare un problema
t0 t1 t2 t3 t4
p0
p1
p2
t0
t1
t2 t3
t4
Semplice, no? Come lo affrontiamo? Vediamo che strumenti abbiamo a disposizione
![Page 6: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/6.jpg)
Introduzione ad ILOG CP
6
ILOG è una azienda francese Produce strumenti per la gestione efficiente di processi di
manageriali e per la soluzione di problemi di ottimizzazione
Che cosa è ILOG?
A noi ci interessano questi
Modellare un problema
Strumenti per modellare problemi Strumenti per risolvere problemi
In particolare:
![Page 7: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/7.jpg)
7
OPL
Cplex
Solver Scheduler
CPOptimizer
AMPL
Concert Dispatcher
ILOG CP
Linguaggio di Modellazione MILP Linguaggio di
modellazione a vincoli
API per modellazione
Math Programming Solver
Semi-automatic CP solver
CP Solvers
Modellare un problema
![Page 8: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/8.jpg)
In pratica...
8
AMPL e OPL sono linguaggi per descrivere modelli Concert è una libreria in C++ Fornisce classi e funzioni per costruire modelli
Modellare un problema
class IloModel modello class IloIntVar variabile intera class IloNumVar variabile reale class IloBoolVar variabile logica class IloConstraint vincolo ...
Per esempio:
Solver è un risolutore (sempre in C++) che dato un modello (ex. costruito in concert) trova una soluzione
![Page 9: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/9.jpg)
9 Modellare un problema
Allora da dove partiamo?
Da carta e penna
![Page 10: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/10.jpg)
Un primo modello
10 Modellare un problema
One dimensional bin packing:
altrimenti
usatoèpsey ii 0
1 Variabili:
altrimenti
psuètsex iiij 0
1
Vincoli:
1
0
1p
iijxj
1
0
)(n
jiijj ydeadlinextduri
> Ogni task esegue su un solo processore
> Il tempo totale di esecuzione non deve superare una deadline
![Page 11: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/11.jpg)
11 Modellare un problema
1
0
minp
iiyz
Formulato il modello su carta, possiamo “costruirlo” usando Concert
1
0
1p
iijxj
1
0
)(n
jiijj ydeadlinextduri
Nel complesso:
obiettivo:
soggetto a:
}1,0{, iji xy
![Page 12: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/12.jpg)
Struttura di un programma ILOG
12 Modellare un problema
#include <ilconcert/ilomodel.h>#include <ilsolver/ilosolver.h>
ILOSTLBEGIN
int main(int argc, char** argv){ IloEnv env; IloModel model(env); <inizializzazione modello> <invocazione del solver> <output>}
Per usare concert e solver
MACRO: definisce il namespace std
IloEnv: gestore della memoria, fa da contenitore per il modello
Classe che rappresenta un modello
Variabili e vincoli vengono “aggiunti” al modello
![Page 13: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/13.jpg)
Costruzione del modello
13 Modellare un problema
Per inizializzare un modello innanzitutto vanno definite le sue variabili:
IloIntVarArray Y(env, nproc, 0, 1);
IloArray<IloIntVarArray> X(env, nproc);for(int i = 0; i < nproc; i++){ X[i] = IloIntVarArray(env, ntask, 0, 1);}
Array di variabili intere
Array di arrays Parametri di IloIntVarArray: IloEnv: gestore della memoria IloInt: dimensione IloInt: lower bound del dominio IloInt: upper bound del dominio
![Page 14: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/14.jpg)
Costruzione del modello
14 Modellare un problema
Poi vanno specificati i vincoli
for(int j = 0; j < ntask; j++){ IloIntExpr sum(env); for(int i = 0; i < nproc; i++){ sum += X[i][j]; } model.add(sum == 1);}
Costruisce una espressione vuota...
...che può essere estesa con i normali operatori aritmetici!
I vincoli vanno aggiunti al modello (vengono aggiunte anche le variabili su cui sono definiti)
L’operatore di confronto (“==“) tra espressioni restituisce un vincolo
1
0
1p
iijxj
![Page 15: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/15.jpg)
Costruzione del modello
15 Modellare un problema
for(int i = 0; i < nproc; i++){ IloIntExpr sum(env); for(int j = 0; j < ntask; j++){ sum += durations[j]*X[i][j]; } model.add(sum <= deadline*Y[i]);}
1
0
)(n
jiijj ydeadlinextduri
![Page 16: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/16.jpg)
Costruzione del modello
16 Modellare un problema
In qualunque punto (dopo la definizione delle variabili) si può specificare una funzione obiettivo
1
0
minp
iiyz
model.add(IloMinimize(env, IloSum(Y)));
Indica che la soluzione deve minimizzare l’espressione specificata
Un modo compatto per costruire una espressione di somma (Y è un array)
![Page 17: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/17.jpg)
Utilizzo del solver
17 Modellare un problema
<inizializzazione del modello>IloSolver solver(env);solver.extract(model);solver.solve();<output>
Costruisce un solver (classe IloSolver)
Trova la soluzione ottima (se esiste)
“estrae” il modello
Prima di iniziare la ricerca di una soluzione il modello deve essere convertito nel formato interno del solver
Questa operazione si chiama “estrazione” Classi concert: Ilo... (ex IloIntVar) Classi solver: Ilc... (ex. IlcIntVar)
![Page 18: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/18.jpg)
Input & Output
18 Modellare un problema
Number of fails : 9282Number of choice points : 9312...Running time since creation : 0.2
Y[0]:0 Y[1]:0 Y[2]:1 Y[3]:1 Y[4]:1 Y[5]:1
int ntask = 10;int nproc = 6;int durations[] = {3, 4, 7, 2, 2, 8, 7, 10, 8, 9};int deadline = 16;
![Page 19: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/19.jpg)
Stili di modellazioneModelli alternativi
![Page 20: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/20.jpg)
Un altro modello
20 Stili di modellazione
CP ha un linguaggio di modellazione molto “ricco” (molti tipi di vincoli)
Questo permette di migliorare le performance adottando stili di modellazione differenti
Esempio:Cambiamo le variabili!
iij psuètseix
Solo una variabile per task
IloIntVarArray Proc(env, ntask, 0, nproc-1);
Tra l’altro in questo modo ogni task esegue per forza su un solo processore
![Page 21: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/21.jpg)
Un altro modello
21 Stili di modellazione
Un vincolo può essere utilizzato all’interno di una espressione: denota 1 se è vero, 0 se è falso
Come definire i vincoli di deadline? METAVINCOLI
1
0
)()(n
jjj deadlineixtduri
for(int i = 0; i < ntask; i++){ IloIntExpr sum(env); for(int j = 0; j < ntask; j++){ sum += durations[j]*(Proc[j] == i); } model.add(sum <= deadline);}
![Page 22: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/22.jpg)
Un altro modello
22 Stili di modellazione
Cambia anche la funzione obiettivo:
)(maxmin jj xz
model.add(IloMinimize(env, IloMax(Proc)));
Il più alto indice di processore utilizzato
Il nuovo modello ha la stessa semantica (=> le stesse soluzioni), ma un numero minore di variabili e una diversa funzione obiettivo
![Page 23: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/23.jpg)
Output
23 Stili di modellazione
Number of fails : 425Number of choice points : 432...Running time since creation : 0.03
Proc[0]:0Proc[1]:0Proc[2]:0Proc[3]:0Proc[4]:1Proc[5]:2Proc[6]:3Proc[7]:1Proc[8]:2Proc[9]:3
![Page 24: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/24.jpg)
Esercizio 1 (base2.cpp)
24 Stili di modellazione
Cosa succede con i due modelli aumentando il numero di processori a 16?
Perché?
![Page 25: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/25.jpg)
Vincoli globaliUtilizzo dei vincoli globali
![Page 26: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/26.jpg)
Perché i vincoli globali
26 Vincoli globali
modellazione più compatta propagazione più efficace (a volte) propagazione più efficiente
I vincoli globali modellano alcune sottostrutture particolarmente frequenti. Hanno diversi vantaggi:
Esempio:Gli ultimi p task devono essere assegnati a processori diversi
![Page 27: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/27.jpg)
Modello con vincoli binari
27 Vincoli globali
Modellando con vincoli “!=“:
Number of fails : 44496Number of choice points : 44505...Running time since creation : 1.5
for (int i = ntask-nproc; i < ntask; i++){ for (int j = i+1; j < ntask; j++){ model.add(Proc[i] != Proc[j]); }}
Output:
![Page 28: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/28.jpg)
Modello con alldifferent
28 Vincoli globali
Alldifferent in ILOG
IloAllDiff(IloEnv, IloIntVarArray)
Nel nostro caso:
IloIntVarArray diff(env); for(int j = ntask-nproc; j < ntask; j++) diff.add(Proc[j]);
model.add(IloAllDiff(env, diff));
ATTENZIONE! Dopo aver estratto il modello:solver.setDefaultFilterLevel(IloAllDiffCt, IloExtendedLevel);
IloExtendedLevelIloMediumLevel IloBasicLevel IloLowLevel
IlcFilterLevel
IloAllDiffCtIloDistributeCt IloSequenceCt
IloAllMinDistanceCtIloPartitionCt
IloAllNullIntersectCt IloEqUnionCt
IloNotOverlapCt IloBoxCt
IlcFilterLevelConstraint
![Page 29: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/29.jpg)
Output
29 Vincoli globali
Number of fails : 8Number of choice points : 16...Running time since creation : 0
problem solvedProc[0]:0Proc[1]:0Proc[2]:0Proc[3]:1Proc[4]:0Proc[5]:1Proc[6]:2Proc[7]:3Proc[8]:4Proc[9]:5
IMPORTANTE:ILOG Solver permette anche di definire nuovi vincoli, ma per il
momento non ci interessa...
![Page 30: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/30.jpg)
Esercizio 2 (base2.cpp)
30 Vincoli globali
Nuovo vincolo: non più di tre task per processore
SUGGERIMENTO: il vincolo gcc in ILOG è:
IloDistribute(IloEnv, IloIntVarArray cards, IloIntArray vals, IloIntVarArray vars)
solver.setDefaultFilterLevel(???, ???);
Ricordate che dopo l’estrazione va modificato l’algoritmo di filtering...
![Page 31: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/31.jpg)
Strategie di ricercaModificare la strategia di ricerca
![Page 32: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/32.jpg)
Search strategy
32 Strategie di ricerca
Per esempio si può scegliere il criterio con cui scegliere la variabile su cui fare branching
CP permette l’impiego di diverse strategie di ricerca
IloGenerate(IloEnv, IloIntVarArray, IloChooseIntIndex)
IloChooseFirstUnboundIntIloChooseMaxMaxIntIloChooseMaxMinInt
IloChooseMaxRegretMaxIloChooseMaxRegretMinIloChooseMaxSizeIntIloChooseMinMaxIntIloChooseMinMinInt
IloChooseMinRegretMaxIloChooseMinRegretMinIloChooseMinSizeInt
E’ un IloGoal, va passato come argomento di solver.solve(...)
First Fail Principle
![Page 33: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/33.jpg)
Output
33 Search stratgies
solver.solve(IloGenerate(env, Proc, IloChooseMinSizeInt))
Number of fails : 71Number of choice points : 77...Running time since creation : 0.01
IMPORTANTE:ILOG Solver permette anche di definire
nuove strategie o di intervenire sulla ricerca in modo ancora più complesso, ma per il momento non ci interessa...
![Page 34: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/34.jpg)
Esercizio 3 (base.cpp, base2.cpp)
34 Search stratgies
Cosa succede con altre strategie di ricerca?
Cosa succede utilizzando il first fail principle (IloChooseMinSizeInt) nel primo modello? Perché?
![Page 35: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/35.jpg)
SimmetrieEliminazione delle simmetrie
![Page 36: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/36.jpg)
Simmetrie
36 Simmetrie
I processori sono risorse simmetriche; per esempio le due allocazioni:
Proc[0]:0Proc[1]:0Proc[2]:0Proc[3]:0Proc[4]:1Proc[5]:2Proc[6]:3Proc[7]:1Proc[8]:2Proc[9]:3
e
Proc[0]:1Proc[1]:1Proc[2]:1Proc[3]:1Proc[4]:0Proc[5]:2Proc[6]:3Proc[7]:0Proc[8]:2Proc[9]:3
Sono del tutto equivalenti!
![Page 37: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/37.jpg)
Simmetrie
37 Simmetrie
Una soluzione è quella di forzare un ordine di preferenza tra i processori: se p0 è libero non utilizzare uno dei processori seguenti Si possono aggiungere dei vincoli per vietare le allocazioni che
non rispetterebbero il criterio Per ogni processore teniamo traccia del task di indice più basso
allocato su di esso (dopo vedremo come)
IloIntVarArray minItem(env, nproc, 0, ntask-1);
Il task di indice più basso su p0 deve essere minore di quello su p1, e così via
for(int i = 0; i < nproc-1; i++){ model.add(minItem[i] < minItem[i+1]);}
![Page 38: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/38.jpg)
Simmetrie
38 Simmetrie
Come ottenere minItem?
model.add(minItem(Proc[0]) == 0);for(int i = 1; i < ntask; i++){ IloConstraint xpr = Proc[i] != Proc[i-1]; for(int j = i-2; j >= 0; j--){ xpr = xpr && (Proc[i] != Proc[j]); } model.add(IloIfThen(env, xpr, minItem(Proc[i]) == i));}
METAVINCOLI: i vincoli possono essere combinati in espressioni logiche!
Element constraint in ILOG
![Page 39: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/39.jpg)
Output
39 Simmetrie
Number of fails : 84Number of choice points : 92...Running time since creation : 0.01
Proc[0]:0Proc[1]:0Proc[2]:0Proc[3]:0Proc[4]:1Proc[5]:2Proc[6]:3Proc[7]:1Proc[8]:2Proc[9]:3
![Page 40: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/40.jpg)
Scheduling con ILOGIntroduzione ad ILOG Scheduler
![Page 41: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/41.jpg)
ILOG Scheduler
41 Scheduling con ILOG
Un’altra libreria in C++ Fornisce strumenti per modellare e risolvere problemi di
scheduling Si appoggia al Solver per la soluzione del problema La classe IlcScheduler permette di accedere alla soluzione
Alcuni concetti chiave:
Attività Vincoli temporali Risorse ...
![Page 42: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/42.jpg)
Attività
42 Scheduling con ILOG
Definite con:
IloActivity(env, IloInt duration);IloActivity(env, IloNumVar duration);
Una attività introduce tre variabili: START, END, DUR END = START + DUR
IloArray<IloActivity> acts(env, ntask);for(int i = 0; i < ntask; i++){ acts[i] = IloActivity(env, durations[i]);}
![Page 43: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/43.jpg)
Vincoli temporali
43 Scheduling con ILOG
IloActivity::startsAfterEnd(IloActivity);IloActivity::startsAfterStart(IloActivity);...
...Restituiscono vincoli che forzano relazioni di precedenza
IloActivity::startsBefore(...);IloActivity::startsAfter(...);...
...Restituiscono vincoli temporali rispetto ad istanti fissati (o a variabili intere)
for(int i = 0; i < nprec; i++){ model.add(acts[precTo[i]].startsAfterEnd(acts[precFrom[i]]));}
![Page 44: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/44.jpg)
Risorse
44 Scheduling con ILOG
Per ora consideriamo solo risorse unarie:IloUnaryResource(IloEnv)
Il metodo IloActivity::requires(...) restituisce un vincolo che va aggiunto al modello
IloArray<IloUnaryResource> pres(env, nproc);for(int i = 0; i < nproc; i++) pres[i] = IloUnaryResource(env); for(int i = 0; i < nproc; i++){ for(int j = 0; j < ntask; j++){ model.add(IloIfThen(env, Proc[j] == i, acts[j].requires(pres[i]))); }}
![Page 45: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/45.jpg)
Input & Output
45 Scheduling con ILOG
Proc[0]:0 task[0]: [0 -- 3 --> 3]Proc[1]:0 task[1]: [3 -- 4 --> 7]Proc[2]:1 task[2]: [9 -- 7 --> 16]Proc[3]:2 task[3]: [2 -- 2 --> 4]Proc[4]:2 task[4]: [0 -- 2 --> 2]Proc[5]:0 task[5]: [7 -- 8 --> 15]Proc[6]:3 task[6]: [0 -- 7 --> 7]Proc[7]:2 task[7]: [4 -- 10 --> 14]Proc[8]:3 task[8]: [7 -- 8 --> 15]Proc[9]:1 task[9]: [0 -- 9 --> 9]
int nprec = 5;int precFrom[] = {0, 0, 4, 6, 3};int precTo[] = {1, 2, 5, 5, 8};
Goal: IloGenerate(env, Proc, ...) && IloSetTimesForward(env)
![Page 46: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/46.jpg)
Esercizio 4 (sched.cpp)
46 Scheduling con ILOG
Cosa succede modificando il livello di propagazione?
IloSchedulerEnv schedEnv(env);schedEnv.getResourceParam().setCapacityEnforcement(...);
Notate che IloExtended abilita edge finder
Nuovo vincolo: i task 0, 3, 6, 9 devono accedere ad una memoria a due vie
Risorsa a capacità maggiore di 1: IloDiscreteResource
![Page 47: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/47.jpg)
Minimizzare il tempo di esecuzione
47 Scheduling con ILOG
Introduciamo una nuova variabile (makespan):
IloIntVar makespan(env);
Tutte le attività devono terminare prima del tempo di esecuzione:for(int i = 0; i < ntask; i++) model.add(acts[i].endsBefore(makespan));
Nuovo obiettivo:model.add(IloMinimize(env, makespan));
Goal ottimizzato: IloGenerate(env, Proc, ...)&& IloSetTimesForward(env, makespan)
![Page 48: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/48.jpg)
Output
48 Scheduling con ILOG
Proc[0]:0 task[0]: [0 -- 3 --> 3]Proc[1]:0 task[1]: [10 -- 4 --> 14]Proc[2]:0 task[2]: [3 -- 7 --> 10]Proc[3]:1 task[3]: [2 -- 2 --> 4]Proc[4]:1 task[4]: [0 -- 2 --> 2]Proc[5]:1 task[5]: [7 -- 8 --> 15]Proc[6]:2 task[6]: [0 -- 7 --> 7]Proc[7]:3 task[7]: [0 -- 10 --> 10]Proc[8]:2 task[8]: [7 -- 8 --> 15]Proc[9]:4 task[9]: [0 -- 9 --> 9]
![Page 49: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/49.jpg)
Esercizio 5 (schedMK.cpp)
49 Scheduling con ILOG
Cosa succede usando il goal IloSetTimesFOrward non ottimizzato?
Cosa succede eliminando le relazioni di precedenza?
![Page 50: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/50.jpg)
Basta teoria ;-)Adesso mettiamo le mani in pasta
![Page 51: Constraint Programming con ILOG Solver](https://reader036.vdocumenti.com/reader036/viewer/2022081507/56815a5e550346895dc79402/html5/thumbnails/51.jpg)
Istruzioni
51
Fate login su windows Dal sito del corso scaricate il template di progetto Aprite il file “template.sln” con visual studio 2005 Nel pacchetto con il template ci sono anche alcuni file sorgente,
che contengono il codice di partenza: in ogni esercizio è specificato da quali sorgenti dovete partire per risolverlo
Per lanciare gli eseguibili aprite un prompt dei comandi usando il file batch “START.bat”, sempre nel pacchetto con il template: serve per accedere alla licenza per l’uso di ILOG
BUON LAVORO!