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