La libreria SSC è un versatile strumento progettato per risolvere problemi di Programmazione Lineare (LP) e Programmazione Lineare Misto Intera (MILP). Questa libreria consente di definire e risolvere problemi di ottimizzazione tramite diverse e intuitive sintassi, permettendo agli utenti di modellare vincoli e funzioni obiettivo in modo efficiente. Questa libreria può essere utilizzata per applicazioni in ricerca operativa, economia, ingegneria e gestione; inoltre risulta essere facilmente integrabile in progetti Java tramite Maven e Gradle.
Per utilizzare la libreria SSC è necessario soddisfare i seguenti requisiti:
Per integrare la libreria SSC in un progetto Maven, aggiungi la seguente dipendenza al file pom.xml
:
<!-- https://mvnrepository.com/artifact/org.ssclab/SSC-LP -->
<dependency>
<groupId>org.ssclab</groupId>
<artifactId>SSC-LP</artifactId>
<version>4.6.2</version>
</dependency>
Puoi trovare esempi relativi alla gestione delle dipendenze di questa libreria con diversi gestori, sul repository maven al link "https://mvnrepository.com/artifact/org.ssclab/SSC-LP"
Per integrare la libreria SSC in un progetto Gradle,
aggiungi la seguente dipendenza al file build.gradle
:
// https://mvnrepository.com/artifact/org.ssclab/SSC-LP
implementation group: 'org.ssclab', name: 'SSC-LP', version: '4.6.2'
Per utilizzare la libreria SSC nel tuo progetto Java, puoi scaricarla manualmente e includerla nel tuo classpath. Ecco come procedere:
A. Scarica il File JARFiles
della tabella presente nella pagina, seleziona il link dove vi è scritto jar
.
4.6.2
, il link sarà simile a
https://repo1.maven.org/maven2/org/ssclab/SSC-LP/4.6.2/SSC-LP-4.6.2.jar.
File
> Project Structure
(Struttura del Progetto).Modules
(Moduli) e poi il modulo in cui desideri aggiungere la libreria.Dependencies
(Dipendenze) e clicca su +
per aggiungere una nuova dipendenza.JARs or directories
e naviga al file jar scaricato. Clicca su OK
per aggiungerlo.Apply
e poi OK
per confermare.Properties
(Proprietà).Java Build Path
(Percorso di Costruzione Java) e seleziona la scheda Libraries
(Librerie).Add External JARs...
e naviga al file jar scaricato. Clicca su Open
per aggiungerlo.Apply and Close
per confermare.lib
del tuo progetto (se non esiste, puoi crearla). Copia il tuo Programma Esempio.java
avente package com.example
nella cartella src
del tuo progettojavac
e java
con l'opzione -cp
per specificare il classpath (esempi di comandi in ambiente windows):
C:\java\jdk-10_0_1\bin\javac -cp ".\lib\SSC-LP-4.6.2.jar" src\com\example\Esempio.java
C:\java\jdk-10_0_1\bin\java -cp ".\lib\SSC-LP-4.6.2.jar;.\src" com.example.Esempio
La libreria SSC durante l'esecuzione dell'algoritmo per la risoluzione di problemi di programmazione lineare, utilizza il file system creando directory temporanee. La libreria utilizza un meccanismo flessibile per determinare e configurare la directory di lavoro predefinita, adottando un approccio a cascata per garantire una configurazione robusta e adattabile. Durante l'inizializzazione, la libreria tenta di allocare la directory di lavoro seguendo i seguenti passaggi in ordine di priorità:
Context.getConfig().setPathWorkArea("C:\\path_work_area");
Dove "C:\\path_work_area" deve essere sostituito con il percorso che l'utente sceglie per posizionare le directory temporanee di lavoro di SSC.
Questa flessibilità consente agli utenti di personalizzare il comportamento della libreria per adattarlo a scenari specifici, ad esempio
in ambienti con restrizioni di accesso o in cui è necessario un percorso predefinito per i file di lavoro.
3.1 Panoramica sulla Programmazione Lineare (LP)
La Programmazione Lineare (la sigla LP sta per Linear Programming) è una tecnica matematica utilizzata per risolvere problemi di ottimizzazione in cui si desidera
massimizzare o minimizzare una funzione obiettivo lineare, soggetta a vincoli lineari espressi attraverso equazioni o disequazioni.
Questa metodologia è ampiamente utilizzata in diversi settori, come l'economia, la logistica, l'ingegneria e le scienze gestionali,
per prendere decisioni ottimali in situazioni complesse.
Nella LP, la funzione obiettivo rappresenta il valore da ottimizzare, che può essere il profitto, il costo, o altre misure di interesse.
I vincoli rappresentano le limitazioni o restrizioni del problema, come le risorse disponibili, i requisiti di produzione, o altre condizioni
operative. Questi vincoli sono formulati come espressioni lineari delle variabili decisionali.
La soluzione di un problema di LP consiste nel trovare i valori delle variabili decisionali che ottimizzano la funzione obiettivo
rispettando tutti i vincoli imposti. La soluzione può essere trovata graficamente (nel caso di due variabili) o mediante algoritmi
numerici, come il metodo del simplesso, che è uno dei più noti ed efficienti per risolvere problemi di PL su larga scala.
La LP è una base fondamentale per altre tecniche di ottimizzazione, come la Programmazione Lineare Intera (ILP) e
la Programmazione Lineare Mista Intera (MILP), che estendono i concetti della PL per includere variabili intere e vincoli più complessi.
3.2 Definizione di un Problema LP
Un problema di Programmazione Lineare (LP) mira a ottimizzare una funzione obiettivo lineare, rispettando un insieme di vincoli lineari.
Le variabili decisionali rappresentano le scelte da compiere, e la soluzione ottimale si ottiene applicando metodi come il simplesso,
che garantiscono efficienza nella risoluzione di problemi con queste caratteristiche.
Un esempio di formulazione matematica di un problema LP è:
min 3Y + 2X2 - 4X3 + 7X4 + 8X5
5Y + 2X2 3X4 ≥ 9
3Y + X2 + X3 + 5X5 = 12
6Y + 3X2 + 4X3 5X4 ≤ 24
con Y, X2, X3, X4, X5 ≥ 0
La funzione obiettivo è l'espressione da minimizzare o massimizzare, e deve essere una combinazione lineare delle variabili decisionali,
nel nostro caso è 3Y +2X2 -4X3 +7X4 +8X5
Le righe rimanenti risultano essere i vincoli, anch'essi lineari, che sono espressioni che limitano il valore delle variabili decisionali.
Essi possono essere in forma di disuguaglianza (minore o uguale, maggiore o uguale) o uguaglianza. Nell'esempio, abbiamo disuguaglianze
e un'uguaglianza che definiscono le restrizioni sul problema.
In genere, le variabili di un problema di PL sono non negative, come indicato dalle condizioni
Y, X2, X3, X4, X5 ≥ 0
;
questo è il comportamento predefinito per le variabili nella libreria SSC.
Tuttavia, è possibile gestire variabili che possono assumere valori negativi, rendendole libere o permettendo loro di assumere valori
negativi, a seconda delle necessità del problema specifico.
Generalizzando, un problema di programmazione lineare può essere rappresentato in modo completo attraverso l'uso di vettori e matrici,
in questo caso un generico problema di programmazione lineare può essere descritto tramite la seguente sintassi :
3.3 La Programmazione Lineare, Intera e Mista Intera in SSC
La libreria SSC offre due approcci principali per risolvere problemi di programmazione lineare: il metodo del simplesso e
l'algoritmo Branch and Bound (B&B). Il simplesso è un algoritmo iterativo che cerca la soluzione ottimale muovendosi lungo i
vertici del poliedro definito dai vincoli, risultando particolarmente efficiente anche per problemi su larga scala. L'algoritmo B&B,
invece, è utilizzato per problemi di Programmazione Lineare Intera (ILP) e Programmazione Lineare Mista Intera (MILP), gestendo
variabili discrete e vincoli complessi attraverso la suddivisione dell'albero di ricerca e la valutazione di limiti inferiori e
superiori.
La classe LP della libreria è dedicata alla risoluzione di problemi di Programmazione Lineare standard (LP), dove tutte le variabili
decisionali sono continue, ovvero possono assumere valori reali all'interno di un intervallo definito. Quando invece alcune variabili
devono assumere valori interi, si passa alla Programmazione Lineare Intera (ILP) o alla Programmazione Mista Intera (MILP), gestite dalla
classe MILP. Quest'ultima è in grado di risolvere problemi che combinano variabili intere e continue,
così come problemi con variabili
semicontinue. I problemi con presenza di variabii semicontinue sono una classe speciale di problemi di ottimizzazione in cui alcune delle variabili decisionali possono assumere solo valori pari
a zero o valori all'interno di un intervallo continuo; ad esempio, sia [l, u]
un intervallo continuo delimitato
da l
e u
, allora una variabile x
può essere definita semicontinua
in un problema di PL se l ≤ x ≤ u
x = 0
, naturalmente con
0 ∉ [l, u]
Sia la classe LP che la classe MILP supportano il multithreading, permettendo un'implementazione
parallela degli algoritmi di risoluzione. Questa funzionalità consente di sfruttare più thread per migliorare le prestazioni
e offre vantaggi significativi su architetture con almeno quattro core fisici.
3.4 Special Ordered Sets (SOS)
Un Special Ordered Sets (SOS) è un insieme ordinato di variabili utilizzato nei modelli di ottimizzazione per
specificare condizioni di integralità. A differenza della ramificazione
su singole variabili, l'algoritmo ramifica su interi set di variabili, sfruttando l'ordine tra esse per migliorare l'efficienza della ricerca.
Anche se le variabili nel set possono essere continue o discrete, l'uso di un SOS trasforma il problema in uno di ottimizzazione discreta,
richiedendo l'uso di un risolutore di programmazione mista intera come il B&B. Il principale vantaggio è un'accelerazione nella
procedura di ricerca. Gli SOS possono essere risolti in SSC attraverso l'utilizzo della classe MILP.
Esitono due tipi di SOS:
• SOS1: si tratta di un insieme di variabili in cui al massimo una di esse può assumere un valore diverso da zero,
mentre tutte le altre devono essere pari a zero. Questo tipo di insieme è comunemente utilizzato quando le variabili sono di tipo 0-1,
ovvero quando dobbiamo selezionare al massimo un'opzione tra più possibilità, ma possono anche essere intere o continue.
Un esempio tipico è la scelta di uno tra diversi investimenti, si può scegliere solo una o nessuna tra le opzioni disponibili.
• SOS2: in questo caso si tratta di un insieme di variabili di cui al massimo due possono essere diverse da zero e,
se lo sono, devono essere consecutive nel loro ordinamento. Gli SOS2 sono spesso utilizzati per rappresentare funzioni non lineari
all'interno di un modello lineare. Sono un'estensione naturale del Separable Programming, ma integrati in un algoritmo Branch and Bound,
permettono di ottenere soluzioni ottimali.
Oltre ai due tipi specificati, in SSC vengono implementati altri due tipi di SOS in presenza di variabili binarie:
• F-SOS1-B: (Forced SOS1-Binary), per indicare gli Special Ordered Sets di tipo 1 binari con la condizione
di forzare la valorizzazione di una variabile. In questo caso il vincolo non è quello che solo una variabile può
essere diversa da zero, ma quello che una variabile tra quelle costituenti il Set deve essere diversa da zero.
• F-SOS2-B: (Forced SOS2-Binary), per indicare gli Special Ordered Sets binari di tipo 2 con la stessa caratteristica,
ovvero che due variabili consecutive tra quelle costituenti il Set devono essere diversa da zero.
3.5 Algortimo del Simplesso
Il metodo del simplesso è un algoritmo iterativo utilizzato per risolvere problemi di Programmazione Lineare.
L'algoritmo inizia con una soluzione base iniziale, che è generalmente una soluzione ammissibile dei vincoli.
Attraverso una serie di passi, il metodo sposta la soluzione lungo i vertici del poliedro definito dai vincoli,
migliorando continuamente il valore della funzione obiettivo fino a raggiungere un punto in cui non è più possibile
ottenere un miglioramento.
Il procedimento generale include la scelta della variabile da entrare nella base e quella da uscire, sulla base di un criterio di ottimalità.
La complessità computazionale del metodo è nel caso peggiore esponenziale,
ma in generale possiamo dire che ha un comportamento
medio polinomiale nel numero di variabili e vincoli: nella pratica, l'algoritmo si comporta molto bene per la maggior parte dei problemi reali.
Il metodo del simplesso può essere implementato attraverso il metodo delle due fasi quando non si dispone di una soluzione base
ammissibile iniziale. In questa procedura, si introducono delle variabili artificiali per trovare una soluzione iniziale ammissibile,
che poi viene migliorata nel secondo stadio.
Le soluzioni restituite possono essere di diversi tipi: una soluzione ottima che soddisfa tutti i vincoli e ottimizza la funzione obiettivo,
una soluzione illimitata se la funzione obiettivo può crescere indefinitamente senza violare i vincoli, o una soluzione vuota
(o infeasibile) se non esiste alcuna soluzione che soddisfi tutti i vincoli.
3.6 Algortimo del Branch and Bound (B&B)
Il metodo del Branch and Bound (B&B) è un algoritmo utilizzato per risolvere problemi di Programmazione Lineare Intera (ILP)
e misto intera (MILP), dove tutte o alcune variabili devono assumere valori interi. Questo metodo esplora sistematicamente
un albero di decisioni, dove ogni nodo rappresenta un sottoproblema ottenuto rilassando o fissando alcune variabili intere.
L'algoritmo parte da un rilassamento lineare del problema originale, risolvendo inizialmente questo rilassamento
utilizzando il metodo del simplesso. Se la soluzione ottimale del rilassamento soddisfa i vincoli di integrità, allora
essa è una soluzione ottima per il problema originale. In caso contrario, l'algoritmo suddivide il problema in due o più
sottoproblemi (branching), ciascuno con ulteriori vincoli sulle variabili intere.
Ogni sottoproblema viene poi risolto nuovamente con il simplesso. Se un sottoproblema fornisce una soluzione ottimale intera,
viene aggiornata la soluzione migliore trovata finora. I nodi dell'albero che non possono fornire una soluzione migliore vengono
scartati (bounding). Il processo continua fino a quando tutti i sottoproblemi sono stati esplorati o eliminati.
Sebbene il B&B abbia una complessità computazionale elevata, può risolvere molti problemi
di ILP reali in tempi ragionevoli.
3.7 Dimensioni dei problemi e richiesta di memoria
Il metodo del simplesso è un algoritmo efficiente per risolvere problemi di programmazione lineare continui
(cioè senza variabili intere), consentendo di affrontare problemi con un gran numero di variabili e vincoli.
Quando si utilizza SSC per eseguire il simplesso, i limiti operativi sono legati principalmente alla quantità di
memoria disponibile per la JVM. Ad esempio, specificando un massimo di 4 gigabyte di memoria con l'opzione -Xmx4g
,
è possibile risolvere problemi che coinvolgono migliaia di variabili e vincoli.
Per quanto riguarda il metodo Branch and Bound, la complessità è significativamente maggiore, poiché prevede la risoluzione
di una serie di problemi tramite il simplesso. Ciò comporta un costo computazionale più elevato sia in termini di tempo che
di risorse, rendendo i problemi di Programmazione Lineare Mista Intera (MILP) molto più limitati in termini di dimensioni
rispetto ai problemi di LP puri.
3.8 Scalabilità e Stabilità numerica
Durante la risoluzione di problemi di programmazione lineare, la precisione dei calcoli può essere compromessa quando si
operano valori molto grandi o molto piccoli insieme. Questo effetto, noto come instabilità numerica, può derivare da errori
di arrotondamento o dall'accumulo di piccoli errori nei calcoli iterativi, come quelli dell'algoritmo del Simplesso.
Per migliorare sia la stabilità numerica che le prestazioni, è fondamentale ridimensionare opportunamente i dati di input,
mantenendo i coefficienti dei vincoli e della funzione obiettivo in intervalli simili, ancor meglio se idealmente vicino a 1.
Ad esempio un vincolo :
10000X1 + 20000X2 <= 60000
È opportuno ridimensionarlo in un vincolo come :
X1 + 2X2 <= 6
Un metodo consigliato consiste nell'utilizzare unità di misura adeguate come migliaia di euro invece di euro se gli ammontari sono molto grandi, tonnellate al posto dei chili se i pesi sono rilevanti, etc. Un modello ben scalato minimizza l'impatto di questi errori e migliora l'efficacia dell'algoritmo nella selezione degli elementi pivot, portando a soluzioni più stabili e rapide.
4.1 Formulazione del problema
In SSC per formulare un problema LP (o MILP) può essere utilizzato uno tra i diversi formati a disposizione.
I formati utilizzabili risultano essere rispettimamente i seguenti :
Indipendentemente dal tipo di formato utilizzato per modellare il problema, i risultati dell'elaborazione sono ottenibili utilizzando le stesse interfaccie. Per cui indipendentemente dal formato utilizzato il modo per recuperare i risultati risulta sempre lo stesso.
4.1.1 Formato testo
Consideriamo la seguente formulazione matematica di un problema di Programmazione Lineare :
funzione obiettivo:
min 3X1 + X2 - 4X3 + 7X4 + 8X5
vincoli:
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
limiti delle variabili:
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
condizioni :
X5 ≥ 0
X2, X3 ∈ ℤ
Per rappresentare questo problema di Programmazione Lineare affinché sia elaborabile dalla libreria SSC si può utilizzare il formato testo (o testuale). In questo formato occorre fornire alla libreria il problema sotto forma di una stringa strutturata, che verrà successivamente parserizzata dalla libreria stessa. Questa stringa deve seguire una sintassi specifica che per l'esempio matematico appena descritto risulta essere :
public class Esempio {
public static void main(String[] args) throws Exception {
String lp_problem =
" min: 3x1 +X2 -4x3 +7x4 +8X5 \n"+
" 5x1 +2x2 +3X4 >= 9 \n"+
" 3x1 + X2 +X3 +5X5 = 12.5 \n"+
" 6X1+3.1x2 +4X3 +5X4 <= 24 \n"+
" x1 >= -1 \n"+
"-1 <= x2 <= 6 \n"+
" x3 <= -2 \n"+
" . <= x4 <= . \n"+
" int x2, X3 ";
}
}
Il codice sopra descritto vuole mettere in evidenza, in questa parte iniziale della guida, solo
il formato di rappresentazione di un problema di LP, di conseguenza non risulta completo. L'esempio completo
è riportato nella pagina Esempi
(esempio 3.1) di questo sito.
Dall'esempio risulta evidente che il problema è fomulabile attraverso una unica stringa chiamata
"lp_problem" (ma può avere qualsiasi altro nome). In questo formato la funzione obiettivo e ciascun vincolo
devono essere scritti su righi differenti (occorre inserire al termine di ogni espressione
compiuta il carattere '\n' di nuova linea). Ovviamente, se si usano i Text Blocks di java 15 ("""), i new line '\n' sono superflui se le singole istruzioni si trovano già
su righi differenti. In definitiva, la stringa "lp_problem" contiene tutti gli elementi necessari per formulare il problema matematico sopra riportato:
Variabili: Nel formato testo le variabili possono avere qualsiasi nome (devono però iniziare con un carattere alfabetico
seguito da caratteri alfanumerici) e risultano non essere case-sensitive (ovvero le variabili indicate con "x3" e "X3"
rappresentano la stessa variabile).
Non è necessario elencare le variabili in un ordine specifico all'interno della funzione obiettivo o dei vincoli.
Le variabili possono apparire in qualsiasi ordine, ad esempio "3x1 + X2"
è equivalente a "X2 + 3x1"
.
Tra una variabile ed il suo coefficiente non deve essere mai presente uno spazio, mentre in tutti gli altri casi è
possibile inserirne uno o più Ad esempio, "3x1+X2"
è equivalente a "3x1 + X2"
.
Inoltre, se una variabile appare più volte all'interno della stessa espressione, sia nella funzione obiettivo che nei vincoli,
i coefficienti associati a quella variabile verranno sommati automaticamente. Per esempio, le espressioni
"4Y + 2X2 + Y >= 9"
e "3Y +X2 >= 9 - X2 -2Y"
saranno interpretate entrambe come "5Y + 2X2 >= 9"
.
Questo avviene sia per garantire più flessibilità che per evitare errori di ridondanza nella definizione delle variabili.
Le variabili e i vincoli non devono essere allineati verticalmente o orizzontalmente. Le espressioni possono essere scritte
in modo disallineato, senza la necessità di formattare il testo per allineare i termini.
Questo permette di scrivere le espressioni in maniera più libera e meno vincolata dalla formattazione.
Ricordiamo infine che le variabili risultano essere,
di default, non negative (>=0);
Coeficienti delle variabili: Nel formato testo i coefficienti delle variabili possono essere semplici numeri sia interi che decimali, naturalmente ha senzo mettere la parte frazionaria solo se questa è presente. Nell'esempio sopra riportato, il vincolo :
6X1 +3.1x2 +4X3 +5X4 <= 24
ha la variabile X2
che ha per coefficiente 3.1
che ha una parte frazionaria. Occorre ricordare che
il coefficiente della prima variabile presente a partire dalla sinistra di un vincolo o il numero presente dopo il segno di
uguaglianza o disuguaglianza di un vincolo, se positivo, non necessita del segno +
, in tutti gli altri casi occorre
inserire il segno del coefficiente. Naturalmente se una variabile ha coefficiente 1
questo può essere omesso.
Funzione obiettivo: La prima riga della stringa specifica la funzione obiettivo; essa è preceduta da "min:"
o
"max:"
per indicare se si desidera minimizzare o massimizzare tale funzione. Nel nostro esempio:
min: 3x1 +X2 -4x3 +7x4 +8X5
rappresenta la funzione obiettivo da minimizzare.
Vincoli: Le righe successive specificano i vincoli del problema, che devono essere espressi come disuguaglianze (">="
, "<="
) o uguaglianze ("="
). Ogni vincolo deve essere una combinazione lineare delle variabili. Ad esempio:
5x1 +2x2 +3X4 >= 9
è un vincolo di disuguaglianza. In un vincolo le variabili possono anche essere poste sul lato destro della disuguaglianza o uguaglianza, ovvero :
5x1 +2x2 >= 9 -3X4
è sempre una formulazione valida di vincolo.
Ai vincoli del problema possono essere assegnate delle etichette o nomi. Questi nomi non devono essere necessariamente univoci per ciascun vincolo, in tal caso una singola etichetta puo essere utilizzata per più vincoli per identificarli come appartenenti ad un gruppo specifico. Dare un nome o una etichetta ha il solo scopo di identificare un vincolo o un gruppo di vincoli; difatti in fase di recupero ed interpretazione dei risultati sarà possibile identificare ciascun vincolo a partire dalla sua etichetta insieme alle altre caratteristiche. Per definire una etichetta su un vincolo, basta anteporre al vincolo stesso il nome seguito dai due punti ":", come nell'esempio seguente :
vincolo1: 5X1 +2X2 +3X4 >= 9
Le etichette dei vincoli sono singole parole (non separate da spazi) che devono iniziare con un carattere alfabetico seguito da caratteri alfanumerici (lettere e numeri).
Vincoli sulle variabili: È possibile specificare limiti inferiori e superiori per le variabili (upper bound e lower bound)
utilizzando la sintassi "l <= x <= u"
oppure "x >= l"
o "x <= u"
, dove l
rappresentano i limiti. Se non sono specificati, le variabili sono considerate non negative di default. Nell'esempio sopra riportato,
la seguente dichiarazione :
e
u
X1 >= -1
indica un lower bound sulla variabile X1
. Quando si definisce un lower bound negativo, come in questo caso, la variabile non è
più vincolata alla non negatività e può assumere valori anche inferiori a zero. È importante notare che questa
dichiarazione implica che la variabile X1
può avere qualsiasi valore maggiore o uguale a -1, inclusi valori negativi.
Tuttavia, se specifichiamo il segno della variabile sulla definizione di un upper o lower bound, come ad esempio:
+X1 >= -1
stiamo in realtà solo definendo un vincolo e non un lower bound, senza eliminare il vincolo di non negatività In altre parole,
stiamo dicendo che X1
deve essere maggiore o uguale a -1, ma, poiché la variabile è esplicitamente non
negativa per impostazione predefinita, X1
sarà limitata a valori non negativi che soddisfano la
condizione X1 >= -1
. Pertanto, la variabile non potrà mai essere minore di zero, anche
se il vincolo è fissato a -1.
Questo significa che:
• se dichiariamo X1 >= -1
, stiamo definendo un lower bound e la variabile è libera di assumere qualsiasi valore a partire da -1,
inclusi valori negativi.
• se inseriamo il segno (+/-
) e dichiariamo +X1 >= -1
, stiamo definendo un vincolo e la variabile rimane soggetta alla
condizione di non negatività e
assumerà solo valori maggiori o uguali a zero, anche se il vincolo stabilisce che deve essere maggiore di -1.
Partendo dal nostro esempio consideramo la vairabile X2
che ha un vincolo del tipo "l <= x <= u"
, ovvero :
-1 <= X2 <= 6
Questo vincolo può essere espresso in modo equivalente con la notazione inversa "u >= x >= l"
,
ovvero:
6 >= X2 >= -1
Le due notazioni sono perfettamente equivalenti e descrivono lo stesso intervallo per la variabile X2
.
Variabili libere o negative: Per poter dichiarare variabili libere, ovvero variabili senza limite inferiore (il limite inferiore
non sarà più lo zero ma -infinito),
basta specificare un lower bound indefinito. Se si dichiara un valore indefinito su un lower bound o su un upper bound,
SSC trasforma tali valori in -infinito nel primo caso ed in +infinito nel secondo. Nel formato testo il valore indefinito
si rappresenta con il punto ".". In generale
per poter impostare delle variabili libere basta valorizzare un lower bound indefinito; ad esempio nel nostro caso la
variabile X4
può assumere valori in [-∞,+∞]
tramite la dichiarazione :
. <= X4 <= .
Per poter impostare delle variabili che possono assumere valori anche in un range negativo basta valorizzare o un lower bound negativo
o un upper bound negativo. Nell'esempio sopra riportato si definisce una variabile x1
che può assumere valori in [-1,+∞]
(ovvero valori negativi maggiori di -1 e positivi)
e una variabile x3
che può assumere solo valori negativi in [-∞,-2]
con le seguenti istruzioni:
x1 >= -1
x3 <= -2
Variabili Intere: Per problemi di programmazione lineare intera mista (MILP), le variabili che devono assumere valori interi vengono
dichiarate con il prefisso "int"
. Ad esempio nel nostro esempio:
int X2, X3
specifica che X2
e X3
devono essere intere.
Variabili binarie: Per problemi di programmazione lineare con variabili binarie, le variabili che devono assumere valori in {0,1}
vengono dichiarate con il prefisso "bin"
. Per cui usando la notazione :
bin X2, X3
si specifica che X2
e X3
devono essere binarie.
Variabili semicontinue: È possibile risolvere problemi di programmazione lineare con variabili semicontinue. Ricordiamo che una
variabile semicontinua può essere o pari a zero oppure deve appartenere a un intervallo continuo delimitato;
ad esempio, sia [l, u]
un intervallo continuo delimitato da l
e u
tale che "l > 0"
,
allora una variabile x
è semicontinua
in un problema LP se "l ≤ x ≤ u"
oppure se "x = 0"
, naturalmente con 0 ∉
[l, u]
. Per definire delle variabili semicontinue, occorre far precedere le variabili interessate dal prefisso
"sec"
, ad esempio :
sec x4, X5
Naturalmente se definiamo una qualsiasi variabile X
semicontinua con il prefisso "sec"
, questa deve anche essere dichiarata
limitata tramite un vincolo del tipo :
l <= X <= u
Caratteri o parole Jolly: Se in un problema di Programmazione lineare occorre impostare che la totalità
delle variabili sia intera è possibile utilizzare la parola "ALL"
; ad esempio se, utilizzando il formato testo,
usiamo questa sintassi :
int ALL
stiamo allora dichiarando che tutte le variabili del problema sono intere. Questa sintassi può essere usata per dichiararle
tutte binarie ("bin ALL"
) o semicontinue ("sec ALL"
). Nel formato testo è possibile usare anche
il carattere jolly "*", per dichiarare che tutte le variabili che iniziano con un determinato prefisso appartengano ad una
determinata classe di variabili. Ad esempio con la notazione:
int X*
bin Y*
si dichiara che tutte le variabili che iniziano per X
sono intere, mentre quelle che iniziano per Y
sono binarie e le rimanenti reali. Ricordiamo che ciascuna dichiarazione di tipo "int", "bin", "sec"
, se usate
contemporaneamente nella stessa formulazione, vanno poste su righi distinti.
SOS (Special Ordered Set): In SSC è possibile definire gli Special Ordered Sets (SOS) che sono insiemi ordinati di
variabili con vincoli aggiuntivi sul loro comportamento, utili per problemi di ottimizzazione complessi.
La libreria supporta sia SOS di tipo 1 (SOS1) che SOS di tipo 2 (SOS2), incluse varianti binarie, intere e forzate.
Un insieme SOS1 limita il set di variabili in modo che solo una variabile possa essere diversa da zero, mentre tutte le altre
devono essere pari a zero. Ecco un esempio di istruzione da aggiungere nella formulazione del problema per dichiarare un insieme SOS1 :
sos1 X1,X2,X3
Questo dichiara che solo una tra X1, X2 e X3
può
essere diversa da zero, mentre le altre devono essere uguali a zero.
Se le variabili del set SOS1 devono essere binarie
(cioè 0 o 1), si utilizza :
sos1:bin X1,X2,X3
In questo caso, solo una tra X1, X2 e X3
puè essere uguale a 1, mentre tutte
le altre devono essere 0.
Per dichiarare che le variabili sono intere, si può usare:
sos1:int X1,X2,X3
Questo vincola le variabili X1, X2 e X3
ad assumere valori interi,
con il vincolo che solo una di queste può assumere valori diversi da zero.
Nel caso volessimo forzare in un insieme SOS1 di variabili binarie, una variabile a essere valorizzata, possiamo utilizzare la notazione:
sos1:bin:force X1,X2,X3
In questo caso, una delle variabili sarà necessariamente diversa da zero, mentre le altre saranno pari a zero.
L'opzione force
può essere usata solo su insiemi binari di variabili.
La libreria consente di usare un carattere jolly "*" per includere tutte le variabili che iniziano con un certo
prefisso ad appartenere ad un SOS di tipo 1. Ad esempio:
sos1 X*
Questo include tutte le variabili che iniziano con "X
" nel set di tipo SOS1.
Un insieme SOS2 limita il set di variabili in modo che al massimo due variabili possano essere diverse da zero e,
se entrambe sono diverse da zero, devono essere contigue nel loro ordine. L'ordine delle variabili è fondamentale:
sos2 X2,X3,X1
In questo caso, al massimo due delle variabili X2, X3 e X1
possono essere diverse da zero,
e devono essere contigue nell'ordine dichiarato, ad esempio, (X2, X3
) o
(X3, X1
).
Se vogliamo che le variabili in un SOS2 siano binarie o intere o forzate binarie, possiamo utilizzare le seguenti sintassi analoghe al SOS1:
sos2:bin X2,X3,X1
sos2:int X2,X3,X1
sos2:bin:force X2,X3,X1
A differenza di SOS1, in SOS2 non è possibile usare il carattere jolly *, poiché va esplicitamente
dichiarato l'ordine delle variabili attraverso la dichiarazione "sos2 Z,X,Y,K...
".
È possibile dichiarare più set SOS nello stesso problema di programmazione
lineare, basta scrivere le dichiarazioni su righe separate. Ad esempio, se si desidera dichiarare un set SOS1 con variabili
binarie e un altro set SOS1 binario con una variabile forzata nella valorizzazione, si può fare così:
sos1:bin X1,X2,X3
sos1:bin:force X4,X5,X6
Possiamo ora fare un esempio di utilizzo degli SOS con variabili miste. Supponiamo di voler dichiarare una serie di set SOS1 e SOS2 in un problema di programmazione lineare. Il codice potrebbe essere simile a questo:
// Dichiarazione di un set SOS1 di variabili miste
sos1 X1,X2,X3,X4,X5
int X1,X2
bin X3,X4
// Dichiarazione di un set SOS2 di variabili binarie
sos2:bin Y1,Y2,Y3
// Dichiarazione di un set SOS1 binario con variabile forzata
sos1:bin:force Z1,Z2,Z3
Esempi completi di modellazione di problemi che utilizzano il formato testuale sono riportati nella sezione Esempi
di questo sito,
dimostrando come rappresentare sia problemi di LP standard (esempi 1.1 ,
1.6 ,
1.11) che MILP
(esempi 2.7,
2.9,
2.16,
2.17,
2.18,
2.19,
3.1).
La libreria parserizza automaticamente le espressioni presenti nella stringa e le traduce in un modello matematico che può essere risolto utilizzando
algoritmi come il simplesso o il branch and bound.
4.1.2 Formato JSON
Consideriamo la seguente formulazione matematica di un problema di Programmazione Lineare :
funzione obiettivo:
min 3X1 + X2 - 4X3 + 7X4 + 8X5
vincoli:
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
limiti delle variabili:
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
condizioni :
X5 ≥ 0
X2, X3 ∈ ℤ
La libreria supporta la formulazione di problemi di Programmazione Lineare (LP) in formato JSON, che consente una rappresentazione strutturata della funzione obiettivo, dei vincoli, dei limiti sulle variabili. Ecco come è possibile rappresentare un problema con questo formato:
public class Esempio {
public static void main(String[] args) throws Exception {
//Questo esempio utilizza i Text Blocks """, presenti da java 15.
//Se si dispone di una versione di java precedente usare le stringhe standard.
String stringJson = """
{
"objective": {
"type": "min",
"coefficients": {
"X1": 3,
"X2": 1,
"X3":-4,
"X4": 7,
"X5": 8
}
},
"constraints": [
{
"coefficients": {
"X1": 5,
"X2": 2,
"X4": 3
},
"relation": "ge",
"rhs": 9,
"name":"ConstraintA"
},
{
"coefficients": {
"X1": 3,
"X2": 1,
"X3": 1,
"X5": 5
},
"relation": "eq",
"rhs": 12.5,
"name":"ConstraintB"
},
{
"coefficients": {
"X1": 6,
"X2":3.1,
"X3": 4,
"X4": 5
},
"relation": "le",
"rhs": 24,
"name":"ConstraintC"
}
],
"bounds": {
"X1": {
"lower": -1
},
"X2": {
"lower": -1,
"upper": 6
},
"X3": {
"upper": -2
},
"X4": {
"lower": null,
"upper": null
}
},
"variables": {
"x2": "integer",
"X3": "integer"
}
}""";
JsonProblem jsonProb=new JsonProblem(stringJson);
}
}
Il codice sopra descritto vuole mettere in evidenza, in questa parte iniziale della guida, solo
il formato di rappresentazione di un problema di LP, di conseguenza non risulta completo. L'esempio completo
è riportato nella pagina Esempi
(esempio 3.5) di questo sito.
Il formato JSON utilizzato è suddiviso in sezioni, ognuna delle quali è rapresentata da una chiave
JSON. Ad esempio per rappresentare la funzione obiettivo occorre definire la chiave "objective"
. Va ricordato che
tutte le chiavi ed i valori stringa devono essere riportati in minuscolo, fatto salvo i nomi delle variabili del problema di LP
ed il nome (facoltativo) da assegnare ai vincoli.
La libreria SSC utilizza una implementazione di jakarta.json
per gestire il parsing dei file JSON.
Va notato che tale implementazione non genera un errore di parsing quando trova chiavi duplicate all'interno di un oggetto JSON.
In tali casi, solo l'ultima chiave duplicata viene considerata valida, e il suo valore sovrascrive eventuali valori precedenti
associati alla stessa chiave. Questo comportamento potrebbe non essere immediatamente evidente, quindi è consigliato evitare
chiavi duplicate all'interno delle definizioni JSON per garantire risultati corretti.
Una volta rappresentato il problema, si crea un oggetto delle classe JsonProblem
, passandogli come argomento la stringa
contenente il JSON stesso (nel caso di un file JSON, si passa l'oggetto Path
relativo al percorso del file, vedi esempio
1.17).
Ma analizziamo ciascun elemento del formato JSON.
Funzione obiettivo: Nella formulazione del problema, la funzione obiettivo è
descritta tramite la sezione "objective"
. Qui puoi specificare il tipo (type
) di ottimizzazione, che può
essere "max"
o "min"
, e definire i coefficienti (coefficients
) delle variabili
da ottimizzare, come di seguito specificato:
"objective": {
"type": "min",
"coefficients": {
"X1": 3,
"X2": 1,
"x3":-4,
"X4": 7,
"X5": 8
}
}
Come possiamo notare sia i nomi delle chiavi ("objective","type", "coefficients")
che i valori "min"
vanno indicati in minuscolo. Al contrario i nomi da dare alle variabili non sono case-sensitive,
per cui "X3"
e "x3"
rappresentano la stessa variabile.
Vincoli: I vincoli sono specificati nella sezione "constraints"
, dove ogni vincolo è un elemento di un array e viene descritto
tramite i coefficienti delle variabili coinvolte, la relazione (maggiore o uguale "ge"
, minore o uguale "le"
, uguale "eq"
) e il valore del termine destro "rhs"
. Opzionalmente è possibile assegnare
un nome al vincolo tramite la proprietà "name"
. Di seguito una rappresenttazione di un vincolo del problema sopra specificato:
"constraints": [
{
"coefficients": {
"Y" : 5,
"X2": 2,
"X4": 3
},
"relation": "ge",
"rhs": 9,
"name": "VINCOLO1"
},
...
...
]
Limiti delle variabili: I limiti sulle variabili sono definiti nella sezione "bounds"
.
Se non specificati (ovvero se mancano tali sezioni), le variabili sono considerate non negative di default.
Puoi specificare i limiti inferiori e superiori per ciascuna variabile, indicando null
se ci sono limiti infiniti
inferiori o superiori:
"bounds": {
"X1": {
"lower": -1
},
"X2": {
"lower":-1,
"upper": 6
},
"X3": {
"upper": -2
},
"X4": {
"lower": null,
"upper": null
}
}
Il codice JSON sopra riportato sta ad indicare :
1) che la variabile X1
può assumere valori in [-1,+∞].
2) che la variabile X2
può assumere valori in [-1,6]
,
ovvero una variabile che può assumere valori negativi maggiori di -1 o positivi minori di 6.
3) che la variabile X3
può assumere solo valori negativi in [-∞,-2]
.
4) che la variabile X4
può assumere valori [-∞,+∞]
o libera.
5) che la variabile X5
, non essendo stata modificata nei limiti, può assumere valori in [0,+∞]
.
Naturalmente specificare un upper bound infinito (con l'istruzione "upper": null
) è in realtà
superfluo dato che le variabili, essendo per default non negative, hanno gia tale limite. Abbiamo inserito questo esempio per specificare
quali valori possono essere assegnati alle proprietà "upper"
e "lower"
ed il loro significato.
Variabili libere o negative: Per poter dichiarare variabili libere, ovvero variabili senza limite inferiore
(il limite inferiore non sarà più lo zero ma -infinito), basta specificare un lower bound indefinito.
Se si dichiara un valore indefinito sulle proprietà "lower"
o "upper"
, SSC trasforma
tali valori in -infinito nel primo caso ed in +infinito nel secondo. Nel formato JSON il valore indefinito si rappresenta
con il null
.
In generale per poter impostare delle variabili che possono assumere valori anche in un range negativo,
basta valorizzare un lower bound indefinito (come sulla X4
) o negativo (come sulla X1
),
oppure un upper bound negativo (come sulla X3
).
Tipologia delle variabili: Per problemi di Programmazione Lineare Intera Mista (MILP), è possibile dichiarare quali variabili
devono assumere valori interi, binari o semicontinui.
La natura delle variabili (ad esempio, se sono continue, intere, binarie) può essere definita nella sezione "variables"
.
In questo esempio, le variabili X2
e X3
sono dichiarate intere:
"variables": {
"x2": "integer",
"X3": "integer"
}
A seconda che siano intere, binarie, semicontinue o semicontinue intere, si utilizzano rispettivamente
i valori "integer","binary" ,"semicont"
e "integer-semicont"
.
Ricordiamo che il JSON è un formato che richiede chiavi univoce sugli oggetti in esso definiti,
per cui se una variabile è intera e semicontinua, non usate sulla stessa variabile i valori "integer"
e
"semicont"
duplicando la chiave relativa al nome di qualche variabile per assegnarli tali valori,
ma usate il valore predisposto, ovvero "integer-semicont"
.
4.1.3 Formato a coefficienti
Consideriamo la seguente formulazione matematica di un problema di Programmazione Lineare :
funzione obiettivo:
min 3X1 + X2 - 4X3 + 7X4 + 8X5
vincoli:
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
limiti delle variabili:
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
condizioni :
X5 ≥ 0
X2, X3 ∈ ℤ
Per rappresentare questo problema di Programmazione Lineare affinché sia elaborabile dalla libreria SSC si può utilizzare
il formato a coefficienti. In questo formato si definiscono dei dati strutturati dove ciascun rigo (record) rappresenta o la funzione
obiettivo, o un vincolo, o la definizione di caratteristiche per le variabili.
Per separare le diverse espressioni, queste devono appunto trovarsi su righi differenti; per questo motivo alla fine di ogni espressione
è presente il catattere "\n" di nuova linea.
In questo formato le colonne rappresentano i coefficienti delle variabili, le relazioni, i termini noti (o valori rhs).
Questi dati strutturati devono seguire una sintassi che viene definita dall'utilizzatore come nell'esempio riportato di seguito :
import org.ssclab.ref.InputString;
public class Esempio {
public static void main(String[] args) throws Exception {
String milp_coeff = " 3 1 -4 7 8 min . \n"+
" 5 2 0 3 0 ge 9 \n"+
" 3 1 1 0 5 eq 12.5 \n"+
" 6 3.1 4 5 0 le 24 \n"+
"-1 -1 . . 0 lower . \n"+
" . 6 -2 . . upper . \n"+
" 0 1 1 0 0 integer . " ;
InputString milp_input = new InputString(milp_coeff);
milp_input.setInputFormat("X1:double,X2:double,X3:double,X4:double,X5:double, TYPE:varstring(8), RHS:double");
}
}
Il codice sopra descritto vuole mettere in evidenza, in questa parte iniziale della guida, solo
il formato di rappresentazione di un problema di LP, di conseguenza non risulta completo. L'esempio completo
è riportato nella pagina Esempi
(esempio 3.2) di questo sito.
Come accennato, una colonna può rappresentare i coefficienti che una specifica variabile assume sui diversi vincoli
e sulla funzione obiettivo. Nell'esempio sopra riportato, ad esempio, la prima colonna rappresenta tutti i coefficienti
che la variabile X1
assume sulle diverse espressioni del problema. Ma come si indica al risolutore SSC,
ad esempio, che la prima colonna è relativa alla variabile X1
?
Per definire cosa rappresenta ogni colonna occorre specificare il formato di input (o tracciato record). Per formato di input
intendiamo una dichiarazione che descrive come vanno lette ed interpretate le colonne presenti nella struttura dati nella quale
si è formulato il problema. La definizione del formato di input si effettua attraverso queste due istruzioni :
InputString milp_input = new InputString(milp_coeff);
milp_input.setInputFormat("X1:double,X2:double,X3:double,X4:double,X5:double, TYPE:varstring(8), RHS:double");
La stringa che contiene la formulazione del problema (milp_coeff)
viene passata al costruttore della classe InputString
per creare una istanza di questa classe; su tale istanza è possibile invocare il metodo setInputFormat()
.
Ebbene, la definizione del formato di input si effettua attraverso una stringa da passare come argomento al metodo setInputFormat()
;
in questa stringa si susseguono, separate da virgola, le notazioni "nome variabile:tipologia variabile"
per definire,
in sequenza, i nomi delle variabili da associare alla colonne ed il tipo di dato presente nelle colonne.
Sebbene si parli di 'colonne', ciò serve solo a semplificare la comprensione: il primo dato di ogni riga presente
nella stringa milp_coeff
viene associato alla
prima variabile dichiarata, il secondo dato alla seconda variabile dichiarata, e così via. Non è necessario che i
coefficienti siano allineati rigorosamente in verticale (ovvero che si trovino tutti sul k-esimo carattere di ciascun rigo);
l'importante è che siano separati da almeno uno spazio e che seguano la sequenza corretta. Il termine 'colonna' è
stato introdotto solo per identificare in modo concettuale i coefficienti di una variabile sui vari vincoli e sulla funzione obiettivo
o i termini noti.
Riprendendo il nostro esempio abbiamo che i valori delle prime 5 colonne relative alle variabili del problema di LP
vengono memorizzate nelle variabili X1, X2, X3, X4, X5
di tipo numerico double;
i valori della colonna delle relazioni vengono memorizzati in una variabile chiamata TYPE
(di tipo stringa e con lunghezza
di 8 caratteri); i valori della colonna dei termini noti vengono memorizzati nella variabile RHS
di tipo double.
I nomi da assegnare alle
variabili del problema di LP sono scelti dall'analista (devono però iniziare con un carattere alfabetico seguito da caratteri alfanumerici),
mentre la colonna delle relazioni e quella dei termini noti devono necessariamente essere memorizzate in variabili chiamate TYPE
e RHS
.
Di norma possiamo chiamare le variabili anche con nomi non necessariamente seguiti da un numero, ad esempio:
"PRICE:double, AMOUNT:double, WEIGHT:double"
, etc, etc. Di solito è preferibile dichiarare le n
variabili
di un problema con una diversa notazione, chiamata ad intervalli, che risulta particolarmente utile se le variabili del
problema sono decine o centinaia. In questo caso la dichiarazione "X1:double, X2:double, X3:double, .... , Xn:double"
di n
variabili, può essere sostituita con la notazione "X1-Xn:double"
.
Consideriamo un esempio teorico: supponiamo di avere un problema con 7 variabili che desideriamo suddividere in due gruppi;
in questo caso, possiamo utilizzare due distinti prefissi, ad esempio "PRICE1-PRICE3:double,COST1-COST4:double"
.
Tornando al nostro esempio ed utilizzando la notazione ad intervalli, il formato di input cambia in :
milp_input.setInputFormat("X1-X5:double, TYPE:varstring(8), RHS:double");
Questa seconda notazione, certamente più compatta, permette di dichiarare tutte le variabili comprese nell'intervallo che va da
X1
a X5
. Ricordiamo inoltre che la dichiarazione delle variabili ad intervalli non deve partire necessariamente da
1
, nel nostro caso possiamo anche scrivere "X6-X10:double"
La colonna da associare alla variabile TYPE
viene utilizzata per definire il 'tipo'
di espressione contenuta in una riga, ad esempio: vincolo o funzione obiettivo. Se il valore è "min"
oppure
"max"
, la riga verrà interpretata cone un f.o; mentre se assume uno dei valori in {"eq","le","ge"}
verrà interpretata come vincolo. La variabile TYPE
può
assumere solo i seguenti valori che possono essere scritti sia in minuscolo che in maiuscolo:
min, max, eq, le, ge, lower, upper, integer, binary, semicont
La variabile TYPE
è dichiara di tipo varstring(8)
affichè
possa contenere valori con al più 8 catatteri (difatti il valore "semicont"
è il piu lungo e conta 8 caratteri).
Infine occorre dichiarare la variabile RHS
che contiene i termini noti. Ricordiamo ancora che
nella definizione del formato di input è obbligatorio dichiarare una variabile TYPE
e una variabile RHS
da associare ai relativi valori presenti nella formulazione del problema.
Analizziamo ora le diverse espressioni (righi) attraverso le quali si formula un problema di Programmazione Lineare
utilizzando il formato a coefficienti:
Funzione obiettivo: Nella formulazione del problema riportata sopra, la prima riga della stringa milp_coeff
specifica i
coefficienti della funzione obiettivo e l'operazione di ottimizzazione ("min" o "max"). Ovvero la riga :
3 1 -4 7 8 min .
indica la funzione obiettivo (f.o.) da minimizzare, con i coefficienti 3, 1, -4, 7
e 8
rispettivamente
associati alle variabili X1, X2, X3, X4 e X5
. Segue poi il tipo
di funzione obiettivo che è di tipo "min"
.
Infine sulla colonna rhs abbiamo un punto (".") che rappresenta un valore indefinito. Ciò è dovuto al fatto che nel formato
a coefficienti ogni variabile dichiarata deve avere, su ogni rigo, associato un valore; in questo caso inseriamo un valore indefinito,
da associare alla colonna relativa ai valori rhs, in quanto irrilevante nella definizione della funzione obiettivo.
Nel formato a coefficienti, a differenza di quello testuale, ogni singolo valore letto, separato dagli altri da uno o più spazi,
deve essere compiutamente significativo, per cui quando si inserisce il segno davanti ad un numero questo deve essere
rigorosamente unito al numero stesso senza nessun spazio che li separi. Infine i vari coefficienti non necessitano di segno
se questo è positivo.
Vincoli: Le righe successive rappresentano i vincoli del problema.
Ogni vincolo è specificato dai coefficienti delle variabili, seguito dal tipo (TYPE
) di disuguaglianza
("ge"
per ≥
, "le"
per ≤
, "eq"
per =
)
e dal valore del lato destro rhs (o termine noto). Ad esempio, la riga :
5 2 0 3 0 ge 9
rappresenta il vincolo 5X1+2X2+3X4
. Da quanto detto in precedenza, ovvero che ogni variabile
dichiarata deve avere un valore su ogni rigo, ne consegue che se su un vincolo una variabile non è presente,
il relativo coefficiente dovrà comunque essere indicato, ma uguale a zero.
≥
9
Limiti sulle variabili: È possibile specificare limiti superiori e inferiori per le variabili utilizzando
righe dedicate. La sintassi segue lo schema "u a b c d e upper ."
per i limiti superiori e "l n o p q r lower ."
per i limiti inferiori, dove "u"
ed "l"
rappresentano i valori dei limiti per la prima variabile dichiarata nel formato
di imput, "a"
ed "n"
rappresentano i valori dei limiti per la seconda e cosi via. Se non specificati
(ovvero se mancano tali righi), le variabili sono considerate non negative di default. Nell'esempio sopra riportato, l'espressione:
-1 -1 . . 0 lower .
. 6 -2 . . upper .
sta ad indicare :
1) che la prima variabile dichiarata nel formato di input (la X1
) può assumere valori in
[-1,.]
, ovvero [-1,+∞].
2) che la seconda variabile dichiarata (la X2
) può assumere valori in [-1,6]
,
ovvero una variabile che può assumere valori negativi maggiori di -1 o positivi minori di 6.
3) che la terza variabile dichiarata (la X3
) può assumere valori in [.,-2]
,
ovvero può assumere solo valori negativi in [-∞,-2]
.
4) che la quarta variabile dichiarata (la X4
) può assumere valori in [.,.]
,
ovvero [-∞,+∞]
o libera.
5) che la quinta variabile dichiarata (la X5
) può assumere valori in [0,.]
,
ovvero [0,+∞]
.
Variabili libere o negative: Per poter dichiarare variabili libere, ovvero variabili senza limite inferiore
(il limite inferiore non sarà più lo zero ma -infinito), basta specificare un lower bound indefinito.
Se si dichiara un valore indefinito sulla riga dei lower bound o sulla riga degli upper bound, SSC trasforma
tali valori in -infinito nel primo caso ed in +infinito nel secondo. Nel formato a coefficienti il valore indefinito si rappresenta
con il punto "." .
In generale per poter impostare delle variabili che possono assumere valori anche in un range negativo,
basta valorizzare un lower bound indefinito (come sulla X4
) o negativo (come sulla X1
),
oppure un upper bound negativo (come sulla X3
).
Variabili Intere: Per problemi di Programmazione Lineare Intera Mista (MILP), è possibile dichiarare quali variabili
devono assumere valori interi. Ciò viene fatto utilizzando una riga che ha per TYPE
il valore "integer"
e che specifica, tramite i valori 1
e 0
, quali variabili devono essere intere e quali no.
La dichiarazione presente nell'esempio sopra riportato:
0 1 1 0 0 integer .
specifica che le variabili X2
e X3
devono essere intere.
Variabili Binarie: Per problemi di Programmazione Lineare Intera Mista (MILP) , è possibile dichiarare quali variabili
devono assumere valori binari {0,1}
. Ciò viene fatto utilizzando una riga che ha per TYPE
il valore "binary"
e che specifica, tramite i valori 1
e 0
, quali variabili
devono essere binarie e quali no. Ad esempio, la dichiarazione:
1 0 0 0 0 binary .
specifica che la prima variabile dichiarata nel formato di input deve essere binaria.
Variabili semicontinue: È possibile risolvere problemi di programmazione lineare con variabili semicontinue. Ricordiamo che una
variabile semicontinua può essere o pari a zero oppure deve appartenere a un intervallo continuo delimitato. Ad esempio,
sia [l, u]
un intervallo continuo delimitato da l
e u
, allora una variabile
x
può essere definita semicontinua
in un problema LP se l ≤ x ≤ u
oppure se x = 0
, naturalmente con 0 ∉
[l, u]
. Per definire delle variabili semicontinue, occorre aggungere una riga che ha per TYPE
il valore
"semicont"
e che specifica, tramite i valori 1
e 0
, quali variabili
devono essere semicontinue e quali no, ad esempio con la notazione:
1 0 0 1 0 semicont .
Stiamo dichiarando che la prima e la quarta variabile dichiarate nel formato di input sono semicontinue.
Naturalmente se definiamo una variabile x
semicontinua , questa deve essere dichiarata anche limitata tramite
un vincolo del tipo l ≤ x ≤ u
, e quindi occorre definire per la suddetta variabile anche i
valori di upper e lower bound.
Esempi completi di modellazione di problemi che utilizzano il formato a coefficienti sono riportati nella sezione Esempi
di questo sito, dimostrando come rappresentare sia problemi di LP standard
(esempi 1.2 ,
1.4 ,
1.8 ,
1.10
1.14), sia problemi di MILP
(esempi 2.1,
2.4 ,
2.10,
3.2).
La libreria parserizza automaticamente le espressioni presenti nella stringa e le traduce in un modello matematico che può essere risolto utilizzando
algoritmi come il simplesso o il branch and bound.
4.1.4 Formato matriciale
Consideriamo la seguente formulazione matematica di un problema di Programmazione Lineare :
funzione obiettivo:
min 3X1 + X2 - 4X3 + 7X4 + 8X5
vincoli:
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
limiti delle variabili:
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
condizioni :
X5 ≥ 0
X2, X3 ∈ ℤ
Per rappresentare questo problema di Programmazione Lineare affinché sia elaborabile dalla libreria SSC si può
utilizzare il formato matriciale. Questo formato è simile a quello di Apache Simplex Solver ed è particolarmente
utile per rappresentare problemi di programmazione lineare in modo strutturato, consentendo di manipolare facilmente le varie
componenti del problema attraverso l'uso di vettori e matrici (array e matrici java). Occorre quindi definire la matrice
A[][]
c[]
dei coefficienti della f.o. ed il vettore
b[]
dei valori rhs (o termini noti). Naturalmente alla matrice ed ai vettori possono esssere dati nomi diversi.
Il codice Java che segue mostra un esempio di sintassi per rappresentare il problema di LP sopra riportato utilizzando il formato
matriciale:
import org.ssclab.pl.milp.*;
import static org.ssclab.pl.milp.ConsType.*;
import static org.ssclab.pl.milp.LP.NaN;
public class Esempio {
public static void main(String[] args) throws Exception {
double c[] =
{ 3.0, 1.0, -4.0, 7.0, 8.0 }; //vettore dei coefficienti della f.o.
double A[][]={
{ 5.0 , 2.0 , 0.0 , 3.0 , 0.0 },
{ 3.0 , 1.0 , 1.0 , 0.0 , 5.0 },
{ 6.0 , 3.1 , 4.0 , 5.0 , 0.0 },
{ NaN , 6.0 , -2 , NaN , NaN }, //rigo degli upper bound
{ -1 ,-1.0 , NaN, NaN , 0.0 }, //rigo dei lower bound
{ 0.0 , 1.0 , 1.0 , 0.0 , 0.0 }}; //rigo per la definizione degli integer
double b[]= { 9.0, 12.5 ,24.0, NaN, NaN, NaN}; //vettore dei termini noti
ConsType rel[]= { GE, EQ, LE, UPPER, LOWER, INT}; //vettore delle relazioni
LinearObjectiveFunction fo = new LinearObjectiveFunction(c, GoalType.MIN);
ListConstraints constraints = new ListConstraints();
for(int i=0; i < A.length; i++) constraints.add(new Constraint(A[i], rel[i], b[i]));
}
}
Il codice sopra descritto vuole mettere in evidenza, in questa parte iniziale della guida, solo
il formato di rappresentazione di un problema di LP, di conseguenza non risulta completo. L'esempio completo
è riportato nella pagina Esempi
(esempio 3.3) di questo sito.
Definita la matrice java A[][]
b[]
e c[]
, si crea un oggetto LinearObjectiveFunction
che rappresenta la funzione obiettivo e
gli oggetti Constraint
che rappresentano i vincoli, questi ultimi alimenteranno la lista (di tipo ListContraint
)
contenente tutti i vincoli. La lista di vincoli e la funzione obiettivo
permettono di istanziare un problema di programmazione lineare in SSC.
Ecco una descrizione dettagliata di ciascun componente:
Funzione obiettivo: È definita da un vettore c[]
, dove ogni elemento rappresenta il coefficiente
che ogni variabile assume sulla funzione obiettivo (f.o.). Ad esempio, il vettore :
double c[]= { 3.0, 1.0, -4.0, 7.0, 8.0 };
rappresenta la funzione 3X1+X2-4X3+7X4+8X5
.
Se una variabile assume coefficiente nullo sulla f.o., il valore 0
deve essere comunque riportato nel vettore c[]
.
La direzione dell'ottimizzazione (minimizzazione o massimizzazione) viene specificata tramite un parametro di tipo GoalType
,
come "GoalType.MAX"
o "GoalType.MIN"
. Il GoalType
va specificato, insieme al
vettore c[]
, come argomento nel costruttore della classe LinearObjectiveFunction
:
LinearObjectiveFunction fo = new LinearObjectiveFunction(c, GoalType.MIN);
questo permette di creare un oggetto che rappresenta in modo completo la funzione obiettivo.
Vincoli: I vincoli del problema sono definiti utilizzando una matrice A[][]
b[]
contiene i termini noti associati ai vincoli, e l'array rel[]
specifica il tipo di vincolo o relazione, ad esempio "GE"
per i vincoli ≥
, "LE"
per ≤
, "EQ"
per =
.
Ogni vincolo viene creato utilizzando il costruttore "new Constraint(A[i], rel[i], b[i])"
. Se prendiamo l'esempio sopra riportato
e se consideriamo i=0
, ovvero selezioniamo i valori della matrice e dei vettori corrispondenti all'indice i=0
e li
utilizziamo per definire il primo vincolo, otterremo per sostituzione l'equivalente istruzione :
new Constraint( new double[]{ 5.0 , 2.0 , 0.0 , 3.0 , 0.0 }, GE, 9);
Che rappresenta appunto il primo vincolo 5X1+2X2+3X4 ≥ 9
del nostro problema.
Poichè gli oggetti della classe Constraint
vengono di norma creati ed aggiunti alla lista dei vincoli
ciclando sui righi della matrice A[][]
for(int i=0; i < A.length; i++) constraints.add(new Constraint(A[i], rel[i], b[i]));
ed avendo nel nostro esempio inserito nella matrice A[][]
b[]
dei termini noti abbia tanti elementi
quanti sono i righi della matrice A[][]
b[]
della lunghezza corretta si inseriscono degli "NaN"
(che nel formato a matrice
significa valore indefinito) in corrispondenza di quelle relazioni che non hanno necessità di un valore rhs, che poi sono
quelle che hanno per ConsType
i valori "UPPER", "LOWER", "INT", "BIN", "SEMICONT"
. Lo sviluppatore, se vuole, può anche
definire in A[][]
≤ , ≥, =
) e inserire
in array separati i vettori che rappresentano le restanti limitazioni, come nel codice riportato in questo esempio
(Esempio 2.8 righi 34-35).
Volendo elencare la totalità dei valori che ogni elemento dell'array rel[]
può assumere, abbiamo :
LE, GE, EQ, UPPER, LOWER, INT, BIN, SEMICONT
Ai vincoli del problema possono essere assegnate delle etichette o nomi.
Questi nomi non devono essere necessariamente univoci per ciascun vincolo, in tal caso una singola etichetta può essere utilizzata
per più vincoli per identificarli come appartenenti ad un gruppo specifico. Dare un nome o una etichetta ha il solo scopo
di identificare un vincolo o un gruppo di vincoli; difatti in fase di recupero ed interpretazione dei risultati sarà possibile
identificare ciascun vincolo a partire dalla sua etichetta insieme alle altre caratteristiche.
Per definire una etichetta su un vincolo, basta aggiungere il nome del vincolo come ultimo argomento
al costruttore della classe Constraint
, come nell'esempio seguente :
new Constraint(A[i], rel[i], b[i],"Vincolo"+i);
In questo caso ciclando sull'indice i
assegneremo i seguenti nomi: "Vincolo0"
, "Vincolo1"
,
"Vincolo2"
, e così via. Naturalmente si possono dare nomi diversi non necessariamente numerati.
Variabili: Nel formato matriciale i nomi delle variabili del problema di programmazione lineare vengono assegnati
in automatico dal sistema. La prima variabile avrà nome X1
, la seconda X2
, e cosi via.
Limiti delle variabili: I limiti superiori e inferiori delle variabili possono essere specificati utilizzando due righe separate
nella matrice A[][]
ConsType
pari ad "UPPER"
e "LOWER"
nell'array rel[]
. Ad esempio, per la variabile X2
che presenta un limite inferiore -1 e un limite superiore 6,
si possono inserire tali due righe nella matrice A[][]
A[][]
{ NaN , 6.0 , -2 , NaN , NaN }, //rigo degli upper bound
{ -1 ,-1.0 , NaN, NaN , 0.0 }, //rigo dei lower bound
stanno ad indicare :
1) che la variabile X1
può assumere valori in [-1,NaN]
, ovvero [-1,+∞]
.
2) che la variabile X2
può assumere valori in [-1,6]
, ovvero una variabile che assume
valori negativi maggiori di -1
o positivi minori di 6
.
3) che la variabile X3
può assumere valori in [NaN,-2]
, ovvero una variabile che assume
solo valori negativi in [-∞,-2]
.
4) che la variabile X4
può assumere valori in [NaN,NaN]
, ovvero [-∞,,+∞]
o libera.
5) che la variabile X5
può assumere valori in [0,NaN]
, ovvero [0,+∞]
.
Variabili libere o negative:Per poter dichiarare variabili libere, ovvero variabili senza limite inferiore (il limite inferiore non sarà
più lo zero ma -infinito), basta specificare un lower bound indefinito. Se si dichiara un valore indefinito sulla riga dei lower bound
o sulla riga degli upper bound, SSC trasforma tali valori in -infinito nel primo caso ed in +infinito nel secondo.
Nel formato matriciale il valore indefinito si rappresenta
con il "NaN"
. In generale per poter impostare delle variabili che possono assumere valori anche in un range negativo,
basta valorizzare un lower bound indefinito (come sulla X4
) o negativo (come sulla X1
),
oppure un upper bound negativo (come sulla X3
).
Variabili intere: Le variabili che devono assumere valori interi sono indicate tramite una riga nella matrice A[][]
ConsType
, presente nel vettore rel[]
delle relazioni, pari a "INT"
.
Questa riga deve contenere 1 per le variabili intere e 0 per le altre.
Variabili binarie: Le variabili che devono assumere valori binari sono indicate tramite una riga nella matrice A[][]
ConsType
, presente nel vettore rel[]
delle relazioni, pari a "BIN"
.
Questa riga deve contenere 1 per le variabili binarie e 0 per le altre.
Variabili semicontinue: È possibile risolvere problemi di programmazione lineare con variabili semicontinue. Ricordiamo che una
variabile semicontinua può essere o pari a zero oppure deve appartenere a un intervallo continuo delimitato.
Ad esempio, sia [l, u]
un intervallo continuo e delimitato, allora una variabile x
può essere definita
semicontinua se l ≤ x ≤ u
oppure se x = 0
, naturalmente
con 0 ∉ [l, u]
.
Le variabili che devono assumere valori semicontinui sono indicate tramite una riga nella matrice A[][]
ConsType
, presente nel vettore rel[]
, pari a "SEMICONT"
. Questa riga contiene 1
per le variabili che devono essere semicontinue e 0
per le altre. Se nella matrice A[][]
ConsType
pari a "SEMICONT"
ed in tale riga ci fossero i valori:
{ 1.0 , 0.0 , 0.0 , 0.0 , 1.0 },
stiamo dichiarando che la prima e la quinta variabile sono semicontinue. Naturalmente se definiamo una variabile x
semicontinua,
questa deve anche essere dichiarata limitata tramite un vincolo del tipo l ≤ x ≤ u
, e quindi occorre
definire per la suddetta variabile anche i valori di upper e lower bound.
Esempi completi di modellazione di problemi che utilizzano il formato matriciale sono riportati nella sezione Esempi
di questo sito, dimostrando come rappresentare sia problemi di LP standard
(esempi 1.3 ,
1.5 ,
1.13),
sia problemi di MILP
(esempi 2.2,
2.5 ,
2.8,
2.11,
2.13,
3.3).
La libreria parserizza automaticamente le espressioni presenti nella stringa e le traduce in un modello matematico che può essere risolto utilizzando
algoritmi come il simplesso o il branch and bound.
4.1.5 Formato sparso
Consideriamo la seguente formulazione matematica di un problema di Programmazione Lineare :
funzione obiettivo:
min 3X1 + X2 - 4X3 + 7X4 + 8X5
vincoli:
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
limiti delle variabili:
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
condizioni :
X5 ≥ 0
X2, X3 ∈ ℤ
Per rappresentare questo problema di Programmazione Lineare affinchè sia elaborabile dalla libreria SSC si può utilizzare il formato sparso. Questo formato è simile a quello fornito da SAS® (LP procedure) e fornisce un metodo flessibile per rappresentare problemi di programmazione lineare utilizzando una struttura dati che descrive le relazioni tra variabili, vincoli e la funzione obiettivo. Il codice Java che segue mostra un esempio di sintassi per rappresentare il problema sopra riportato utilizzando il formato sparso:
import org.ssclab.ref.InputString;
public class Esempio {
public static void main(String[] args) throws Exception {
String lp_sparse =
// TYPE COL_ ROW_ COEF
" MIN . fo_costo . \n" +
" GE . vincolo1 . \n" +
" EQ . compenso . \n" +
" LE . autonomia . \n" +
" UPPER . lim_superiore . \n" +
" LOWER . lim_inferiore . \n" +
" INTEGER . var_intere . \n" +
" . X1 fo_costo 3 \n" +
" . X1 vincolo1 5 \n" +
" . X1 compenso 3 \n" +
" . X1 autonomia 6 \n" +
" . X1 lim_inferiore -1 \n" +
" . X2 fo_costo 1 \n" +
" . X2 vincolo1 2 \n" +
" . X2 compenso 1 \n" +
" . X2 autonomia 3.1 \n" +
" . X2 lim_superiore 6 \n" +
" . X2 lim_inferiore -1 \n" +
" . X2 var_intere 1 \n" +
" . X3 fo_costo -4 \n" +
" . X3 compenso 1 \n" +
" . X3 autonomia 4 \n" +
" . X3 lim_superiore -2 \n" +
" . X3 var_intere 1 \n" +
" . X4 fo_costo 7 \n" +
" . X4 vincolo1 3 \n" +
" . X4 autonomia 5 \n" +
" . X4 lim_superiore . \n" +
" . X4 lim_inferiore . \n" +
" . X5 fo_costo 8 \n" +
" . X5 compenso 5 \n" +
" . RHS vincolo1 9 \n" +
" . RHS compenso 12.5 \n" +
" . RHS autonomia 24 \n" ;
InputString lp_input = new InputString(lp_sparse);
lp_input.setInputFormat("TYPE:varstring(10), COL_:varstring(3) , ROW_:varstring(14), COEF:double");
}
}
Il codice sopra descritto vuole mettere in evidenza, in questa parte iniziale della guida, solo
il formato di rappresentazione di un problema di LP, di conseguenza non risulta completo. L'esempio completo
è riportato nella pagina Esempi
(esempio 3.4) di questo sito.
In questo formato si definiscono dei dati strutturati presenti in una stringa,
dove ogni riga rappresenta una dichiarazione che definisce un aspetto specifico del problema di programmazione lineare,
come la funzione obiettivo, un vincolo o i limiti delle variabili.
Per separare le diverse definizioni, queste devono trovarsi su righi differenti,
per questo motivo alla fine di ogni definizione si utilizza il catattere '\n' di nuova linea.
Questo formato si compone esclusivamente di quattro colonne di valori che vengono associate alle variabili TYPE, COL_, ROW_, e COEF
che vengono definite nel formato di input.
Per formato di input intendiamo una dichiarazione che descrive come vanno lette ed interpretate le colonne presenti
nella struttura dati nella quale si è formulato il problema. La definizione del formato di input
si effettua attraverso queste due istruzioni :
InputString lp_input = new InputString(lp_sparse);
lp_input.setInputFormat("TYPE:varstring(10), COL_:varstring(3) , ROW_:varstring(14), COEF:double");
La stringa che contiene la formulazione del problema (lp_sparse)
viene passata al costruttore della classe InputString
per creare una istanza di questa classe; su tale istanza è possibile invocare il metodo setInputFormat()
.
Ebbene, la definizione del formato di input si effettua attraverso una stringa da passare come argomento al metodo setInputFormat()
;
in questa stringa si susseguono, separate da virgola, le notazioni
per definire,
in sequenza, i nomi delle variabili da associare alla colonne ed il tipo di dato presente nelle colonne.
Sebbene si parli di 'colonne', ciò serve solo a semplificare la comprensione: il primo dato di ogni riga viene associato alla
prima variabile dichiarata, il secondo dato alla seconda variabile dichiarata, e così via. Non è necessario che i
valori siano allineati rigorosamente in verticale (ovvero che si trovino tutti sul k-esimo carattere di ciascun rigo);
l'importante è che siano separati da almeno uno spazio e che seguano la sequenza corretta. E' da menzionare che in questo formato,
il carattere punto (".") rappresenta il valore indefinito o mancante (analogo ad un null
).
Essendo un formato rigidamente costituito da 4 colonne, indipendentemente dal numero di variabili decisionali e vincoli presenti
nel problema, questo formato può essere utilizzato anche per importare problemi di programmazione lineare
da una tabella di un database (vedi esempio 1.9).
Un secondo vantaggio del formato sparso è che consente di specificare solo i coefficienti diversi da zero nella
descrizione del problema di programmazione lineare.
Vediamo in dettaglio le diverse parti costituenti questo formato:
1) TYPE
: I valori che la colonna TYPE
può assumere sono i seguenti :
MAX MIN EQ LE GE UPPER LOWER INTEGER BINARY SEMICONT
Questi valori possono essere scritti sia in maiuscolo che in minuscolo; in entrambi i casi verranno convertiti in maiuscolo.
Quando il motore di elaborazione analizza una riga con TYPE
valorizzato (diverso da "."),
inizia a definire una nuova entità ed assegna ad essa un marcatore, quello indicato nella colonna dei ROW_
.
Piu specificatamente, se il motore rileva che il TYPE
assume il valore "MAX"
o "MIN"
,
inizia la definizione della funzione obiettivo; se invece il valore di TYPE
è uno dei valori "EQ"
(=) ,
"LE"
(≤
) o "GE"
(≥
), inizia la definizione di un vincolo.
Consideriamo il primo rigo dell'esempio sopra riportato:
MIN . fo_costo .
Durante il processamento di questo rigo, nel quale sono solo le variabili TYPE
e ROW_
ad essere valorizzate,
il motore di elaborazione inizia a creare la definizione della funzione obiettivo associandogli come marcatore il valore
"fo_costo"
e come direzione dell'ottimizazione la minimizzazione.
Come possiamo notare nella riga sono presenti dei punti (".") che rappresentano un valore indefinito.
Ciò è dovuto al fatto che nel formato sparso ogni variabile dichiarata deve avere, su ogni rigo, associato un valore;
in questo caso inseriamo un valore indefinito, da associare alla relative colonne, in quanto irrilevanti
nella creazione della funzione obiettivo.
Consideriamo il secondo rigo:
GE . vincolo1 .
Quando questo rigo viene interpretato si inizia a creare la definizione di un vincolo di disuguaglianza (≥
)
al quale viene assegnato il marcatore "vincolo1"
.
Questo meccanismo permette di definire tutte le caratteristiche del problema.
Difatti, proseguendo nell'esposizione, se la variabile TYPE
assume il valore "UPPER"
o "LOWER"
,
stiamo definendo i marcatori che permettono di impostare i limiti superiori e inferiori delle variabili. Infine, se la variabile TYPE
assume uno dei valori "INTEGER"
, "BINARY"
, o "SEMICONT"
, stiamo definendo i marcatori necessari
per indicare quali variabili sono intere, binarie o semicontinue.
2) ROW_
: Ogni riga con TYPE
valorizzato ha associato un marcatore (specificato nella
colonna ROW_
) che identifica in modo univoco il nome di una entità.
I nomi di questi marcatori sono scelti liberamente dallo sviluppatore, ma è importante notare
che essi sono case-sensitive.
Se una riga contiene un valore in ROW_
ma ha TYPE
indefinito (".") non si sta definendo una nuova entità
ma si sta specificando il coefficiente che una variabile assume su quella entità.
In questo caso il valore COEF
indica il coefficiente che la variabile, specificata in COL_
,
assume per l'entità corrispondente al marcatore presente in ROW_
. Consideriamo il rigo presente nel nostro esempio :
. X1 fo_costo 3
Questo rigo dichiara che la variabile X1
assume il coefficiente 3
sulla funzione obiettivo.
Consideriamo un altro rigo presente nel nostro esempio :
. X1 vincolo1 5
Questo rigo dichiara che la variabile X1
assume il coefficiente 5 sul vincolo identificato
dal marcatore "vincolo1"
.
3) COL_
:
I valori COL_
identificano i nomi delle colonne (ovvero delle variabili). Per rappresentare la colonna dei valori rhs (termini noti)
si utilizza la parola riservata "RHS"
, che quindi non deve essere utilizzata per identificare altro.
4) COEFF
:
I valori COEFF
risultano o i coefficienti che le variabili assumono sulle diverse entità (vincolo o f.o.)
o i valori dei termini noti se il valore della colonna COL_
è uguale a "RHS"
.
Occorre ribadire che i valori della colonna TYPE
e COL_
possono essere espressi sia in maiuscolo che in minuscolo;
in entrambi i casi essi verranno ricondotti al maiuscolo; mentre per la colonna ROW_
esprimere il marcatore di una
stessa entità in minuscolo e in maiuscolo, nell'ambito di una stessa formulazione, significa dichiarare due marcatori
(e quindi due entità) distinti.
In funzione di quanto detto vediamo come definire le diverse componenti che costituiscono un problema di LP:
Funzione obiettivo : Per definire con il formato sparso la funzione obiettivo
3X1+X2-4X3+7X4+8X5
da minimizzare presente nel nostro esempio iniziale,
occorrono i seguenti record :
MIN . fo_costo .
. X1 fo_costo 3
. X2 fo_costo 1
. X3 fo_costo -4
. X4 fo_costo 7
. X5 fo_costo 8
Il primo record, attraverso il valore del TYPE
pari a "MIN"
, informa che si sta definendo una f.o. da
minimizzare e che il marcatore utilizzato per identificarla è "fo_costo"
; con i successivi record si
dichiarano i coefficienti che ogni variabile ha su quel marcatore, che rappresenta appunto la f.o..
Vincoli : Per definire il vincolo
5X1+ 2X2+3X4≥ 9
occorre definire i seguenti record :
GE . vincolo1 .
. X1 vincolo1 5
. X2 vincolo1 2
. X4 vincolo1 3
. RHS vincolo1 9
Nome dei vincoli: Nel momento in cui si definisce un marcatore per un vincolo, questo risulta essere anche il suo nome;
questo permette di identificare un vincolo in fase di recupero ed interpretazione dei risultati insieme alle altre caratteristiche.
Non vi sono restrizioni particolari sui nomi dei vincoli, devono però essere una singola parola senza contenere spazi.
Naturamente se si defiscono nomi particolamernte lunghi occorre che nel formato di input
la variabile ROW_
sia definita con una lunghezza adeguata, maggiore di quella dichiarata
per questo esempio che è di 14 caratteri (ROW_:varstring(14)
).
Nomi delle variabili: Non vi sono restrizioni particolari sui nomi delle variabili, devono pero essere una singola parola senza spazi.
Naturamente se si defiscono nomi particolamernte lunghi occorre che nel formato di input
la variabile COL_
sia definita con una lunghezza adeguata, maggiore di quella dichiarata
per questo esempio che è di 3 caratteri (COL_:varstring(3)
).
Limiti delle variabili : Per definire gli upper bound e i lower bound, occorre preliminarmante definire i marcatori
con TYPE
valorizzato a "UPPER"
e "LOWER"
. Questi consentono di definire i limiti sulle variabili.
Ad esempio, per impostare il limite sulla variabile X1
, limitata in X1 ≥ -1
,
occorre che siano presenti i seguenti record :
LOWER . lim_inferiore .
. X1 lim_inferiore -1
Il primo record, attraverso il valore del TYPE
pari a "UPPER"
, informa che si sta definendo
il marcatore dei lower bound "lim_inferiore"
; con il successivo record si dichiara il lower bound
per la variabile X1
.
Variabili libere o negative: Per poter dichiarare variabili libere, ovvero variabili senza limite inferiore
(il limite inferiore non sarà più lo zero ma -infinito), basta specificare un lower bound indefinito.
Se si dichiara un valore indefinito di lower bound o di upper bound per una variabile, SSC trasforma
tali valori in -infinito nel primo caso ed in +infinito nel secondo. Nel formato sparso il valore indefinito si rappresenta con il punto (".").
In generale per poter impostare delle variabili che possono assumere valori anche in un range negativo,
basta valorizzare un lower bound indefinito (come sulla X4
) o negativo (come sulla X1
),
oppure un upper bound negativo (come sulla X3
).
Variabili intere: Le variabili che devono assumere valori interi sono indicate tramite il marcatore definito dallo sviluppatore
"var_intere"
che ha associato un TYPE
pari a "INTEGER"
.
La variabile intera si indica poi ponendo un 1
sulla colonna dei COEF
come di seguito:
INTEGER . var_intere .
. X2 var_intere 1
Variabili binarie: Le variabili che devono assumere valori binari sono indicate tramite un marcatore definito dallo sviluppatore
che ha associato un TYPE
pari a "BINARY"
.
La variabile intera si indica poi ponendo un 1
sulla colonna dei COEF
.
Variabili semicontinue: È possibile risolvere problemi di programmazione lineare con variabili semicontinue. Ricordiamo che una
variabile semicontinua può essere o pari a zero oppure deve appartenere a un intervallo continuo delimitato.
Ad esempio, sia [l, u]
un intervallo continuo e delimitato, allora una variabile x
può essere definita
semicontinua se l ≤ x ≤ u
oppure se x = 0
, naturalmente
con 0 ∉ [l, u]
.
Le variabili che devono assumere valori semicontinui sono indicate tramite un marcatore definito dallo sviluppatore
che ha associato un TYPE
pari a "SEMICONT"
.
La variabile semicontinua si indica poi ponendo un 1
sulla colonna dei COEF
.
Esempi completi di modellazione di problemi che utilizzano il formato sparso sono riportati nella sezione Esempi
di questo sito, dimostrando come rappresentare sia problemi di LP standard
(esempi 1.7 ,
1.9 ,
1.12) ,
sia problemi di MILP
(esempi 2.3 ,
2.6 ,
2.12 ,
3.4).
La libreria parserizza automaticamente le espressioni presenti nella stringa e le traduce in un modello matematico
che può essere risolto utilizzando algoritmi come il simplesso o il branch and bound.
4.1.6 Formulazione del Problema in un file esterno
La libreria SSC supporta la possibilità di definire un problema di programmazione lineare in un file esterno
utilizzando quattro dei cinque formati disponibili: formato testo, formato JSON, formato a coefficienti e formato sparso.
I dati del problema sono memorizzati in un file esterno e interpretati dalla libreria,
garantendo flessibilità e facilità d'uso. Di seguito, vediamo come gestire ciascun formato.
Formato Testo: Nel formato testo, il problema è descritto in forma verbale all'interno di un file di testo esterno
che viene referenziato utilizzando la classe Paths
e poi interpretato dalla classe LP o MILP
(vedere esempio 1.11).
Formato JSON: Nel formato JSON, il problema è descritto in un oggetto JSON all'interno di un file esterno
che viene referenziato utilizzando la classe Paths
e poi interpretato dalla classe JsonProblem
(vedere esempio 1.17).
Formato a Coefficienti: Nel formato a coefficienti, il problema è descritto in un file di testo esterno
con una strutura dati contenente i valori dei coefficienti delle variabili, i tipi di vincoli e i termini noti.
Il file viene referenziato utilizzando la classe InputFile
(vedere esempio 1.8).
Formato Sparso: Nel formato sparso, il problema è descritto in un file di testo esterno
contenente una tabella con i valori delle quattro colonne necessarie a definire il problema: TYPE, COL_, ROW_, e COEF
.
Il file viene referenziato utilizzando la classe InputFile
(vedere esempio 1.12).
4.1.7 Formulazione del Problema in database esterno
La libreria SSC supporta la possibilità di definire un problema di programmazione lineare in un database esterno (RDBMS)
utilizzando il formato sparso. Viene utilizzato il formato sparso
in quanto è l'unico formato rigidamente costituito da 4 colonne, di conseguenza è indipendentemente dal numero
di variabili decisionali e vincoli presenti nel problema. Questo si sposa con la necessità di una tabella di database
di essere costituita da un numero prefissato di campi. Per poter effettuare questa operazione occorre quindi che il database abbia
quattro campi (colonne) nei quali memorizzare le informazioni
contenute nei campi TYPE, ROW_, COL_ e COEF
del formato sparso.
Per poter recuperare la formulazione del problema da una tabella presente in un database,
occorre scaricare il driver JDBC per il database in questione e istanziare un oggetto Connection. Una volta ottenuta
una connessione al DB, tramite l'oggetto Connection è possibile, da SSC, accedere al DB attraverso il concetto di libreria.
Gli oggetti di tipo Library
rappresentano una interfaccia al database;
da questa interfaccia possiamo ottenere, tramite una query SQL, un oggetto di tipo Input che fa riferimento
ai record relativi al problema inserito nella tabella (vedere esempio 1.9).
4.2.1 Esecuzione dell'ottimizzazione
Per risolvere un problema di Programmazione Lineare (LP) o di Programmazione Lineare Mista Intera (MILP), è innanzitutto
necessario definire il problema utilizzando il formato desiderato, come descritto nei paragrafi precedenti.
A seconda del formato scelto, la formulazione del problema viene memorizzata in oggetti di classi specifiche o che implementano
interfacce specifiche (come l'interfaccia Input
).
Di seguito, i diversi formati e le relative classi da utilizzare:
String
.JsonProblem
.Input, InputString, InputFile
.LinearObjectiveFunction e ListConstraints
.Input, InputString, InputFile
.
Questi oggetti consentono di memorizzare il problema nel formato scelto; l'interprete presente in SSC converte queste diverse
formulazioni in una struttura uniforme, rendendola comprensibile al motore di risoluzione della libreria.
La conversione in una struttura unificata avviene attraverso la creazione di un oggetto della classe LP
(per problemi senza variabili
intere) o della classe MILP
(per problemi misti interi), passando al costruttore l'oggetto contenente il problema.
Una volta creato l'oggetto LP
o MILP
, su entrambe le istanze è possibile invocare il metodo
resolve()
per avviare il processo di risoluzione.
Questo metodo restituisce un valore appartenente alla classe SolutionType
, che indica
se è stata trovata una soluzione ottimale o no. Ecco un esempio completo di risoluzione di un problema
di programmazione lineare utilizzando il formato testo e la classe LP
:
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String pl_string =
"min: 3Y +2x2 +4x3 +7x4 +8X5 \n"+
" 5Y +2x2 +3X4 >= 9 \n"+
" 3Y + X2 + X3 +5X5 = 12 \n" +
" 6Y+3.0x2 +4X3 +5X4 <= 24 \n";
LP lp = new LP(pl_string);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution soluzione=lp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore :"+var.getValue());
}
SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Se nell'esempio fosse stata dichiarata qualche variabile intera, occorre semplicemente sostituire la classe LP
con la classe MILP
.
A seconda del formato prescelto occorre utilizzare l'appropriato costruttore per creare un oggetto di una delle due classi.
Vediamo quali sono i costruttori disponibili per la classe LP
elencati nella seguente tabella in base ai parametri passati
come argomento:
Costruttore classe LP |
Descrizione | Formato da utilizzare | Esempio |
---|---|---|---|
LP(String text) |
Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in una stringa.String text : è la stringa contenente la formulazione del problema in formato testo.
|
TESTO | 1.1 |
LP(ArrayList<String> text) |
Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in un ArrayList.ArrayList<String> text : è un ArrayList contenente una lista ordinata di stringhe,
ognuna delle quali memorizza
una riga del problema formulato con il formato testo.
|
TESTO | 1.15 |
LP(Path path) |
Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in un file esterno.Path path : l'oggetto Path deve riferirsi al percorso in cui si trova il file contenente
il problema di LP formulato con il formato testo.
|
TESTO | 1.11 |
LP(JsonProblem jsonProb) |
Costruttore da utilizzare con la formulazione del problema in formato JSON memorizzato in una stringa
o in un file.JsonProblem jsonProb : è l'oggetto contenente la formulazione del problema in formato JSON.
|
JSON | 1.17 |
LP(LinearObjectiveFunction fo,ArrayList<Constraint> constraints) |
Costruttore da utilizzare con la formulazione del problema in formato matriciale A[][],b[],c[] . LinearObjectiveFunction fo : è l'ogggetto contenente la formulazione della funzione obiettivo. ArrayList<Constraint> constraints : è la lista contenente i singoli vincoli di tipo Constraint.
|
MATRICIALE | 1.13 |
LP(LinearObjectiveFunction fo,ListConstraints constraints) |
Costruttore da utilizzare con la formulazione del problema in formato matriciale A[][],b[],c[] . LinearObjectiveFunction fo : è l'ogggetto contenente la formulazione della funzione obiettivo. ListConstraints constraints : è la lista contenente i singoli vincoli di tipo Constraint.
|
MATRICIALE | 1.3 |
LP(Input input) |
Costruttore da utilizzare con la formulazione del problema in formato a coefficienti.Input input : l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti,
deve implementare questa interfaccia.
|
COEFFICIENTI | 1.2 |
LP(Input input,Session session) |
Costruttore da utilizzare con la formulazione del problema in formato a coefficienti.Input input : l'ogggetto che memorizza la formulazione del problema avente formato a coefficienti
deve implementare questa interfaccia. Session session : è la sessione di lavoro SSC se ne è stata già istanziata una. |
COEFFICIENTI | - |
LP(Input input,FormatType format) |
Costruttore da utilizzare con la formulazione del problema in formato a coefficienti o sparso.Input input : l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti o sparso,
deve implementare questa interfaccia. FormatType format : è il tipo di formato utilizzato nella definizione del problema; si può indicare
FormatType.SPARSE o FormatType.COEFF .
|
SPARSO O COEFFICIENTI | 1.7 |
LP(Input input,Session session, FormatType format) |
Costruttore da utilizzare con la formulazione del problema in formato a coefficienti o sparso.Input input :l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti o sparso,
deve implementare questa interfaccia. Session session : è la sessione di lavoro SSC se ne è stata già istanziata una. FormatType format : è il tipo di formato utilizzato nella definizione del problema; si può indicare
FormatType.SPARSE o FormatType.COEFF .
|
SPARSO O COEFFICIENTI | 1.9 |
Vediamo ora i costruttori disponibili per la classe MILP
(Programmazione Lineare Mista Intera) elencati nella seguente tabella in
base ai parametri passati come argomento:
Costruttore classe MILP |
Descrizione | Formato da utilizzare | Esempio |
---|---|---|---|
MILP(String text) |
Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in una stringa.String text : è la stringa contenente la formulazione del problema in formato testo.
|
TESTO | 2.7 |
MILP(ArrayList<String> text) |
Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in un ArrayList.ArrayList<String> text : è un ArrayList contenente una lista ordinata di Stringhe,
ognuna delle quali memorizza una riga del problema formulato con il formato testo.
|
TESTO | - |
MILP(Path path) |
Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in un file esterno.Path path : l'oggetto Path deve riferirsi al percorso in cui si trova il file contenente
il problema di LP formulato con il formato testo.
|
TESTO | - |
MILP(JsonProblem jsonProb) |
Costruttore da utilizzare con la formulazione del problema in formato JSON memorizzato in una stringa o in un file.JsonProblem jsonProb : è l'oggetto contenente la formulazione del problema in formato JSON.
|
TESTO | 2.15 |
MILP(LinearObjectiveFunction fo,ArrayList<Constraint> constraints) |
Costruttore da utilizzare con la formulazione del problema in formato matriciale A[][],b[],c[] . LinearObjectiveFunction fo : è l'ogggetto contenente la formulazione della funzione obiettivo. ArrayList<Constraint> constraints : è la lista contenente i singoli vincoli di tipo Constraint.
|
MATRICIALE | 2.2 |
MILP(LinearObjectiveFunction fo,ListConstraints constraints) |
Costruttore da utilizzare con la formulazione del problema in formato matriciale A[][],b[],c[] . LinearObjectiveFunction fo : è l'ogggetto contenente la formulazione della funzione obiettivo. ListConstraints constraints : è la lista contenente i singoli vincoli di tipo Constraint.
|
MATRICIALE | 2.5 |
MILP(Input input) |
Costruttore da utilizzare con la formulazione del problema in formato a coefficienti.Input input : l'ogggetto che memorizza la formulazione del problema, avente formato a coefficienti,
deve implementare questa interfaccia.
|
COEFFICIENTI | 2.1 |
MILP(Input input,Session session) |
Costruttore da utilizzare con la formulazione del problema in formato a coefficienti.Input input : l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti,
deve implementare questa interfaccia. Session session : è la sessione di lavoro SSC se ne è stata già istanziata una. |
COEFFICIENTI | - |
MILP(Input input,FormatType format) |
Costruttore da utilizzare con la formulazione del problema in formato a coefficienti o sparso.Input input : l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti o sparso,
deve implementare questa interfaccia FormatType format : è il tipo di formato utilizzato nella definizione del problema; si può indicare
FormatType.SPARSE o FormatType.COEFF .
|
SPARSO O COEFFICIENTI | 2.3 |
MILP(Input input,Session session, FormatType format) |
Costruttore da utilizzare con la formulazione del problema in formato a coefficienti o sparso.Input input : l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti o sparso,
deve implementare questa interfaccia. Session session : è la sessione di lavoro SSC se ne è stata già istanziata una. FormatType format : è il tipo di formato utilizzato nella definizione del problema; si può indicare
FormatType.SPARSE o FormatType.COEFF .
|
SPARSO O COEFFICIENTI | - |
4.2.2 Configurazione e Opzioni di Esecuzione
Come detto, sull'oggetto appartenente alla classe LP
o MILP
, si può invocare il metodo
resolve()
per avviare il processo di risoluzione. Prima di eseguire il run dell'ottimizzazione, la libreria
offre diverse opzioni di configurazione per adattare la risoluzione del problema alle esigenze specifiche dell'utente.
Queste opzioni consentono di controllare la tolleranza, l'utilizzo del multithreading, la possibilità di ottenere
una soluzione fattibile, etc, offrendo un ulteriore controllo sull'algoritmo di risoluzione.
Esecuzione parallela con multithreading
Per migliorare le prestazioni, la libreria consente l'uso del simplesso parallelo, specificando il numero di thread
con il metodo setThreadsNumber()
della classe LP
(vedi esempio 1.14). Per esempio:
LP lp = new LP(lp_input);
lp.setThreadsNumber(LPThreadsNumber.N_4);
In questo caso stiamo specificano 4 thread per l'esecuzione. È possibile utilizzare anche il parametro LPThreadsNumber.AUTO
per delegare al sistema la scelta del numero di thread. L'uso del multithreading è consigliato principalmente per problemi
con migliaia di variabili o vincoli e su macchine con almeno 4 core fisici.
Numero massimo di iterazioni
La libreria permette di limitare il numero massimo di iterazioni tramite setNumMaxIteration()
della classe LP
(vedi esempio 1.10) , il cui valore di default
è 100.000.000:
LP lp = new LP(lp_input);
lp.setNumMaxIteration(500);
In questo modo limitiamo il numero di iterazioni a 500.
Determinazione di una soluzione ammissibile
È possibile configurare l'algoritmo per restituire una soluzione ammissibile,
anche se non ottima, utilizzando il metodo setJustTakeFeasibleSolution(true)
della classe LP
(vedi esempio 1.10). Questo approccio, adatto in situazioni in cui si
cerca una soluzione ammissibile rapida, esegue solo la prima fase del simplesso:
LP lp = new LP(lp_input);
lp.setJustTakeFeasibleSolution(true);
Se esiste una soluzione ammissibile, il metodo resolve()
restituirà SolutionType.FEASIBLE
,
permettendo di ottenere una soluzione basica senza procedere alla ricerca dell'ottimo.
Modifica della tolleranza
Una delle opzioni riguarda la tolleranza utilizzata per determinare la convergenza della 'fase uno' dell'algoritmo del simplesso.
Questa opzione può essere configurata utilizzando il metodo setCEpsilon()
della classe LP
(vedi esempio 1.13). Per esempio:
LP lp = new LP(fo,constraints);
lp.setCEpsilon(EPSILON._1E_M5);
La tolleranza di default è impostata su 1E-8. Tuttavia, in presenza di numeri molto grandi, potrebbe essere
necessario aumentarla a un valore maggiore per garantire che il valore ottimo della funzione obiettivo, nella fase uno del simplesso,
soddisfi la condizione di ottimalità. Ricordiamo che condizione necessaria affinchè il problema ammetta una soluzione
ammissibile è che il valore ottimo della fase uno del simplesso sia uguale a zero. Ciò potrebbe non avvenire
a causa della manipolazione di numeri di grandezza molto elevata. In questo particolare caso se non si modifica
la tolleranza ε
del valore ottimo z
della f.o relativo alla fase uno la risoluzione del problema
potrebbe non dare come risultato soluzioni ammissibili.
In altre parole, se alla fine della fase uno |z| > ε
, allora il problema non ammette soluzioni.
Per ovviare a questo, nelle righe sopra riportate, la tolleranza viene aumentata da 1E-8 (valore di default) a 1E-5.
per far si che possa avvenire che |z| < ε
.
Senza questa modifica, il problema potrebbe risultare privo di soluzioni ammissibili, nonostante esistano.
Naturalmente i valori di tolleranza usabili sono diversi : 1E-4, 1E-5, 1E-6, etc
Elenchiamo nella tabella che segue i metodi della classe LP
e
MILP
da utilizzare per impostare le varie opzioni di configurazione:
Metodo | Descrizione | Classe | Esempio |
---|---|---|---|
setEpsilon(EPSILON epsilon) |
Questo metodo consente di impostare il valore epsilon relativo alla tolleranza che interviene in vari contesti.
Viene utilizzato nei seguenti casi: 1) Durante la fase uno, sia nella determinazione della variabile in entrata che in quella in uscita con o senza la regola Bland. 2) Viene utilizzato per determinare se la base è degenere. 3) Viene utilizzato alla fine della fase uno: se nella base è presente una variabile ausiliaria, epsilon viene utilizzato per determinare se è possibile eliminare le righe e le colonne di queste sulla tabella estesa. 4) Durante la fase due, sia nella determinazione della variabile in entrata che in quella in uscita con o senza la regola Bland. EPSILON epsilon : è l'unumerazione con i diversi valori di tolleranza impostabili :
_1E_M12 , _1E_M11 , _1E_M10 , _1E_M9 , _1E_M8 , etc.
|
LP | - |
setCEpsilon(EPSILON epsilon) |
Questo metodo consente di impostare il valore epsilon (ε ) relativo alla tolleranza
permessa sulla soluzione finale della fase 1. Ovvero, se il valore z della soluzione ottimale espressa
dalla fase 1 è prossima allo zero, ovvero se |z| < ε EPSILON epsilon : è l'unumerazione con i diversi valori di tolleranza impostabili :
_1E_M12 , _1E_M11 , _1E_M10 , _1E_M9 , _1E_M8 , etc.
|
LP | 1.13 |
setNumMaxIteration(int num_max_iteration) |
Questo metodo consente di limitare il numero massimo di iterazioni del simplesso (iterazioni fase 1
+ iterazioni fase 2).int num_max_iteration : è un intero che esprime il numero massimo di iterazioni.
|
LP | 1.10 |
setParallelSimplex(boolean isParallelSimplex) |
Permette di attivare il multithreading. Le prestazioni del simplesso possono essere migliorate
eseguendo i processi di ottimizzazione in parallelo su più thread. Il numero di thread è impostato su AUTO,
il sistema decide il numero di thread da utilizzare.boolean isParallelSimplex : un booleano che se true attiva il multithreading.
|
LP | - |
setThreadsNumber(LPThreadsNumber threadsNumber) |
Permette di attivare il multithreading e imposta trasmite il parametro passato il numero di thread
da utilizzare nell'esecuzione. Se il valore passato è AUTO, il sistema decide in autonomia numero di thread da utilizzare.
LPThreadsNumber threadsNumber : una enumerazione che specifica il numero di thread da utilizzare, ammette i valori :
AUTO, N_1, N_2 , N_4 , N_6 , N_8 , etc.
|
LP | 1.14 |
setJustTakeFeasibleSolution(boolean isStopPhase2) |
Impostandolo su true è possibile interrompere il simplesso alla fine della fase 1,
per determinare non una soluzione ottimale ma solo una soluzione fattibile del problema.boolean isStopPhase2 un booleano che se true interrompere il simplesso alla fine della fase 1.
|
LP | 1.10 |
setEpsilon(EPSILON epsilon) |
Questo metodo consente di impostare il valore epsilon relativo alla tolleranza che interviene in vari contesti.
Viene utilizzato nei seguenti casi: 1) Durante la fase uno, sia nella determinazione della variabile in entrata che in quella in uscita con o senza la regola Bland. 2) Viene utilizzato per determinare se la base è degenere. 3) Viene utilizzato alla fine della fase uno: se nella base è presente una variabile ausiliaria, epsilon viene utilizzato per determinare se è possibile eliminare le righe e le colonne di queste sulla tabella estesa. 4) Durante la fase due, sia nella determinazione della variabile in entrata che in quella in uscita con o senza la regola Bland. EPSILON epsilon : è l'unumerazione con i diversi valori di tolleranza impostabili :
_1E_M12 , _1E_M11 , _1E_M10 , _1E_M9 , _1E_M8 , etc.
|
MILP | - |
setCEpsilon(EPSILON cepsilon) |
Questo metodo consente di impostare il valore epsilon (ε ) relativo alla tolleranza
permessa sulla soluzione finale della fase 1 dei simplessi. Ovvero, se il valore z della soluzione ottimale
espressa dalla fase 1 è prossima allo zero, ovvero se |z| < ε EPSILON epsilon : è l'unumerazione con i diversi valori di tolleranza impostabili :
_1E_M12 , _1E_M11 , _1E_M10 , _1E_M9 , _1E_M8 , etc.
|
MILP | - |
setIEpsilon(EPSILON iepsilon) |
Questo metodo consente di impostare il valore epsilon relativo alla tolleranza per determinare
se un numero debba essere considerato intero o meno. Questo controllo avviene quando alla fine del simplesso la
soluzione trovata viene valutata per soddisfare la condizione intera sulle variabili che devono essere intere.
Sia x un numero e Int(x) l'intero più vicino a x, se EPSILON epsilon : è l'unumerazione con i diversi valori di tolleranza impostabili :
_1E_M12 , _1E_M11 , _1E_M10 , _1E_M9 , _1E_M8 , etc.
|
MILP | - |
setThreadsNumber(MILPThreadsNumber lpThreadsNumber) |
Questo metodo consente di impostare il numero di thread da utilizzare per l'esecuzione di Branch and Bound.MILPThreadsNumber lpThreadsNumber : una enumerazione che specifica il numero di thread da utilizzare, ammette i valori :
N_1, N_2 , N_4 , N_6 , N_8 , N_16 etc.
|
MILP | 2.13 |
setJustTakeFeasibleSolution(boolean isJustTakeFeasibleSolution) |
Impostandolo su true è possibile interrompere il Branch and Bound per determinare non una soluzione
ottimale ma solo una soluzione fattibile al problema.boolean isJustTakeFeasibleSolution un booleano interrompe il B&B appena trovata una soluzione ammissibile.
|
MILP | 2.14 |
setNumMaxSimplexs(int num_max_simplex) |
Essendo il B&B una successione di esecuzioni di simplessi,
imposta il numero massimo di simplessi eseguibili. Defalt 1.000.000int num_max_simplex : è un intero che esprime il numero massimo di simplessi.
|
MILP | - |
setNumMaxIterationForSingleSimplex(int num_max_iteration) |
Questo metodo consente di limitare il numero massimo di iterazioni del singolo simplesso (iterazioni fase 1
+ iterazioni fase 2). Defalt 10.000.000.int num_max_iteration : è un intero che esprime il numero massimo di iterazioni per simplesso.
|
MILP | - |
Abbiamo visto nei precedenti paragrafi che per eseguire l'ottimizzazione di una formulazione di un problema di LP
occorre istanzire un oggetto della classe LP
(o MILP
se ci sono delle variabili intere)
ed invocare il metodo resolve()
, come indicato nelle seguenti istruzioni :
LP lp = new LP(pl_string);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
...
...
Possiamo notare come il metodo resolve()
restituisca un oggetto di tipo SolutionType
che puo assumere i seguenti valori
(vedi esempio 1.10) :
OPTIMUM FEASIBLE ILLIMITATUM VUOTUM MAX_ITERATIUM MAX_NUM_SIMPLEX
Analizziamo nel dettaglio ognuno di questi valori:
OPTIMUM
: Se l'istanza della classe LP
(o MILP
) riesce ad convergere verso la soluzione ottima,
viene restituito questo valore; è possibile quindi recuperale i valori ottimi della variabili decisionali e della funzione obiettivo
insieme a molte altre informazioni inerenti la risoluzione del problema.
FEASIBLE
: Se sull'istanza della classe LP
(o MILP
) viene richiamato il metodo
setJustTakeFeasibleSolution(true)
il motore di risoluzione non cerca la soluzione ottima, ma determina la prima soluzione
ammissibile determinata. Se l'istanza della classe LP
(o MILP
) riesce ad convergere verso la soluzione ammissibile,
viene restituito questo valore; è possibile quindi recuperale i valori della variabili decisionali e della funzione obiettivo relativi a tale
soluzione ammissibile insieme a molte altre informazioni inerenti la risoluzione del problema.
ILLIMITATUM
: Il problema non ammette soluzione ottima, ma solo un ottimo illimitato.
VUOTUM
: Il problema non ammette soluzioni.
MAX_ITERATIUM
: L'istanza della classe LP
ha raggiunto il numero massimo di iterazioni.
MAX_NUM_SIMPLEX
: L'istanza della classe MILP
ha raggiunto il numero massimo di Simplessi eseguibili.
4.3.1 Interfaccia Solution
Dopo aver eseguito il metodo resolve()
ed ottenuto una soluzione ottimale o ammissibile, puoi accedere ai dettagli della
soluzione individuata. Per farlo, è necessario richiamare il metodo getSolution()
sull'istanza di LP
(o MILP
). Consideriamo la seguente porzione di codice:
LP lp = new LP(pl_string);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution soluzione=lp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Variabile "+var.getName() +": "+var.getLower() + " <= ["+var.getValue()+"] <= "+var.getUpper());
}
SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
}
Il metodo getSolution()
restituisce un oggetto che implementa l'interfaccia Solution
, dal quale
è possibile ottenere informazioni sulla soluzione ottimale o ammissibile. Attraverso l'oggetto Solution
, puoi accedere
a un array di oggetti Variable
, che contengono i valori che le variabili decisionali assumono nella soluzione,
oltre a recuperare il valore ottimale della funzione obiettivo con il metodo getOptimumValue()
.
Oltre ai valori assunti dalle variabili decisionali, gli oggetti Variable
permettono di ottenere i relativi upper e lower
bound richiamando i metodi getUpper()
e getLower()
. Questa funzionalità consente di verificare
facilmente i limiti inferiori e superiori
definiti in fase di formulazione del problema su ciascuna variabile.
Se invece hai impostato la ricerca di una soluzione ammissibile ma non ottimale, tramite il metodo setJustTakeFeasibleSolution(true)
,
dovrai utilizzare al posto di getOptimumValue()
il metodo getValue()
per ottenere il valore
della funzione obiettivo, poiché non verrà calcolato il
valore ottimale (vedi esempio 2.14).
L'oggetto Solution
fornisce anche altre informazioni utili. Ad esempio, tramite il metodo getSolutionConstraint()
,
è possibile ottenere dettagli sui vincoli. Ecco un esempio pratico:
LP lp = new LP(pl_string);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution soluzione=lp.getSolution();
for(SolutionConstraint constraint: soluzione.getSolutionConstraint()) {
SscLogger.log("Vincolo "+constraint.getName()+" : value ="+constraint.getValue()+
"[ "+constraint.getRel()+" "+constraint.getRhs()+" ]" );
}
}
In questo codice, richiamando il metodo getSolutionConstraint()
, otteniamo un array di oggetti SolutionConstraint
,
che rappresentano i vincoli risolti, ovvero i valori dei vincoli nella soluzione individuata. Questi valori, chiamati LHS (Left Hand Side), sono
confrontati con i corrispettivi valori RHS (Right Hand Side) tramite il metodo getRhs()
.
Nel contesto di un problema di programmazione lineare della forma AX<=>b
, LHS rappresenta il prodotto AX
,
mentre RHS rappresenta b
. È importante notare che le variabili inserite nella parte destra del segno di
disuguaglianza o uguaglianza durante la definizione del problema in formato testo non saranno considerate come parte del RHS,
ma verranno raggruppate nei valori AX
.
Il codice mostra anche il nome del vincolo (ottenuto tramite getName()
) e il tipo di vincolo (getRel()
),
consentendo una visione completa delle caratteristiche dei vincoli risolti.
Infine, nel caso di un problema di programmazione lineare intera (MILP), tramite l'oggetto Solution
è
possibile ottenere informazioni non solo sulla soluzione ottima misto intera individuata, ma anche
sul suo rilassamento lineare. Ricordiamo che un rilassamento lineare è una versione semplificata di un
problema di ottimizzazione ottenuta rimuovendo o allentando alcuni vincoli, in questo caso quelli di integrità.
Per cui i vincoli che richiedono che le variabili siano intere vengono rimossi, consentendo alle variabili di
assumere valori continui.
Per ottenere informazioni in merito alla soluzione rilassata occorre invocare sull'istanza MILP
il metodo getRelaxedSolution()
che restituirà sempre un oggetto Solution
contenente però le informazioni inerenti la soluzione rilassata, come da esempio che segue:
MILP milp = new MILP(fo,constraints);
SolutionType solution=milp.resolve();
if(solution==SolutionType.OPTIMUM) {
Solution sol=milp.getSolution();
Solution sol_relax=milp.getRelaxedSolution();
Variable[] var=sol.getVariables();
Variable[] var_relax=sol_relax.getVariables();
for(int _i=0; _i< var.length;_i++) {
SscLogger.log("Nome variabile :"+var[_i].getName() + " valore:"+var[_i].getValue()+
" ["+var_relax[_i].getValue()+"]");
}
SscLogger.log("valore ottimo:"+sol.getOptimumValue() +" valore rilassamento : ["+sol_relax.getOptimumValue()+"]");
}
È importante precisare che anche sulle variabili semicontinue si applica il rilassamento; questo determinerà che se x è una variabile semicontinua per la quale x puo assumere valori in \( x \in \text{{0}} \cup [l, u] \), la soluzione rilassata verrà calcolata in x su un nuovo insieme di valori più ampio (rilassato): \( x \in [0, u] \).
La libreria permette di salvare la soluzione di un problema di Programmazione Lineare Mista Intera (MILP) o
Programmazione Lineare (LP) in formato JSON. Utilizzando il metodo resolve(null)
è possibile costruire una catena
di chiamate per salvare i risultati su un file esterno o manipolare direttamente la rappresentazione JSON della soluzione.
Ecco un esempio di come creare una catena per salvare il risultato in un file JSON:
new MILP(pl_string)
.setTitle("Esempio risultati in JSON")
.resolve(null)
.getSolutionAsJson()
.saveToFile("c:\\sscResult\\solution.json");
In questo esempio, la soluzione del problema viene risolta e memorizzata in un file JSON esterno. È importante notare che
viene passato il valore null
al metodo resolve()
per abilitare il concatenamento dei metodi, permettendo di ottenere la soluzione
senza restituire un tipo di risultato specifico.
In alternativa, è possibile memorizzare la soluzione in una stringa JSON:
String json = new MILP(pl_string)
.resolve(null)
.getSolutionAsJson()
.toString();
Se nel salvataggio del JSON, in un file esterno o in una stringa, si vuole che esso sia formattato, ovvero che presenti indentazione e ritorni a capo,
richiamare il metodo formatted(true)
, come nell'esempio seguente:
String json = new MILP(pl_string)
.resolve(null)
.getSolutionAsJson()
.formatted(true)
.toString();
Se si preferisce lavorare con un oggetto JSON direttamente, come JsonObject
della libreria jakarta.json, è possibile fare in questo modo:
JsonObject jsonObject = new MILP(pl_string)
.resolve(null)
.getSolutionAsJson()
.getJsonObject();
La struttura JSON generata avrà diverse sezioni, che possono includere informazioni come meta-dati, vincoli e bounds delle variabili (vedi esempio 1.18). La struttura del JSON è la seguente:
{
"meta": { ... },
"objectiveType": "min",
"status": "optimal",
"solution": { ... },
"relaxedSolution": { ... }
}
Le diverse sezioni presenti nel JSON possono essere aggiunte o rimosse specificando le costanti SolutionDetail
nel metodo
getSolutionAsJson()
. Ad esempio, per includere i bounds delle variabili e la soluzione rilassata:
MILP milp=new MILP(pl_string);
milp.resolve();
String json=milp.getSolutionAsJson(SolutionDetail.INCLUDE_BOUNDS,SolutionDetail.INCLUDE_RELAXED).toString();
I valori che SolutionDetail
può assumere includono:
INCLUDE_BOUNDS
: Aggiunge i bounds (limiti superiori e inferiori) delle variabili specificati in fase di formulazione del problema.
INCLUDE_RELAXED
: Include la soluzione rilassata (vedi paragrafo precedente).
INCLUDE_CONSTRAINT
: Aggiunge i valori LHS e RHS dei vincoli del problema (vedi paragrafo precedente).
INCLUDE_META
: Fornisce meta-informazioni sull'ottimizzazione, come il tempo di esecuzione e il numero di thread.
INCLUDE_TYPEVAR
: Include il tipo di ciascuna variabile (es. intera, binaria, continua).
In SSC è attivo di default un logger che mostra le informazioni della avvenuta esecuzione,
informando l'utente mediante messaggi sulla console. Prendiamo ad esempio il log relativo all'esecuzione del problema
1.1 presente nella sezione Esempi
di questo sito :
11/09/24 15:03:57 - INFO:
11/09/24 15:03:57 - INFO: ##############################################
11/09/24 15:03:57 - INFO: SSC Version 4.2.2
11/09/24 15:03:57 - INFO: ##############################################
11/09/24 15:03:57 - INFO:
11/09/24 15:03:57 - INFO: Aperta sessione con ID: 1700441298
11/09/24 15:03:57 - INFO: Assegnata libreria WORK C:\ssclab\ssc_work\work_1720063492
11/09/24 15:03:58 - INFO: Avviata procedura utilizzando il seguente numero di Thread: 1
11/09/24 15:03:58 - INFO: ---------------------------------------------
11/09/24 15:03:58 - INFO: Valore funzione obiettivo fase Uno :8.881784197001252E-16
11/09/24 15:03:58 - TIME: Durata fase Uno Simplesso 00:00:00:007 (hh:mm:ss:mmm)
11/09/24 15:03:58 - INFO: Numero iterazioni fase Uno Simplesso :2
11/09/24 15:03:58 - TIME: Durata fase Due Simplesso 00:00:00:013 (hh:mm:ss:mmm)
11/09/24 15:03:58 - INFO: Numero iterazioni totali (fase Uno + fase Due) Simplesso :3
11/09/24 15:03:58 - TIME: Durata totale Simplesso 00:00:00:020 (hh:mm:ss:mmm)
11/09/24 15:03:58 - INFO: Il simplesso ha trovato una soluzione ottima.
11/09/24 15:03:58 - INFO: ---------------------------------------------
11/09/24 15:03:58 - INFO: Accuratezza soluzione ottima x :
11/09/24 15:03:58 - INFO: Ax + s = b -> Ax + s - b = e (errore).
11/09/24 15:03:58 - INFO: x >= 0, b >= 0, s >= 0 variabili slacks.
11/09/24 15:03:58 - INFO: Errore medio, Mean(e):2.886579864025407E-14
11/09/24 15:03:58 - INFO: Errore massimo, Max(e):1.1368683772161603E-13
11/09/24 15:03:58 - INFO: ---------------------------------------------
11/09/24 15:03:58 - INFO: Chiusa sessione con ID: 1700441298
11/09/24 15:03:58 - LOG: Nome variabile :X2 valore :0.0
11/09/24 15:03:58 - LOG: Nome variabile :X3 valore :0.0
11/09/24 15:03:58 - LOG: Nome variabile :X4 valore :0.0
11/09/24 15:03:58 - LOG: Nome variabile :X5 valore :0.0
11/09/24 15:03:58 - LOG: Nome variabile :Y valore :4.0
11/09/24 15:03:58 - LOG: Valore ottimo:12.0
Il sistema di logging della libreria fornisce informazioni sull'esecuzione dell'algoritmo di risoluzione.
Le voci marcate come "INFO"
offrono un quadro generale sull'avanzamento, inclusa l'apertura e la chiusura della sessione di lavoro,
il numero di thread utilizzati e i risultati del metodo del simplesso, come il numero di iterazioni e l'accuratezza della soluzione.
Le voci "TIME"
indicano la durata di ciascuna fase del processo. Al contrario, le voci con "LOG"
sono generate
dallo sviluppatore utilizzando la classe SscLogger
e, nel nostro esempio, permettono di visualizzare
dettagli specifici sulla soluzione trovata, come i valori delle variabili e il valore ottimo della f.o..
In questo caso è lo sviluppatore a decidere se scrivere
determinati risultati nel log oppure gestirli diversamente per memorizzarli su altre locazioni.
Per scrivere sul log, che di default stampa i messaggi nella console standard (di solito, System.out),
basta invocare il metodo log()
della classe SscLogger
, come nell'esempio:
SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
Questa istruzione generera sulla console standard il seguente messaggio :
11/09/24 15:03:58 - LOG: Valore ottimo:12.0
Ricordiamo che le classi per il logging (SscLogger, SscLevel
) sono contenute nel package org.ssclab.log
.
Lo sviluppatore se vuole può non solo generare messaggi di tipo "LOG"
, ma anche degli altri "livelli",
utilizzando i metodi disponibili. Ad esempio per generare un messaggio "INFO"
, uno "WARNIG"
ed uno
"ERROR"
occorre utilizzare le seguenti istruzioni :
SscLogger.info("Avvio programma ottimizzazione.");
SscLogger.warning("Il numero di variabili e' molto elevato.");
SscLogger.error("C'e stato un errore durante l'elaborazione.");
Queste istruzioni genereranno sulla console standard i seguenti messaggi :
11/09/24 16:47:26 - INFO: Avvio programma ottimizzazione.
11/09/24 16:47:26 - WARNING: Il numero di variabili e' molto elevato.
11/09/24 16:47:26 - ERROR: C'e stato un errore durante l'elaborazione.
Se lo sviluppatore non ha necessità di avere un log, può disabilitarlo ponendo all'inizio del suo codice la seguente istruzione :
SscLogger.setLevel(SscLevel.OFF);
L'istruzione appena utilizzata non fa altro che impostare il log ad un determinato livello attraverso il metodo setLevel()
.
Ciò sta ad indicare che esistono diversi livelli, impostabili dallo sviluppatore, ognuno dei quali permette di visualizzare solo
i messaggi che appartengono al livello impostato e ai livelli gerarchicamente superiori.
La gerarchia, e quindi anche i livelli selezionabili, sono i seguenti:
ALL FINE CONFIG INFO LOG TIME NOTE WARNING ERROR
Nel momento in cui si seleziona un livello, tutti i restanti livelli posizionati alla destra della lista, insieme al livello prescelto,
risultano visualizzabili sulla console. Ad esempio se si sceglie "WARNING"
(con l'istruzione
SscLogger.setLevel(SscLevel.WARNING)
), verranno visualizzati soli i "WARNING"
e gli "ERROR"
.
Se il log deve essere memorizzato su file esterno è possibile inviare il logging su file utilizzando
la seguente istruzione :
SscLogger.setLogToFile("c:\\logs\\simplesso.log",true);
Che permette di memorizzare il log nel file di nome simplesso.log
; il secondo parametro permette, se true
,
di andare in append.
La documentazione API è disponibile al seguente link API.