Appunti sul linguaggio di programmazione AMPL Roberto Cordone, Maurizio Bruglieri, Leo Liberti 1 (maintainer) Milano, Ottobre 2001, ultima modi(cid:28)ca 030618 1DipartimentodiElettronicaeInformazione,PolitecnicoofMilano,PiazzaLeonardo daVinci 32, 20133 Milano(Si prega di segnalareerrori o puntipoco chiariall’indirizzo e-mail [email protected]). Indice 1 I generatori algebrici di modelli 1 2 Il software AMPL 4 2.1 Scrivere e risolvere un modello con AMPL . . . . . . . . . . . . 4 2.2 Il sistema di aiuto di AMPL . . . . . . . . . . . . . . . . . . . . 6 3 Il linguaggio AMPL 7 3.1 Caratteristiche generali del linguaggio . . . . . . . . . . . . . . . 7 3.2 Struttura di un programma AMPL . . . . . . . . . . . . . . . . 8 3.3 Insiemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.4 Dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.5 Variabili . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.6 Espressioni algebriche . . . . . . . . . . . . . . . . . . . . . . . . 16 3.7 Espressioni logiche . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.8 Funzione obiettivo . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.9 Vincoli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Uso di AMPL da linea di comando 22 4.1 Caricare ed eseguire modelli . . . . . . . . . . . . . . . . . . . . . 22 5 Visualizzare e analizzare la soluzione 24 5.1 Visualizzare i risultati . . . . . . . . . . . . . . . . . . . . . . . . 24 5.2 Analisi di sensitivit(cid:224) . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.2.1 Il problema del casei(cid:28)cio . . . . . . . . . . . . . . . . . . . 26 5.3 Salvare i risultati . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.4 Modi(cid:28)care un modello . . . . . . . . . . . . . . . . . . . . . . . . 31 I Questadispensasiproponedifornireunaguidainitalianoaiconcettifonda- mentali di uno dei software di modellazione piø di(cid:27)usi: AMPL. La trattazione Ł di livello elementare: leggendo queste pagine, chiunque abbia un minimo di dimestichezza con un linguaggio di programmazione dovrebbe poter imparare velocementeaformulareproblemidiottimizzazionelineareconAMPL,inmodo dapoterlitrasmettereaqualsiasirisolutoreeaccederesemplicementeairisultati. Il primo capitolo spiega la (cid:28)loso(cid:28)a sulla quale si fondano i software detti generatori algebrici di modelli. Il secondo introduce l’uso del software AMPL. Il terzo descrive la struttura e la sintassi di un modello formulato nel linguaggio AMPL. Si Ł volutamente data ai modelli una struttura piø rigida di quella e(cid:27)et- tivamenterichiestadallinguaggio,alloscopodiguidaremegliol’utenteinesperto lungo i passi necessari a tradurre un problema di ottimizzazione in un modello AMPL. Una trattazione piø approfondita del linguaggio e delle possibilit(cid:224) che o(cid:27)re si pu(cid:242) trovare in [1]. AMPL non Ł l’unico software di modellazione disponibile: altri software e linguaggi svolgono la stessa funzione. Essi hanno caratteristiche diverse, e so- prattuttoognunohaunasintassipropria,malastrutturageneralediunmodello scrittoneidiversilinguaggitendeadesseresemprelastessa. DituttiŁingenere disponibile in rete una versione per studenti, capace di gestire problemi con un numero limitato di variabili e di vincoli: • GAMS (General Algebraic Modeling System) al sito http://www.gams.com • MPL (Mathematical Programming Language) al sito http://www.maximal-usa.com/mpl/ • LINGO al sito http://www.lindo.com Quella del software AMPL si scarica dal sito http://www.ampl.com. La dis- pensa fa riferimento all’interfaccia gra(cid:28)ca del software, che la casa produttrice non fornisce piø ed Ł quindi disponibile solo a chi possieda il manuale delle versioni precedenti. Sono per(cid:242) indicate nello stesso sito diverse interfacce real- izzate da utenti, che le o(cid:27)rono gratuitamente. Ovviamente, quanto si riferisce alla struttura dei modelli e alla sintassi AMPL mantiene tutta la sua validit(cid:224). II Capitolo 1 I generatori algebrici di modelli Fra gli anni ’50 e gli anni ’70, la programmazione matematica comp(cid:236) progressi sostanziali, cui, tuttavia, non corrispose un’applicazione altrettanto di(cid:27)usa a problemi reali. Un forte ostacolo fu la di(cid:30)colt(cid:224) pratica di stendere i modelli, raccogliereeorganizzareidati, programmareglialgoritmirisolutivieanalizzare i risultati ottenuti. Risoluzione Modello Soluzione Algoritmo Problema Strategia Figura 1.1: Schema dell’approccio modellistico per passare da un problema concreto a una strategia operativa L’approccio modellistico, infatti, ha indubbi vantaggi, ma in esso, come ri- cordalaFigura1.1,ilpassaggiodalproblemaallastrategiarisolutivaŁtutt’altro cheimmediato: sitrattadiformulareprimaunmodello,poidirisolverlo,ein(cid:28)ne di tradurre la soluzione in azioni concrete. Il passaggio dal problema al modello e quello dalla soluzione alla strategia operativa non sono banali, e richiedono anzi la dose maggiore di creativit(cid:224). Anche il passaggio intermedio, per(cid:242), (quello dal modello alla soluzione) Ł solo apparentemente astratto e matematico. Infat- ti, se si fa uso (come in genere avviene) di uno strumento informatico, questo passaggio non si riduce all’applicazione di un algoritmo, ma comprende (vedi 1 Figura 1.2): 1. la traduzione del modello (pensato, o scritto in linguaggio matematico) e dei dati (disponibili su carta, o in un database informatico) in strutture dati accessibili a un risolutore 2. la realizzazione di un risolutore, che trasformi i dati in una soluzione opportunamente codi(cid:28)cata 3. la traduzione della soluzione in un formato accessibile all’utente (tabelle, gra(cid:28)ci o altro) Modello matematico Risoluzione Tabelle, grafici Dati (database) Modellatore Stampa Modello Soluzione Risolutore Strutture Strutture dati dati Modellazione Interpretazione Problema Strategia Figura 1.2: Dettaglio della fase di risoluzione nell’approccio modellistico Grandi successi in campo matematico e un’enorme potenza di calcolo pos- sono dar luogo a risolutori molto potenti, ma questi sono poco utili a livello applicativo se l’utente non dispone di un’interfaccia comoda verso il risolutore, ovvero di un software che gestisca modelli e dati appartenenti al modo reale e interroghi il risolutore. I generatori algebrici di modelli, fra cui AMPL, costitu- iscono quest’interfaccia, cioŁ si occupano del primo e del terzo passo, lasciando il secondo al risolutore. Le caratteristiche principali dei generatori algebrici di modelli sono: • fornire un linguaggio semplice per descrivere modelli complessi, un lin- guaggio che sia contemporaneamente (cid:21) ad alto livello, cioŁ comprensibile a un essere umano (cid:21) formalmente strutturato, cioŁ accessibile a un risolutore • permettereall’utentedicomunicareconilrisolutoreattraverso(cid:28)leditesto anzichØ attraverso strutture dati, in modo da non richiedergli conoscenze informatiche approfondite e da poter formulare il modello con un semplice editor, qualunque sia la piattaforma su cui viene scritto e quella su cui viene risolto 2 • permettere all’utente di comunicare con diversi risolutori, in modo da poter sfruttare i piø potenti sul mercato, ovvero quelli disponibili • tenere distinti la struttura logica del modello (variabili di decisioni, obiet- tivi, vincoli e le loro relazioni) dal valore dei dati numerici Si pu(cid:242) descrivere questa situazione come segue: utente ↔ modello ↔ programma ↔ solutore (es.AMPL) (es.CPLEX) ↑ dati ↑ database Utilizzandoungeneratoredimodellil’utentenonsioccupapiødirettamente diinterrogareilrisolutore,mapu(cid:242)concentrarsisullastesuradelmodello,usando un linguaggio di alto livello che gli rende piø semplice descrivere problemi reali anche molto complessi. Pu(cid:242) a(cid:30)dare la gestione dei dati a un database esterno cuiaccederequandonecessario. Pu(cid:242)sostituireilrisolutoresenzadoverriscrivere il modello. In(cid:28)ne la separazione tra la struttura logica e i dati evita che piccole modi(cid:28)che nella struttura del modello o nei dati comportino di riscrivere tutto: diventa infatti semplice usare lo stesso modello su dati di(cid:27)erenti o applicare modelli diversi allo stesso problema. 3 Capitolo 2 Il software AMPL IlsoftwareAMPLŁingradoditradurremodellidiProgrammazioneMatematica scrittinellinguaggioAMPLinunformatocomprensibileaungenericorisolutore di programmazione matematica. 2.1 Installazione di AMPL sotto Windows ¨ necessario scaricare da internet i seguenti (cid:28)les: • http://www.ampl.com/GUI/amplvb.zip • http://netlib.bell-labs.com/netlib/ampl/student/mswin/cplex.zip • http://www.ampl.com/NEW/TABLES/amplcml.zip Decomprimere amplvb.zip con WinZip e lanciare il programma di installazione setup.exe. Quando l’installazione avr(cid:224) termine, selezionare la voce (cid:16)Trova(cid:17) dal menu Avvio e successivamente (cid:16)File o cartelle(cid:17). Cercare il (cid:28)le ampl.exe sul drive dove AMPL Ł stato installato, e individuarne la cartella di instal- lazione (la scelta di default Ł la cartella AMPLWIN sotto la cartella Programmi nel drive C:). Decomprimere ora i (cid:28)les in cplex.zip e spostarli manualmente nella cartella di installazione di AMPL. Lanciando il (cid:28)le eseguibileAmplwin.exe situ- ato nella cartella di installazione di AMPL, dovrebbe partire l’ambiente gra(cid:28)co sperimentale (per ora piuttosto scarno) di AMPL, come mostrato in (cid:28)g (??). Ilterzo(cid:28)lescaricato,amplcml.zip,contieneunaversionealineadicomando (per Windows) di AMPL, che Ł ridondante rispetto alla versione con interfaccia gra(cid:28)ca,macherisultatuttaviautileperlacartellaMODELScontenentegliesempi. Si decomprima dunque amplcml.zip speci(cid:28)cando a WinZip di estrarre anche le cartelle. AMPLŁdisponibileperdiversisistemioperativi,Linuxincluso. Leistruzioni per lo scaricamento e l’installazione di AMPL sotto Linux Ł disponibile sul sito www.ampl.org. 4 Figura 2.1: L’ambiente gra(cid:28)co di AMPL sotto Windows. 5 2.2 Scrivere e risolvere un modello con AMPL Questasezioneinsegnaacaricareunmodellogi(cid:224)formulato,passarloaunrisolu- tore e accedere ai risultati. In genere, i generatori algebrici di modelli vengono distribuiti con esempi didattici, con i quali ci si pu(cid:242) impratichire sull’uso del software. Il procedimento consiste di sette semplici passi: • avviare AMPL • caricare il (cid:28)le del modello • caricare il (cid:28)le dei dati • speci(cid:28)care il solutore esterno (es. CPLEX, MINOS, etc.) • risolvere il modello • vedere la soluzione Avviare AMPL Selezionare la voce (cid:16)AMPLWin(cid:17) dal menu (cid:16)Programmi(cid:17) del menu di Avvio. La (cid:28)nestra principale di AMPL, come mostrato in (cid:28)g. ??, consiste di una barra dei menu, una barra dei pulsanti, un campo denominato (cid:16)ampl:(cid:17) per il comando da inserire, una (cid:28)nestra Transcript che mostra l’output di AMPL, una (cid:28)nestra Model e una (cid:28)nestra Data (vuote all’avvio di AMPL). La (cid:28)nestra Model mostra il (cid:28)le modello caricato, e la (cid:28)nestra Data mostra il (cid:28)le di dati caricato. Caricare il (cid:28)le del modello Il secondo passo Ł caricare il (cid:28)le del modello. La cartella (directory) MODELS citata sopra contiene diversi modelli di esempio. Sitrattadisemplici(cid:28)leditesto, chehannoobbligatoriamentel’estensione.mod. Nel seguito, faremo riferimento al (cid:28)le diet.mod. Per raggiungerlo: 1. premere il pulsante Model sulla barra dei pulsanti della (cid:28)nestra di AMPL (questo apre una (cid:28)nestra di selezione (cid:28)les); 2. raggiungere la cartella MODELS; 3. selezionare il (cid:28)le diet.mod e fare un doppio click su di esso. Caricare il (cid:28)le dei dati Per caricare il (cid:28)le dei dati, procediamo come per il modello: premendo il pulsante Data, cercando nella cartella MODELS il (cid:28)le diet.dat e aprendolo con un doppio click. Speci(cid:28)care il solutore esterno AMPL permette di risolvere problemi di programmazione matematica usando diversi risolutori. Con la procedura di installazione descritta sopra sono disponibili due solutori: CPLEX (per la pro- grammazione lineare e intera), e MINOS (un solutore locale per la program- mazione nonlineare continua). La scelta default di AMPL Ł quella di usare MI- NOS. PoichØ questo corso concerne primariamente problemi di PL e PLI, sar(cid:224) 6 necessariospeci(cid:28)care,unavoltacaricatoilmodelloeidati,diusareCPLEX,me- diante l’istruzione (cid:16)option solver cplex;(cid:17), da inserire nel campo denominato ampl: di immissione comando corrente. Sul sito di AMPL sono disponibili parecchi solutori esterni. Ognuno deve essereinstallatomanualmentenellacartellad’installazionediAMPL,eselezion- ato mediante un’opportuno comando option solver nome_solutore ; immesso nel campo dei comandi. Risolvere il modello Una volta che si Ł speci(cid:28)cato il risolutore, per risolvere il modello basta cliccare sul pulsante Solve. La (cid:28)nestra Transcript fornisce: • una copia del (cid:28)le di modello e una del (cid:28)le di dati o eventuali errori di sintassi in uno dei (cid:28)les; • informazioni sullo status di AMPL e qualche statistica sul problema; • informazionisullostatusdelsolutoreesterno(CPLEXsegnalalasoluzione ottima con la stringa (cid:16)optimal solution(cid:17)). Visualizzare la soluzione Per accedere alla soluzione si usa il comando display nome_variabile ; immesso nel campo dei comandi. Il solutore CPLEX stampa automaticamente il valore della funzione obiettivo. Esistono comandi per mostrare diversi dettagli relativi alla soluzione, inclusi i valori delle variabili di slack, i prezzi ombra e cos(cid:236) via. 7