Post on 06-May-2019
1Linguaggio MPL
Uso di MPL e Solver perproblemi LP ed ILP
Daniele VigoD.E.I.S. - Università di Bologna
dvigo@deis.unibo.it
rev. 4.1 - Aprile 2004
MPL.Intro.2D. Vigo
Problema della dieta n possibili alimentim sostanze nutritivebi fabbisogno giornaliero sostanza icj costo alimento jaij quantità di sostanza i per unità di alimento j
determinare la dieta (mix di alimenti) di costo minimo, assicurando il fabbisogno giornaliero di ogni sostanza
2Linguaggio MPL
MPL.Intro.3D. Vigo
Modello matematico (PL)• xj := quantità alimento j nella dieta, j=1, …, n
∑=
n
jjj xc
1min
mibxa i
n
jjij ,,1
1K=≥∑
=
njx j ,,10 K=≥
MPL.Intro.4D. Vigo
Dieta: esempio numericon = 5m = 8cj = { 10, 8, 15, 6, 16 }
bi = {40, 20, 30, 10, 42, 41, 65, 17}
aij = { 0, 36, 8, 20, 7,14, 89, 42, 17, 44,2, 1, 15, 0, 16, 36, 99, 9, 6, 19,0, 30, 26, 55, 28, 55, 17, 3, 1, 0,33, 7, 23, 0, 10,44, 10, 11, 0, 4}
3Linguaggio MPL
MPL.Intro.5D. Vigo
Soluzione 1: scrittura manuale• Definizione di un file di input (testo) per un
risolutore (Es. Cplex):
/*file CPLEX*/MINIMIZE
z: 10 x1 + 8 x2 + 15 x3 + 6 x4 + 16 x5SUBJECT TO
CONSTR1: 36 x2 + 8 x3 + 20 x4 + 7 x5 >= 40CONSTR2: 14 x1 + 89 x2 + 42 x3 + 17 x4 + 44 x5 >= 20CONSTR3: 2 x1 + x2 + 15 x3 + 16 x5 >= 30CONSTR4: 36 x1 + 99 x2 + 9 x3 + 6 x4 + 19 x5 >= 10CONSTR5: 30 x2 + 26 x3 + 55 x4 + 28 x5 >= 42CONSTR6: 55 x1 + 17 x2 + 3 x3 + x4 >= 41CONSTR7: 33 x1 + 7 x2 + 23 x3 + 10 x5 >= 65CONSTR8: 44 x1 + 10 x2 + 11 x3 + 4 x5 >= 17
END
MPL.Intro.6D. Vigo
Soluzione 2: scrittura su File• Scrittura automatica del file di input (testo):Void scrivi_dieta( n, m, a, b, c){
int i, j;FILE *fout;fout = fopen(“dieta.lp”,w);fprintf(fout,”MINIMIZE\n Z: ”);for (j = 1; j <= n; j++ )
if (c[j] > 0) fprintf(fout, “+%d x%d “,c[j], j );fprintf(fout,” \n SUBJECT TO \n”);for (i = 1; i <= m; i++ ) {
fprintf(fout, “CONSTR%d : “,i );for ( j = 1; j <= n; j++ ) if (a[i][j]>0) fprintf(fout, “+%d x%d “,a[i][j],j);fprintf(fout, “ >= %d \n”,b[i] );
}fprintf(fout,”END\n”);fclose(fout);
}
4Linguaggio MPL
MPL.Intro.7D. Vigo
Soluzione 3: MPL• Modello MPL del problema:TITLE
Dieta {problema della dieta}INDEX
sost := (Calorie, Proteine, Calcio, Ferro, VitA, VitB1, VitB2, Niacina);
cibo := (pasta, prosciutto, formaggio, uova, pane);DATA
Qmin[sost] = (40, 20, 30, 10, 42, 41, 65, 17);Costo[cibo] = (10, 8, 15, 6, 16);A[cibo,sost] = DATAFILE(dati_dieta.dat);
DECISION VARIABLESx[cibo]; ! quantità di cibo da acquistare
MODELMIN z = SUM(cibo: Costo*x);
SUBJECT TOFabbisogno[sost]: SUM(cibo: A*x) >= Qmin;
! equivalente a SUM(cibo: A[sost]*x) >= Qmin[sost];END
MPL.Intro.8D. Vigo
Soluzione 4: MPL+DATABASE
{ Diet.mpl }TITLE
ExampleOPTIONSDatabaseType = AccessDatabaseAccess = “diet.mdb"
INDEXnutrients := DATABASE(“sostanze",“sostanzaID"); foods := DATABASE(“cibi",“ciboID");
DATARequired[nutrients] = DATABASE(“sostanze", “min_req");Cost[foods] = DATABASE(“cibi", “costo_unit");A[foods,nutrients] = DATABASE("valori", foods="IDfoods", nutrients="IDnutrients");
DECISIONx[foods] EXPORT ACTIVITY TO DATABASE(“sostanze”);
MODELMIN z = SUM(foods: Cost*x) ;
SUBJECT TOCONSTR[nutrients] : SUM(foods: A*x) > Required[nutrients]
END
•Modello MPL del problema integrato con una base di dati
5Linguaggio MPL
MPL.Intro.9D. Vigo
Soluzione 5: Solver di ExcelProblema della Dieta
B C D E F G H I J K
(1000) (g) (g) (mg) (1000 ius) (B1) (mg) (B2) (mg) (mg) CostoCalorie Proteine Calcio Ferro Vit. A Tiamina Riboflavina Niacina €/Kg
Fabbisogno giornaliero 40 20 30 10 42 41 65 17 qta (Kg)pasta 0 14 2 36 0 55 33 44 10 0.508369prosciutto 36 89 1 99 30 17 7 10 8 0.691981formaggio 8 42 15 9 26 3 23 11 15 1.886085uova 20 17 0 6 55 1 0 0 6 0pane 7 44 16 19 28 0 10 4 16 0
Contenuto dieta 40 147.9191 30 103.7822 69.79765 45.38221 65 50.03497
costo complessivo (€) 38.91082
=MATR.SOMMA.PRODOTTO(B7:B11;$K$7:$K$11)
=MATR.SOMMA.PRODOTTO(J7:J11;K7:K11)
MPL.Intro.10D. Vigo
MPL: Introduzione• MPL è un pacchetto software che permette di
implementare modelli di programmazione lineare (LP) ed intera (ILP)
• E’ dotato di un linguaggio ad alto livello chepermette di descrivere sistemi anche moltocomplessi
• Realizza la separazione tra dati e modello e permette di importare i dati da diverse sorgenti (file di testo, excel, database …)
6Linguaggio MPL
MPL.Intro.11D. Vigo
MPL: Introduzione (2)• I modelli sono indipendenti dal risolutore
impiegato e dalla piattaforma sulla quale sono eseguiti (Windows, Unix, Macintosh, OSF Motif)
• Nell’output e nel log sono indicate, in modo comprensibile, tutte le operazioni svolte dal risolutore
• Esiste una libreria di oggetti (Optimax 2000) che contiene tutte le funzioni MPL e può essere usata da Visual Basic e Visual C++
MPL.Intro.12D. Vigo
MPL Modeling System (1)
DATAMODELS
MPL
SOLVERS
7Linguaggio MPL
MPL.Intro.13D. Vigo
MPL: solver MPL si può utilizzare i seguenti LP ed ILP solver:
• CPLEX della ILOG• XPress-MP della DASH Associates
ed anche:• OSL • XA • FrontLine• Lindo • FortMP • C-Whiz…
MPL.Intro.14D. Vigo
MPL: Input dataMPL consente di acquisire i dati di input:
• Direttamente nel file MPL• file di testo (ASCII)• foglio di lavoro Excel• database interno a MPL• database esterno (ACCESS, EXCEL, ODBC,
ORACLE…...)
8Linguaggio MPL
MPL.Intro.15D. Vigo
MPL: Modeling LanguageAlcune caratteristiche:
• Utilizzo di nomi lunghi e alias• Inclusione di file e direttive condizionali (#include, #define, #undef, #ifdef …)
• Utilizzo di sommatorie di vettori e matrici• Lunghezza righe: 255 caratteri (oltre ignorati)• Separatori: i diversi statement all’interno dello stesso
blocco devono essere divisi dal punto e virgola ;• Commenti: le parentesi graffe {} racchiudono un
blocco di commenti anche su più righe. • Il punto esclamativo ! delimita l’inizio di un commento
che termina a fine riga.
MPL.Intro.16D. Vigo
Struttura modello MPL (1)Parte 1: Dichiarazioni
• TITLE Nome del Modello (Opzionale)• INDEX Definizione indici per insiemi• DATA Dati di input e costanti• DECISION VARIABLES Variabili decisionali• MACRO Definizione di macro per parti ripetitive• OPTIONS Impostazione di molte delle
opzioni dell’ambiente MPL (alternativa ai menù)
9Linguaggio MPL
MPL.Intro.17D. Vigo
Struttura file MPL (2)Parte 2: Modello
• MODEL Inizio modello …• MAX/MIN Funzione obiettivo• SUBJECT TO Vincoli del modello• BOUNDS Upper e Lower bounds variabili• INTEGER Variabili intere• BINARY Variabili binarie• FREE Variabili libere• END … fine modello
MPL.Intro.18D. Vigo
MPL: Opzioni
OPTIONS
• Vengono specificate alcune opzioni per MPL.• Possono essere definite in qualunque punto del file.• Alcune possibili opzioni:
• directory corrente;• controlli sulla definizione delle variabili;• tipo e nome del database utilizzato;
OPTIONSDatabaseType = Access
DatabaseAccess = "kp.mdb"
10Linguaggio MPL
MPL.Intro.19D. Vigo
INDEXGli indici definiscono i domini del problema. Possono essere:• Numerici: intervallo di valori
nutrients:= 1..8;
• Nominali: lista di identificatorifoods :=(pasta,ham,cheese,egg,bread);città :=(BO,MI,FI,GE,NA);numeri:=(3,6,7,9,21,123);
• Il numero di caratteri può essere limitatofoods :=(pasta,ham,cheese,egg,bread):3;
genera (pas, ham, che, egg, bre);
MPL.Intro.20D. Vigo
INDEX: alias• Agli indici nominali si possono associare alias
(usati nei file di output al posto dei nomi) :foods:= (pasta,ham,cheese,egg,bread)
-> (p, h, c, e, b);
• oppure foods:=(pasta,ham,cheese,egg,bread):1;• Si può assegnare ad un indice il nome di un altro
(si chiama indice alias)INDEX
città :=(BO,MI,FO,RN,GE);orig := città;dest := città;
DECISION VARIABLEStrasp[orig,dest];
11Linguaggio MPL
MPL.Intro.21D. Vigo
INDEX: indici circolari• Se i domini rappresentano periodi di tempo è
spesso necessario usare operazioni in modulo sul valore dell’indice
day := (mo,tu,we,th,fr,sa,su) CIRCULAR;month := 1..12 CIRCULAR;…Inventory[month+5] …
se month=9, l’indice è (9+5)mod(12) = 2
MPL.Intro.22D. Vigo
INDEX: sottoinsiemi• Si possono definire sottoinsiemi di indici:
• bisogna specificare l’indice di base• la lista di valori del sottoinsieme
day := (mo,tu,we,th,fr,sa,su);month := 1..12 CIRCULAR;
holiday[day] := (sa,su);summer[month] := 7..9;servicedays[day] := (mo,we,fr); repair[month] WHERE (month>=5)AND(month<=8);
12Linguaggio MPL
MPL.Intro.23D. Vigo
INDEX: Set operations• Con gli indici si possono fare operazioni insiemistiche
INDEXplants := (NewYork, Chicago, London, Paris);OpenPlants[plants] := (NewYork,London);EuroPlants[plants] := (London, Paris);
! Differenza e NOTClosedPlants[plants]:= plants – OpenPlants;USAPlants[plants] := NOT EuroPlants;
!Unione ed IntersezioneOpenOrEuro[plants] := OpenPlants OR EuroPlants;
OpenAndEuro[plants] := OpenPlants AND EuroPlants;
MPL.Intro.24D. Vigo
INDEX: indici multidimensionali (1)• Spesso i diversi indici sono collegati tra loro• E` possibile tener conto esplicitamente delle
associazioni tra elementi di indici• Es. coppie (impianto,macchina)
INDEXplants := (Atlanta, Chicago, Dallas);machine := (Grind, Drill, Press); PlantMachine[plants,machine] :=
(Atlanta.Grind, Chicago.Drill, Chicago.Press, Dallas.Grind);
13Linguaggio MPL
MPL.Intro.25D. Vigo
INDEX: indici multidimensionali (2)• Invece di listare tutte le coppie si può usare
node1 := (n1, n2, n3, n4);node2 := node1;arcs[node1,node2] WHERE (node1<>node2);
• E` possibile accedere direttamente a tutte le coppie che hanno un certo valore di un indice
INTEGER VARIABLESProd[PlantMachine];
SUBJECT TOCapa_sede[plants]:
SUM(Macc in machine: Prod) < MCAP;
MPL.Intro.26D. Vigo
INDEX: importazione da file• Gli elementi dell’indice possono essere letti da file
INDEX
plants := INDEXFILE(”plants.dat”,2);! file1, Atlanta, 127.35, 221.332, Dallas, 112.44, 212.00
PlantMachine[plants,machine] :=INDEXFILE(”PlantMach.dat”);
! fileplant1, mach1,plant1, mach2,
14Linguaggio MPL
MPL.Intro.27D. Vigo
INDEX: importazione da Excel e DbINDEX
plants := EXCELRANGE(”plants.xls”,”Plantrange”);
Apre plants.xls e legge dal primo foglio (o da quello specificato nelle opzioni) gli elementi dal rangePlantrange fino alla prima cella vuota
plants := DATABASE(”plants”,”plantsID”);plants := DATABASE(”plants”); plants := DATABASE(”plants”,”location”);plants := DATABASE(”plants”,WHERE country =“Italy”);
Apre la tabella plants e definisce l’indice in base al contenuto dei campi plantsID o location
MPL.Intro.28D. Vigo
DATA (1)• In questa sezione si specificano i coefficienti
utilizzati dal modello (costanti o vettori)
1. Costanti: DATA
MaxP = 10;MeseFerie = 3;
…INDEX
Pezzi := 1..MaxP;
15Linguaggio MPL
MPL.Intro.29D. Vigo
DATA (2)• Se il valore è seguito da un ? a runtime ne viene
chiesto l’inserimento in una finestraDATA
MaxP = 10;MaximumInventory = 1200 ?;
…
• I valori possono anche essere letti da file, excel e db
MPL.Intro.30D. Vigo
DATA (3)2. Vettori (contenenti i dati di ingresso)INDEX
nutrients := 1..8;DATA
Required[nutrients] := (40, 20, 30, 10, 42, 41, 65, 17);
Vengono generate le variabili Required1, Required2, … Required8
con Required1 = 40, Required2 = 20, …
• Vettore sparso (solo alcuni elementi)Vet[nutrients] := [1: 5.0, 4: 7.5, 8: 10.0];
16Linguaggio MPL
MPL.Intro.31D. Vigo
DATA (4)Matrici (definite per righe)INDEX
i := 1..4;j := 1..3;
DATACost[i,j] := (40, 20, 30,
10, 42, 41, 19, 23, 32,65, 17, 13);
• Si possono usare formule e moltiplicatori:A[i] := (3, 4/5, 2*SQR(3)+2, 1/(3+2))Cost[nutrients] :=
1000 (10, 20, 3, 10, 10, 8, 6, 12);
• il valore 1000 è un moltiplicatore (Cost1=10000)
MPL.Intro.32D. Vigo
DATA (5)Dati da una fonte esterna: • File di testo:
A[foods,nutrients]:= 1000 DATAFILE(”input.dat");
{ input.dat }! Calories Protein Calcium Iron VitaminA Thiamine Riboflavin Niacin! (1000) (grams) (grams) (MG) (1000 IU) (MG) (MG) (MG) WheatFlour 0 14 2 36 0 55 33 44CornMeal 36 89 1 99 30 17 7 10EvapMilk 8 42 15 9 26 3 23 11Margarine 20 17 0 6 55 1 0 0Cheese 7 44 16 19 28 0 10 4
• Database Excel: A[foods,nutrients]=EXCELRANGE(”input.xls",”foods");
17Linguaggio MPL
MPL.Intro.33D. Vigo
DECISION (1)• In questa sezione sono definite le variabili
decisionali del problema• Per definire un insieme di variabili con lo stesso
nome, si indica il nome del vettore e la dimensione del vettore stesso
DECISIONX[foods];
• Si possono definire variabili multidimensionali.MultiVar[foods,nutrients] -> Y;Production[product,month] WHERE
(Demand[product,month] > 0);
MPL.Intro.34D. Vigo
DATA (6)3. Database AccessDATACost[foods] = DATABASE(“cibi", “costo_unit");
Carica nel vettore cost il contenuto della colonna costo_unit della cartella cibi del database corrente.
18Linguaggio MPL
MPL.Intro.35D. Vigo
DATA (7)• Dati che dipendono da piu` indiciDATAA[foods,nutrients] = DATABASE("valori",
foods="IDfoods", nutrients="IDnutrients");
• Legge la colonna A nella cartella valori del database corrente e memorizza i corrispondentivalori.
• I valori non presenti nel database sono nulli.
MPL.Intro.36D. Vigo
DECISION (2)• Se alcune delle variabili decisionali sono intere
bisogna indicare ciò con la parola chiave INTEGER INTEGER VARIABLES
MultiVar[foods,nutrients];
• Nel caso in cui siano binarie si usa BINARY• Il risultato si può esportare in file, excel e dbINTEGER VARIABLES
A[i,j] EXPORT TO Sparsefile(“Sol.dat”); A[i,j] EXPORT ALL TO Sparsefile(“Sol.dat”);
ALL esporta tutte le informazioni (altrimenti solo valore e costo ridotto)
19Linguaggio MPL
MPL.Intro.37D. Vigo
FUNZIONE OBIETTIVO• Esprime la funzione lineare da ottimizzare• Deve essere preceduta dalla parola chiave MIN o
MAX (MINIMIZE o MAXIMIZE)MAX 3x1 + 5x2 ;MIN Z = SUM(foods:cost*x) + 127000;MINIMIZE Cost = SUM(foods,nutrients : Y);
Il nome (Z, Cost …) è opzionale
MPL.Intro.38D. Vigo
VINCOLI (1)• I vincoli del modello vengono definiti
immediatamente dopo la funzione obiettivo.• Preceduti dalla parola chiave SUBJECT TO• Ogni vincolo deve terminare con il carattere ;• I plain constraints sono espressi direttamente
name : X1 + X2 + X3 >= 2;
• I vector constraints sono associati ad indici.CONSTRAINT[nutrients]:
SUM(foods:A*x)>required[nutrients];
20Linguaggio MPL
MPL.Intro.39D. Vigo
VINCOLI (2)• è possibile scrivere dei vector constraints solo su
un sottoinsieme degli indici o in base a determinate condizioni.CONSTR[nutrients=1..4] : …CONSTR[foods,nutrients]
WHERE (foods > bread) : …
• è possibile esportare lo slack del vincolo, il prezzo ombra ecc. in file dati, excel e dbCONSTR[nutrients]
EXPORT TO Sparsefile(“const.dat”): …
MPL.Intro.40D. Vigo
VINCOLI (3)• Vincolo: Xj + X(j+1) + ….X(j+k) >= a
DATAk = 5;
INDEXj := 1…10;
SUBJECT TO:VINC[j]: SUM(k:x[j+k]) >= a
• Cosa succede se j+k > 10? (es.: j=7)• INDICE NON CIRCOLARE: ignora i valori inesistenti
X7 + X8 + X9 + X10 >= a• INDICE CIRCOLARE: riparte da capo
INDEXj := 1…10 CIRCULAR;
X7 + X8 + X9 + X10 + X1 + X2 >= a
21Linguaggio MPL
MPL.Intro.41D. Vigo
BOUNDS• E’ possibile indicare nel modello un lower bound
e/o un upper bound per ogni variabile.• Si utilizza la parola chiave BOUNDSBOUNDSX1 >= MinP; y_bound: 2 < Y(1,1) < 8 ;
• Default: lower bound =0 per tutte le variabili.• Il file MPL deve terminare con la parola END
MPL.Intro.42D. Vigo
Modello completo{Diet.mpl}TITLE
ExampleINDEX
nutrients := 1..8foods := (pasta, ham, cheese, egg, bread )
DATARequired[nutrients] := ( 40 ! Calories [thousands]
20 ! Protein [grams]30 ! Calcium [grams]10 ! Iron [milligrams]42 ! Avitamin [thousand ius]41 ! Thiamine (B1) [milligrams]65 ! Riboflavin (B2)[milligrams]17 ); ! Niacin [milligrams]
Cost[foods] := ( 10, 8, 15, 6, 16 );A[foods,nutrients] = DATAFILE(input.dat) ! Nuritive values
DECISIONx[foods] ! dollars of food to be purchased daily
MODELMIN z = SUM(foods: Cost*x) ;
SUBJECT TOCONSTR[nutrients] : SUM(foods: A*x) > Required[nutrients]
END
22Linguaggio MPL
MPL.Intro.43D. Vigo
Ambiente MPL
MPL.Intro.44D. Vigo
MPL su web• www.maximal-usa.com
• Download software/download• Step1: request activation code form• Step2: download the software (with http)
student version (300 constraints/variables, 100 integer)• Step3: install the software (winzip)• Step4: activating the Cplex license
• MPL user manual /mplman/mpltoc.html