Indice degli esempi
- Programazione lineare
- Risoluzione di un problema di LP espresso in formato testuale
- Risoluzione di un problema di LP espresso in formato a coefficienti
- Risoluzione di un problema di LP espresso in formato matriciale
- Risoluzione di un problema di LP con variabili delimitate e libere espresso in formato a coefficienti
- Risoluzione di un problema di LP con variabili delimitate e libere espresso in formato matriciale
- Risoluzione di un problema di LP con variabili delimitate e libere espresso in formato testuale
- Risoluzione di un problema di LP espresso in formato sparso
- Risoluzione di un problema di LP in formato a coefficienti memorizzato in un file esterno
- Risoluzione di un problema di LP in formato sparso memorizzato in un database
- Risoluzione di un problema di LP al fine di ottenere solo una soluzione ammissibile
- Risoluzione di un problema di LP in formato testuale memorizzato in un file esterno
- Risoluzione di un problema di LP in formato sparso memorizzato in un file esterno
- Risoluzione di un problema di LP e modifica della tolleranza ε relativa al valore assunto dalla f.o. al termine della fase 1 del simplesso
- Risoluzione di un problema di LP mediante un'implementazione del simplesso parallelo
- Risoluzione di un problema di LP espresso in formato testuale contenuto in un ArrayList
- Risoluzione di un problema di LP espresso in formato JSON
- Risoluzione di un problema di LP espresso in formato JSON memorizzato in un file esterno
- Risoluzione di un problema di LP e salvataggio dei risultati su un file JSON esterno
- Risoluzione di un problema di LP e salvataggio dei risultati su un file di testo esterno
- Programazione lineare intera, misto intera e binaria
- Risoluzione di un problema di MILP in formato a coefficienti
- Risoluzione di un problema di MILP in formato matriciale
- Risoluzione di un problema di MILP in formato sparso
- Risoluzione di un problema di MILP in formato a coefficienti con variabili binarie
- Risoluzione di un problema di MILP in formato matriciale con variabili binarie
- Risoluzione di un problema di MILP in formato sparso con variabili binarie
- Risoluzione di un problema di MILP in formato testuale
- Risoluzione di un problema di MILP e confronto della soluzione ottima con quella ottenuta dal suo rilassamento
- Risoluzione di un problema di MILP e confronto del valore che assume la parte LHS di ogni vincolo con il corrispettivo valore RHS
- Risoluzione di un problema di MILP che presenta variabili semicontinue
- Risoluzione di un problema di MILP in formato matriciale che presenta variabili semicontinue
- Risoluzione di un problema di MILP in formato sparso che presenta variabili semicontinue
- Risoluzione di un problema di MILP utilizzando thread multipli (B&B parallelo)
- Risoluzione di un problema di MILP al fine di ottenere una soluzione ammissibile
- Risoluzione di un problema di MILP espresso in formato JSON
- Risoluzione di un problema di MILP e salvataggio dei risultati su un file JSON esterno
- Risoluzione di un problema con variabili SOS1 (New)
- Risoluzione di un problema con variabili SOS2 (New)
- Risoluzione di un problema con variabili SOS di tipo misto (New)
- Esempi presenti nella "Guida"
- Risoluzione di un problema di MILP espresso in formato testuale
- Risoluzione di un problema di MILP espresso in formato a coefficienti
- Risoluzione di un problema di MILP espresso in formato matriciale
- Risoluzione di un problema di MILP espresso in formato sparso
- Risoluzione di un problema di MILP espresso in formato JSON
Esempio 1.1
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
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 pl_string = """
min: 3Y +2x2 +4x3 +7x4 +8X5
5Y +2x2 >= 9 -3X4
3Y + X2 + X3 +5X5 = 12
6Y +3x2 +4X3 <= 124 -5X4
y + 3x2 +6X5 <= 854 -3X4 """;
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);
}
}
Esempio 1.2
Si consideri il seguente problema di LP:
Vogliamo risolvere questo problema usando un secondo formato di rappresentazione. In questo secondo caso possiamo utilizzare dei dati strutturati dove ciascun rigo rappresenta o la funzione obiettivo o un vincolo, mentre le colonne rappresentano i coefficienti delle variabili, le relazioni, i valori rhs [righi 10-13 del codice sottostante]. Questa rappresentazione è denominata a coefficienti.
Formulato il problema occorre specificare il suo tracciato record (o 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 [righi 10-13]. La definizione del formato di input si effettua attraverso una stringa da passare come argomento al metodo setInputFormat() [rigo 15]; in questa stringa si susseguono 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. In definitiva si dichiarano: i nomi delle variabili da assegnare alle prime due colonne che rappresentano le variabili del problema di LP (in questo caso X1 e X2, di tipo numerico double), la variabile relativa alla colonna delle relazioni (chiamata TYPE e di tipo stringa con lunghezza di 3 caratteri), la variabile relativa alla colonna dei valori rhs (chiamata RHS e di tipo double). I nomi da assegnare alle variabili del problema di LP devono essere scelti dall'analista (devono però iniziare con un carattere alfabetico seguito da caratteri alfanumerici), mentre il nomi delle variabili da associare alla colonna delle relazioni e a quella dei valori rhs devono necessariamente essere TYPE e RHS [rigo 15].
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 però è 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". Questa seconda notazione, certamente più compatta, permette di dichiarare tutte le variabili comprese nell'intervallo che va da X1 a Xn.
Possiamo notare come sulla riga relativa alla definizione della f.o. sia presente, nella colonna dei valori rhs, un punto (".") che rappresenta un valore indefinito (simile ad un null). 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.
Una volta rappresentato il problema e assegnati i nomi alle variabili, si esegue l'algoritmo del Simplesso mediante la creazione di un oggetto della classe LP e l'invocazione del metodo resolve() [righi 17-18]. Una volta eseguito il Simplesso, il metodo resolve() ritorna il tipo di soluzione trovata; se la soluzione è ottima è possibile ricavare i valori delle variabili ed il valore ottimo della funzione obiettivo. Si ricorda che in SSC, di default, le variabili di un problema di LP sono considerate, se non diversamente specificato, non negative ( ≥ 0).
max X1 + 3X2 X1 + X2 ≥-1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 con X1, X2 ≥ 0
Vogliamo risolvere questo problema usando un secondo formato di rappresentazione. In questo secondo caso possiamo utilizzare dei dati strutturati dove ciascun rigo rappresenta o la funzione obiettivo o un vincolo, mentre le colonne rappresentano i coefficienti delle variabili, le relazioni, i valori rhs [righi 10-13 del codice sottostante]. Questa rappresentazione è denominata a coefficienti.
Formulato il problema occorre specificare il suo tracciato record (o 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 [righi 10-13]. La definizione del formato di input si effettua attraverso una stringa da passare come argomento al metodo setInputFormat() [rigo 15]; in questa stringa si susseguono 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. In definitiva si dichiarano: i nomi delle variabili da assegnare alle prime due colonne che rappresentano le variabili del problema di LP (in questo caso X1 e X2, di tipo numerico double), la variabile relativa alla colonna delle relazioni (chiamata TYPE e di tipo stringa con lunghezza di 3 caratteri), la variabile relativa alla colonna dei valori rhs (chiamata RHS e di tipo double). I nomi da assegnare alle variabili del problema di LP devono essere scelti dall'analista (devono però iniziare con un carattere alfabetico seguito da caratteri alfanumerici), mentre il nomi delle variabili da associare alla colonna delle relazioni e a quella dei valori rhs devono necessariamente essere TYPE e RHS [rigo 15].
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 però è 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". Questa seconda notazione, certamente più compatta, permette di dichiarare tutte le variabili comprese nell'intervallo che va da X1 a Xn.
Possiamo notare come sulla riga relativa alla definizione della f.o. sia presente, nella colonna dei valori rhs, un punto (".") che rappresenta un valore indefinito (simile ad un null). 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.
Una volta rappresentato il problema e assegnati i nomi alle variabili, si esegue l'algoritmo del Simplesso mediante la creazione di un oggetto della classe LP e l'invocazione del metodo resolve() [righi 17-18]. Una volta eseguito il Simplesso, il metodo resolve() ritorna il tipo di soluzione trovata; se la soluzione è ottima è possibile ricavare i valori delle variabili ed il valore ottimo della funzione obiettivo. Si ricorda che in SSC, di default, le variabili di un problema di LP sono considerate, se non diversamente specificato, non negative ( ≥ 0).
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String lp_string =
" 1 3 max . \n" +
" 1 1 ge -1 \n" +
" 1 1.4 le 6 \n" +
"-5 3 eq 5";
Input lp_input = new InputString(lp_string).setInputFormat("X1-X2:double, TYPE:varstring(3), RHS:double");
LP lp = new LP(lp_input);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 1.3
Si consideri il problema di LP riportato nell'esempio precedente e
dato da:
Il problema dell'esempio precedente può essere espresso anche attraverso l'uso di vettori e matrici. Il formato di rappresentazione utilizzato è simile a quello di Apache simplex solver. In questo caso occorre definire la matrice A[][] dei coefficienti , il vettore c[] dei coefficienti della f.o. ed il vettore b[] dei valori RHS.
Definite tali entità [righi 9-14] si crea un oggetto LinearObjectiveFunction [rigo 18] che rappresenta la funzione obiettivo (il GoalType rappresenta il tipo di ottimizzazione : MAX o MIN) e gli oggetti Constraint [rigo 22] che rappresentano i vincoli. Il tipo di vincolo (LE='minore o uguale', GE='maggiore o uguale', EQ='uguale') viene specificato attraverso gli elementi dell'array delle relazioni rel[], array contenente oggetti di tipo ConsType [rigo 16]. Infine, la lista di vincoli e la funzione obiettivo sono parametri sufficienti per istanziare un oggetto della classe LP [rigo 25].
max X1 + 3X2 X1 + X2 ≥-1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 con X1, X2 ≥ 0
Il problema dell'esempio precedente può essere espresso anche attraverso l'uso di vettori e matrici. Il formato di rappresentazione utilizzato è simile a quello di Apache simplex solver. In questo caso occorre definire la matrice A[][] dei coefficienti , il vettore c[] dei coefficienti della f.o. ed il vettore b[] dei valori RHS.
Definite tali entità [righi 9-14] si crea un oggetto LinearObjectiveFunction [rigo 18] che rappresenta la funzione obiettivo (il GoalType rappresenta il tipo di ottimizzazione : MAX o MIN) e gli oggetti Constraint [rigo 22] che rappresentano i vincoli. Il tipo di vincolo (LE='minore o uguale', GE='maggiore o uguale', EQ='uguale') viene specificato attraverso gli elementi dell'array delle relazioni rel[], array contenente oggetti di tipo ConsType [rigo 16]. Infine, la lista di vincoli e la funzione obiettivo sono parametri sufficienti per istanziare un oggetto della classe LP [rigo 25].
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import static org.ssclab.pl.milp.ConsType.*;
public class Esempio {
public static void main(String[] args) throws Exception {
double A[][]={
{ 1.0 , 1.0 },
{ 1.0 , 1.4 },
{-5.0 , 3.0 } } ;
double b[]= {-1.0, 6.0 ,5.0 };
double c[]= { 1.0, 3.0 };
ConsType rel[]= {GE, LE, EQ};
LinearObjectiveFunction fo = new LinearObjectiveFunction(c, GoalType.MAX);
ListConstraints constraints = new ListConstraints();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], rel[i], b[i]));
}
LP lp = new LP(fo,constraints);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 1.4
Si consideri il seguente problema di LP :
In questo esempio la variabile X1 risulta delimitata sia inferiormente (non dallo zero) che superiormente. Nella rappresentazione del problema con il formato a coefficienti, per poter definire una variabile con tali limiti, basta aggiungere un rigo per gli upper bound e uno per i lower bound [righi 13-14]. Nel caso della variabile X2, cioè di una variabile senza limiti superiore ed inferiore, basta specificare un lower bound e un upper bound indefinito. Se si dichiara un valore indefinito su un lower bound o su un upper bound, SSC trasforma tali valori in -/+ infinito. In questo formato il valore indefinito si rappresenta con il punto (.).
È importante sottolineare che per poter impostare delle variabili libere o variabili che possono assumere valori anche in un range negativo, basta valorizzare un lower bound indefinito (.) o negativo, oppure un upper bound negativo. Ad esempio, se consideriamo la variabile X1 questa deve assumere valori maggiori di -1; ebbene introdurre un vincolo del tipo " 1 0 ge -1 \n" nella formulazione del problema (ovvero il vincolo che la variabile X1 sia maggiore di -1) non determina che la variabile X1 possa assumere valori fino a -1, ma si vincola solo il problema a soddisfare tale condizione, condizione che non potrà essere vagliata pienamente se non si rende la variabile capace di assumere anche valori negativi. Per rendere una variabile libera di variare in range negativi, si deve usare esclusivamente la notazione degli upper e lower bound. In questo esempio sia X1 che X2 sono variabili che possono assumere valori negativi (tramite le dichiarazioni ai righi 13-14).
Infine in fase di stampa della soluzione è possibile recuperare per ogni variabile gli upper ed i lower precedentemente valorizzati in fase di formulazione del problema [rigo 24].
max X1 + 3X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 con -1 ≤ X1 ≤ +1 -∞ ≤ X2 ≤ +∞
In questo esempio la variabile X1 risulta delimitata sia inferiormente (non dallo zero) che superiormente. Nella rappresentazione del problema con il formato a coefficienti, per poter definire una variabile con tali limiti, basta aggiungere un rigo per gli upper bound e uno per i lower bound [righi 13-14]. Nel caso della variabile X2, cioè di una variabile senza limiti superiore ed inferiore, basta specificare un lower bound e un upper bound indefinito. Se si dichiara un valore indefinito su un lower bound o su un upper bound, SSC trasforma tali valori in -/+ infinito. In questo formato il valore indefinito si rappresenta con il punto (.).
È importante sottolineare che per poter impostare delle variabili libere o variabili che possono assumere valori anche in un range negativo, basta valorizzare un lower bound indefinito (.) o negativo, oppure un upper bound negativo. Ad esempio, se consideriamo la variabile X1 questa deve assumere valori maggiori di -1; ebbene introdurre un vincolo del tipo " 1 0 ge -1 \n" nella formulazione del problema (ovvero il vincolo che la variabile X1 sia maggiore di -1) non determina che la variabile X1 possa assumere valori fino a -1, ma si vincola solo il problema a soddisfare tale condizione, condizione che non potrà essere vagliata pienamente se non si rende la variabile capace di assumere anche valori negativi. Per rendere una variabile libera di variare in range negativi, si deve usare esclusivamente la notazione degli upper e lower bound. In questo esempio sia X1 che X2 sono variabili che possono assumere valori negativi (tramite le dichiarazioni ai righi 13-14).
Infine in fase di stampa della soluzione è possibile recuperare per ogni variabile gli upper ed i lower precedentemente valorizzati in fase di formulazione del problema [rigo 24].
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String lp_string =
" 1 3 max . \n" +
" 1 1 ge 1 \n" +
" 1 1.4 le 6 \n" +
"-5 3 eq 5 \n" +
" 1 . upper . \n" +
"-1 . lower . \n" ;
Input lp_input = new InputString(lp_string).setInputFormat("X1-X2:double, TYPE:varstring(8), RHS:double");
LP lp = new LP(lp_input);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variabile "+var.getName() +": "+var.getLower() + " <= ["+var.getValue()+"] <= "+var.getUpper());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 1.5
Si consideri il seguente problema di LP riportato nell'esempio
precedente:
Risolviamo l'esempio precedente utilizzando il formato matriciale. Per poter rappresentare la variabile X1, che risulta delimitata sia inferiormente che superiormente, occorre aggiungere alla matrice A un rigo per gli upper bound e uno per i lower bound [righi 14-15]. Nel caso della variabile X2, ovvero di una variabile libera senza limiti , basta specificare un lower bound e un upper bound indefinito con il valore NaN.
Ricordiamo che per poter impostare delle variabili libere, ovvero delle variabili che possono assumere anche valori negativi, basta valorizzare un lower bound indefinito o negativo, oppure un upper bound negativo. In questo esempio sia X1 che X2 sono libere di assumere anche valori negativi, rispettando il lower e l'upper definiti.
Occorre poi aggiungere nel vettore delle relazioni [rigo 20] le costanti che dichiarano che gli ultimi due righi della matrice A sono relativi agli upper e lower bound (si aggiunge ConsType.UPPER e ConsType.LOWER). Infine, va aggiornata anche la dimensione del vettore b (aggiungendo due valori NaN) che deve essere uguale al numero di righi della matrice A.
max X1 + 3X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 con -1 ≤ X1 ≤ +1 -∞ ≤ X2 ≤ +∞
Risolviamo l'esempio precedente utilizzando il formato matriciale. Per poter rappresentare la variabile X1, che risulta delimitata sia inferiormente che superiormente, occorre aggiungere alla matrice A un rigo per gli upper bound e uno per i lower bound [righi 14-15]. Nel caso della variabile X2, ovvero di una variabile libera senza limiti , basta specificare un lower bound e un upper bound indefinito con il valore NaN.
Ricordiamo che per poter impostare delle variabili libere, ovvero delle variabili che possono assumere anche valori negativi, basta valorizzare un lower bound indefinito o negativo, oppure un upper bound negativo. In questo esempio sia X1 che X2 sono libere di assumere anche valori negativi, rispettando il lower e l'upper definiti.
Occorre poi aggiungere nel vettore delle relazioni [rigo 20] le costanti che dichiarano che gli ultimi due righi della matrice A sono relativi agli upper e lower bound (si aggiunge ConsType.UPPER e ConsType.LOWER). Infine, va aggiornata anche la dimensione del vettore b (aggiungendo due valori NaN) che deve essere uguale al numero di righi della matrice A.
import org.ssclab.log.SscLogger;
import static org.ssclab.pl.milp.ConsType.*;
import org.ssclab.pl.milp.*;
import static org.ssclab.pl.milp.LP.NaN;
public class Esempio {
public static void main(String[] args) throws Exception {
double A[][]={
{ 1.0 , 1.0 },
{ 1.0 , 1.4 },
{-5.0 , 3.0 },
{ 1.0 , NaN },
{-1.0 , NaN }} ;
double b[]= { 1.0, 6.0 ,5.0, NaN, NaN };
double c[]= { 1.0, 3.0 };
ConsType rel[]= {GE, LE, EQ, UPPER, LOWER};
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ListConstraints constraints = new ListConstraints();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], rel[i], b[i]));
}
LP lp = new LP(f,constraints);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 1.6
Si consideri il seguente problema di LP :
Vogliamo risolvere questo problema usando ancora il formato testuale. Questo problema è analogo al problema 1.1, con la sola aggiunta di upper e lower bound. Nel formato testo per definire gli upper u e lower bound l occorre aggiunge rispettivamente un rigo per ogni variabile da limitare [righi 14-15] con dichiarazioni di questo tipo : " u ≤ x ≤ l " , " x ≤ l " , " x ≥ u ".
Ricordiamo che per rendere una variabile libera o una variabile che può assumere valori in un range negativo, occorre valorizzare un lower bound a -infinito (il +infinito e il -infinito si rapresentano con "." nel formato testo) o negativo, oppure un upper bound negativo (vedi esempio 1.4). Nel formato testo dichiarazioni di upper e lower bound come quelle dei righi [14-15] permettono di far assumere alla variabile valori negativi.
Infine in fase di stampa della soluzione è possibile recuperare per ogni variabile [rigo 23] gli upper ed i lower precedentemente valorizzati in fase di formulazione del problema.
min 3Y + 2X2 + 4Z + 7X4 + 8X5 5Y + 2X2 + 3X4 ≥ 9 3Y + X2 + Z + 5X5 = 12 6Y + 3X2 + 4Z + 5X4 ≤ 124 Y + 3X2 + 3X4 + 6X5 ≤ 854 con Y, X4, X5 ≥ 0 -1 ≤ X2 ≤ +6 -∞ ≤ Z ≤ +∞
Vogliamo risolvere questo problema usando ancora il formato testuale. Questo problema è analogo al problema 1.1, con la sola aggiunta di upper e lower bound. Nel formato testo per definire gli upper u e lower bound l occorre aggiunge rispettivamente un rigo per ogni variabile da limitare [righi 14-15] con dichiarazioni di questo tipo : " u ≤ x ≤ l " , " x ≤ l " , " x ≥ u ".
Ricordiamo che per rendere una variabile libera o una variabile che può assumere valori in un range negativo, occorre valorizzare un lower bound a -infinito (il +infinito e il -infinito si rapresentano con "." nel formato testo) o negativo, oppure un upper bound negativo (vedi esempio 1.4). Nel formato testo dichiarazioni di upper e lower bound come quelle dei righi [14-15] permettono di far assumere alla variabile valori negativi.
Infine in fase di stampa della soluzione è possibile recuperare per ogni variabile [rigo 23] gli upper ed i lower precedentemente valorizzati in fase di formulazione del problema.
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 +4Z +7x4 +8X5 \n"+
" 5Y +2x2 +3X4 >= 9 \n"+
" 3Y + X2 + Z +5X5 = 12 \n"+
" 6Y +3.0x2 +4Z +5X4 <= 124\n"+
" Y +3x2 +3X4 +6X5 <= 854\n"+
"-1<= x2 <= 6\n"+
". <= z <= .\n";
LP lp = new LP(pl_string);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variabile "+var.getName() +": "+var.getLower() + " <= ["+var.getValue()+"] <= "+var.getUpper());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 1.7
Si consideri il seguente problema di LP riportato nell'esempio
1.4:
L'esempio 1.4 può essere rappresentato con un quarto formato denominato "sparso" [righi 14-37]. Quando il motore di elaborazione analizza una riga con TYPE valorizzato (diverso da '.'), esso inizia a definire una nuova entità e le assegna un marcatore, specificato nella colonna ROW_. Questo marcatore rappresenta il nome dell'entità, che può essere un vincolo o la funzione obiettivo. In particolare, 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 è 'EQ' (=), 'LE' (≤) o 'GE' (≥), inizia la definizione di un vincolo ed asssegna a queste entità un nome (il marcatore specificato in ROW_). La colonna TYPE può assumere uno dei seguenti valori: EQ, LE, GE, UPPER, LOWER, MAX, MIN.
Successivamente, le variabili del problema vengono specificate valorizzando la colonna COL_, che identifica la variabile stessa, e indicando il coefficiente corrispondente nella colonna COEF. 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 sull'entità corrispondente al marcatore presente in ROW_.
Oltre al nome della variabili (scelte dallo sviluppatore), nella colonna COL_ può essere presente anche il valore "RHS", utilizzato per definire i termini noti (il lato destro) dei vincoli. Se i nomi delle variabili possono essere scelti liberamente, il nome per i valori rhs deve necessariamente essere indicato con la notazione "RHS".
Definito il problema occorre dichiarare nel formato di lettura [rigo 40] il nome e il tipo (con la relativa lunghezza) delle quattro colonne richieste da questo formato : TYPE, COL_, ROW_ e COEF. I nomi delle variabili da assegnare alle corrispettive colonne devono essere necessariamente TYPE, COL_, ROW_ e COEF.
Per poter istanziare con questo formato un oggetto LP occorre passare come argomento al costruttore la costante FormatType.SPARSE per informare l'oggetto LP del tipo di formato utilizzato [rigo 42]. Questo formato è particolarmente indicato per prelevare problemi presenti in tabelle di database, in quanto la struttura della tabella richiesta è sempre la stessa: basta che questa definisca le colonne TYPE, COL_, ROW_ e COEF.
Occorre infine ricordare 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 nome di un rigo contemporaneamente in minuscolo e in maiuscolo, nell'ambito di una stessa formulazione, significa dichiarare due nomi (e quindi due righi ) distinti.
max X1 + 3X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 con -1 ≤ X1 ≤ +1 -∞ ≤ X2 ≤ +∞
L'esempio 1.4 può essere rappresentato con un quarto formato denominato "sparso" [righi 14-37]. Quando il motore di elaborazione analizza una riga con TYPE valorizzato (diverso da '.'), esso inizia a definire una nuova entità e le assegna un marcatore, specificato nella colonna ROW_. Questo marcatore rappresenta il nome dell'entità, che può essere un vincolo o la funzione obiettivo. In particolare, 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 è 'EQ' (=), 'LE' (≤) o 'GE' (≥), inizia la definizione di un vincolo ed asssegna a queste entità un nome (il marcatore specificato in ROW_). La colonna TYPE può assumere uno dei seguenti valori: EQ, LE, GE, UPPER, LOWER, MAX, MIN.
Successivamente, le variabili del problema vengono specificate valorizzando la colonna COL_, che identifica la variabile stessa, e indicando il coefficiente corrispondente nella colonna COEF. 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 sull'entità corrispondente al marcatore presente in ROW_.
Oltre al nome della variabili (scelte dallo sviluppatore), nella colonna COL_ può essere presente anche il valore "RHS", utilizzato per definire i termini noti (il lato destro) dei vincoli. Se i nomi delle variabili possono essere scelti liberamente, il nome per i valori rhs deve necessariamente essere indicato con la notazione "RHS".
Definito il problema occorre dichiarare nel formato di lettura [rigo 40] il nome e il tipo (con la relativa lunghezza) delle quattro colonne richieste da questo formato : TYPE, COL_, ROW_ e COEF. I nomi delle variabili da assegnare alle corrispettive colonne devono essere necessariamente TYPE, COL_, ROW_ e COEF.
Per poter istanziare con questo formato un oggetto LP occorre passare come argomento al costruttore la costante FormatType.SPARSE per informare l'oggetto LP del tipo di formato utilizzato [rigo 42]. Questo formato è particolarmente indicato per prelevare problemi presenti in tabelle di database, in quanto la struttura della tabella richiesta è sempre la stessa: basta che questa definisca le colonne TYPE, COL_, ROW_ e COEF.
Occorre infine ricordare 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 nome di un rigo contemporaneamente in minuscolo e in maiuscolo, nell'ambito di una stessa formulazione, significa dichiarare due nomi (e quindi due righi ) distinti.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String lp_sparse =
// TYPE COL_ ROW_ COEF
" MAX . costo . \n" +
" GE . row1 . \n" +
" LE . row2 . \n" +
" EQ . row3 . \n" +
" UPPER . lim_sup . \n" +
" LOWER . lim_inf . \n" +
" . X1 costo 1 \n" +
" . X1 row1 1 \n" +
" . X1 row2 1 \n" +
" . X1 row3 -5 \n" +
" . X1 lim_sup 1 \n" +
" . X1 lim_inf -1 \n" +
" . X2 costo 3 \n" +
" . X2 row1 1 \n" +
" . X2 row2 1.4 \n" +
" . X2 row3 3 \n" +
" . X2 lim_sup . \n" +
" . X2 lim_inf . \n" +
" . RHS row1 1 \n" +
" . RHS row2 6 \n" +
" . RHS row3 5 \n" ;
Input lp_input = new InputString(lp_sparse)
.setInputFormat("TYPE:varstring(5),COL_:varstring(3),ROW_:varstring(7),COEF:double");
LP lp = new LP(lp_input,FormatType.SPARSE);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 1.8
Si consideri il seguente problema di LP :
In questo caso vogliamo risolvere un problema di LP la cui formulazione si trova in un file di testo (.txt). Chiamiamo tale file pl_problem.txt e utilizziamo, per la rappresentazione del problema, il formato a coefficienti. Nel file pl_problem.txt avremo il seguente contenuto:
min 3Y1 + Y2 + 4Y3 + 7Y4 + 8Y5 5Y1 + 2Y2 + 3Y4 ≥ 9 3Y1 + Y2 + Y3 + 5Y5 ≥ 12 6Y1 + 3Y2 + 4Y3 + 5Y4 ≤ 124 1Y1 + 3Y2 + 3Y4 + 6Y5 ≤ 854 con Y1, Y4, Y5 ≥ 0 0 ≤ Y2 ≤ +6 1 ≤ Y3 ≤ +∞
In questo caso vogliamo risolvere un problema di LP la cui formulazione si trova in un file di testo (.txt). Chiamiamo tale file pl_problem.txt e utilizziamo, per la rappresentazione del problema, il formato a coefficienti. Nel file pl_problem.txt avremo il seguente contenuto:
3 1 4 7 8 min . 5 2 0 3 0 ge 9 3 1 1 0 5 ge 12 6 3 4 5 0 le 124 1 3 0 3 6 le 854 . 6 . . . upper . 0 0 1 0 0 lower .Definito tale file di testo, occorre informare SSC che il problema è contenuto nel file pl_problem.txt [rigo 9] creando una istanza della classe InputFile. Se si hanno un numero significativo di variabili (in questo caso solo 5, ma possono essere molte di più) queste si possono dichiarare mediante notazione ad intervallo [rigo 10], dove con la sintassi "Y1-Y5:double" si dichiarano 5 variabili distinte (Y1, Y2, Y3, Y4, Y5) di tipo double (naturalmente possono essere assegnati altri nomi come Z1-Z5 etc,etc).
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.InputFile;
public class Esempio {
public static void main(String[] args) throws Exception {
InputFile input = new InputFile("c:/dati_pl/pl_problem.txt");
input.setInputFormat("Y1-Y5:double, TYPE:varstring(10), RHS:double");
LP lp=new LP(input);
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);
}
}
Esempio 1.9
Si consideri il seguente problema di LP riportato nell'esempio 1.7:
In questo esempio vogliamo recuperare il problema, formulato nel formato sparso, da una tabella di un database (RDBMS) Oracle. Ricordiamo che nel formato sparso l'input necessario per la risoluzione di un problema di LP richiede la presenza delle colonne TYPE, ROW_, COL_ e COEF. Nella tabella inseriamo anche il campo ID_PROBLEM in modo da poter inserire in tale tabella una moltitudine di problemi di LP identificabili tramite tale campo. Chiamiamo PL_PROBLEM la tabella Oracle che dovrà contenere tali campi; questa tabella può essere creata con la seguente istruzione DDL (Data Definition Language):
L'invocazione di addLibrary() [rigo 18] permette di aggiunge alla sessione SSC corrente una libreria (di nome "DB_ORACLE") che rappresenta una connessione al DB Oracle. Dopo tale invocazione il metodo addLibrary() ritorna un oggetto di tipo Library che rappresenta una interfaccia al database. Da questa interfaccia possiamo [rigo 20] ottenere, tramite una query SQL, un oggetto di tipo Input che fa riferimento ai record relativi al problema inserito nella tabella e precisamente quello con identificativo 13. Una volta ottenuto tale input possiamo passarlo al costruttore LP [rigo 24] ed eseguire il Simplesso.
Naturalmente, le colonne presenti nel database possono anche non chiamarsi TYPE, ROW_, COL_ e COEF; se hanno nomi diversi in fase di estrazione dei dati, tramite select SQL, è possibile rinominare le colonne dei campi (ad esempio: SELECT TIPO as TYPE, RIGA as ROW_, COLONNA as COL_, COEFFICIENTI AS COEF from MyTable) cambiandoli nei nomi richiesti dal'oggetto LP.
È da notare che nel costruttore della classe LP oltre all'oggetto di tipo Input che contiene un riferimento ai record relativi alla formulazione del problema, viene anche passato come secondo argomento [rigo 24] la sessione SSC precedentemente creata, questo per non far istanziare all'oggetto LP una seconda sessione del tutto inutile. Infine, come terzo argomento, viene passata una costante (FormatType.SPARSE) che esplicita con quale formato (sparso) è stato formulato il problema. Naturalmente, al posto del database Oracle puo essere usato qualsiasi altro RDBMS del quale si dispone di un driver JDBC.
max X1 + 3X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 con -1 ≤ X1 ≤ +1 -∞ ≤ X2 ≤ +∞
In questo esempio vogliamo recuperare il problema, formulato nel formato sparso, da una tabella di un database (RDBMS) Oracle. Ricordiamo che nel formato sparso l'input necessario per la risoluzione di un problema di LP richiede la presenza delle colonne TYPE, ROW_, COL_ e COEF. Nella tabella inseriamo anche il campo ID_PROBLEM in modo da poter inserire in tale tabella una moltitudine di problemi di LP identificabili tramite tale campo. Chiamiamo PL_PROBLEM la tabella Oracle che dovrà contenere tali campi; questa tabella può essere creata con la seguente istruzione DDL (Data Definition Language):
CREATE TABLE "PL_PROBLEM"
("TYPE" VARCHAR2(8),
"COL_" VARCHAR2(15),
"ROW_" VARCHAR2(15),
"COEF" FLOAT(24),
"ID_PROBLEM" NUMBER(4)
)
Infine, inseriamo nella tabella i seguenti record (per null si intende il valore
null non la stringa "null"):
MAX null costo null 13 GE null row1 null 13 LE null row2 null 13 EQ null row3 null 13 UPPER null lim_sup null 13 LOWER null lim_inf null 13 null X1 costo 1 13 null X1 row1 1 13 null X1 row2 1 13 null X1 row3 -5 13 null X1 lim_sup 1 13 null X1 lim_inf -1 13 null X2 costo 3 13 null X2 row1 1 13 null X2 row2 1.4 13 null X2 row3 3 13 null X2 lim_sup null 13 null X2 lim_inf null 13 null RHS row1 1 13 null RHS row2 6 13 null RHS row3 5 13Per 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 [righi 40-47]. Una volta ottenuta una connessione al DB, tramite l'oggetto Connection è possibile, da SSC, accedere al DB attraverso il concetto di libreria. SSC per poter allocare librerie necessita che venga creata una sessione di lavoro SSC [riga 17]. Una sessione SSC rappresenta l'ambiente nel quale SSC viene eseguito. Negli esempi precedenti la creazione di una sessione non era necessaria in quanto l'oggetto LP crea e usa una sua sessione SSC implicita.
L'invocazione di addLibrary() [rigo 18] permette di aggiunge alla sessione SSC corrente una libreria (di nome "DB_ORACLE") che rappresenta una connessione al DB Oracle. Dopo tale invocazione il metodo addLibrary() ritorna un oggetto di tipo Library che rappresenta una interfaccia al database. Da questa interfaccia possiamo [rigo 20] ottenere, tramite una query SQL, un oggetto di tipo Input che fa riferimento ai record relativi al problema inserito nella tabella e precisamente quello con identificativo 13. Una volta ottenuto tale input possiamo passarlo al costruttore LP [rigo 24] ed eseguire il Simplesso.
Naturalmente, le colonne presenti nel database possono anche non chiamarsi TYPE, ROW_, COL_ e COEF; se hanno nomi diversi in fase di estrazione dei dati, tramite select SQL, è possibile rinominare le colonne dei campi (ad esempio: SELECT TIPO as TYPE, RIGA as ROW_, COLONNA as COL_, COEFFICIENTI AS COEF from MyTable) cambiandoli nei nomi richiesti dal'oggetto LP.
È da notare che nel costruttore della classe LP oltre all'oggetto di tipo Input che contiene un riferimento ai record relativi alla formulazione del problema, viene anche passato come secondo argomento [rigo 24] la sessione SSC precedentemente creata, questo per non far istanziare all'oggetto LP una seconda sessione del tutto inutile. Infine, come terzo argomento, viene passata una costante (FormatType.SPARSE) che esplicita con quale formato (sparso) è stato formulato il problema. Naturalmente, al posto del database Oracle puo essere usato qualsiasi altro RDBMS del quale si dispone di un driver JDBC.
import org.ssclab.context.Context;
import org.ssclab.context.Session;
import org.ssclab.library.Library;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.Input;
import java.sql.Connection;
import oracle.jdbc.pool.OracleDataSource;
public class Esempio {
public static void main(String[] args) throws Exception {
Session session = null;
try {
session = Context.createNewSession();
Library library_oracle=session.addLibrary("DB_ORACLE", connOracle());
Input select_id_13=library_oracle.getInputFromSQLQuery(
"select TYPE, COL_ , ROW_, COEF from PL_PROBLEM where ID_PROBLEM=13" );
LP lp = new LP(select_id_13,session,FormatType.SPARSE);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
}
finally {
if(session!=null) session.close();
}
}
private static Connection connOracle() throws Exception {
OracleDataSource ods = new OracleDataSource();
String URL = "jdbc:oracle:thin:@//169.254.251.50:1521/XE";
ods.setURL(URL);
ods.setUser("system");
ods.setPassword("HAL9000");
return ods.getConnection();
}
}
Esempio 1.10
Nell'esempio sottostante si riporta un semplice problema di LP che
vuole evidenziare quali sono i valori che il
metodo resolve() può restituire a seconda che il problema di
LP :
a) restituisca una soluzione ottima
b) non ammetta soluzioni ammissibili
c) abbia ottimo illimitato
d) raggiunga il numero massimo di iterazioni possibili
e) venga restituita una soluzione ammissibile al posto di una soluzione ottima
Se l'esigenza è quella di ottenere una soluzione ammissibile non necessariamente ottima (caso e), basta invocare il metodo setJustTakeFeasibleSolution() passandogli il valore "true" (rigo 28). Questa opzione permette di far eseguire solo la prima fase del simplesso e di ottenere una prima soluzione (basica) ammissibile. In questo caso il valore restituito dal metodo resolve() (nel caso esista una soluzione ammissibile) sarà SolutionType.FEASIBLE.
Infine ricordiamo che il numero massimo di iterazioni possibili può essere modificato dall'analista [rigo 27], il numero massimo di default è 100.000.000.
a) restituisca una soluzione ottima
b) non ammetta soluzioni ammissibili
c) abbia ottimo illimitato
d) raggiunga il numero massimo di iterazioni possibili
e) venga restituita una soluzione ammissibile al posto di una soluzione ottima
Se l'esigenza è quella di ottenere una soluzione ammissibile non necessariamente ottima (caso e), basta invocare il metodo setJustTakeFeasibleSolution() passandogli il valore "true" (rigo 28). Questa opzione permette di far eseguire solo la prima fase del simplesso e di ottenere una prima soluzione (basica) ammissibile. In questo caso il valore restituito dal metodo resolve() (nel caso esista una soluzione ammissibile) sarà SolutionType.FEASIBLE.
Infine ricordiamo che il numero massimo di iterazioni possibili può essere modificato dall'analista [rigo 27], il numero massimo di default è 100.000.000.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.LP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Esempio {
public static void main(String[] args) throws Exception {
String lp_string =
"5 4 1 3 max . \n" +
"4 3 1 1 ge 2 \n" +
"1 -2 1 -1 le 2 \n" +
"3 2 1 1.4 le 6 \n" +
"9 8 4 1.7 le 7 \n" +
"5 3 -1 2.4 le 9 \n" +
"3 -2 -5 3 le 5 ";
InputString lp_input = new InputString(lp_string);
lp_input.setInputFormat("V1-V4:double, TYPE:varstring(8), RHS:double");
LP lp = new LP(lp_input);
SscLogger.log("Numero di iterazioni di default:"+lp.getNumMaxIteration());
lp.setNumMaxIteration(5);
lp.setJustTakeFeasibleSolution(true); //imposto la ricerca di una soluzione ammissibile ,
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.FEASIBLE) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore assunto dalla soluzione ammissibile sulla f.o.:"+solution.getValue());
}
else if(solution_type==SolutionType.VUOTUM) {
SscLogger.log("La fase 1 del simplesso non ha trovato soluzioni ammissibili:("+solution_type+")");
}
else if(solution_type==SolutionType.ILLIMITATUM) {
SscLogger.log("Ottimo illimitato:("+solution_type+")");
}
else if(solution_type==SolutionType.MAX_ITERATIUM) {
SscLogger.log("Raggiunto il numero massimo di iterazioni:("+solution_type+")");
}
else if(solution_type==SolutionType.OPTIMUM) {
//questa sezione non verrà mai raggiunta in quanto avendo impostato
//setJustTakeFeasibleSolution(true), il simplesso può solo restituire soluzioni ammissibili
}
}
}
Esempio 1.11
Nell'esempio sottostante si vuole risolvere il problema già affrontato nell'esercizio 1.6, con la particolarità
che la formulazione del problema (utilizzando il formato testuale) è memorizzata in un file. Chiamiamo questo file
pl_problem.txt. Il file menzionato conterrà il seguente contenuto:
Nel codice sottostante sono stati aggiunti delle istruzioni per recuperare le informazioni relative ai vincoli, come il nome associato al vincolo e il tipo di vincolo. Va però evidenziato che è possibile recuperare anche il valore che la parte LHS di ogni vincolo (la parte alla sinistra della relazione) assume valorizzando le variabili incognite con la soluzione ottima. Il valore LHS viene poi confrontato con il corrispettivo valore RHS [righi 18-19]. Specifichiamo che le quantià LHS e RHS di cui si parla in questo specifico caso, dato un problema di programmazione lineare AX <=> b, sono date da AX (parte LHS) e b (RHS). Per cui se nella definizione del problema inseriamo delle variabili sulla destra del segno di disuguaglianza/uguaglianza, queste non saranno considerate come parte RHS, ma raggruppate nella forma: AX (parte LHS) e b (RHS).
min: 3Y +2x2 +4Z +7x4 +8X5 row1:5Y +2x2 +3X4 >= 9 row2:3Y + X2 +Z +5X5 = 12 Vin1:6Y +3.0x2 +4Z +5X4 <= 124 vin2: Y +3x2 +3X4 +6X5 <= 854 -1 <= x2 <= 6 . <= z <= .A differenza della formulazione dell'esempio 1.6 in questo caso ad ogni vincolo abbiamo anche associato una etichetta (nome del vincolo) che si inserisce anteponendo ad ogni vincolo un nome seguito da due punti.
Nel codice sottostante sono stati aggiunti delle istruzioni per recuperare le informazioni relative ai vincoli, come il nome associato al vincolo e il tipo di vincolo. Va però evidenziato che è possibile recuperare anche il valore che la parte LHS di ogni vincolo (la parte alla sinistra della relazione) assume valorizzando le variabili incognite con la soluzione ottima. Il valore LHS viene poi confrontato con il corrispettivo valore RHS [righi 18-19]. Specifichiamo che le quantià LHS e RHS di cui si parla in questo specifico caso, dato un problema di programmazione lineare AX <=> b, sono date da AX (parte LHS) e b (RHS). Per cui se nella definizione del problema inseriamo delle variabili sulla destra del segno di disuguaglianza/uguaglianza, queste non saranno considerate come parte RHS, ma raggruppate nella forma: AX (parte LHS) e b (RHS).
import java.nio.file.Paths;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
LP lp = new LP(Paths.get("C:\\pl_problem.txt"));
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());
}
for(SolutionConstraint sol_constraint: soluzione.getSolutionConstraint()) {
SscLogger.log("Vincolo "+sol_constraint.getName()+" : valore="+sol_constraint.getValue() +
"[ "+sol_constraint.getRel()+" "+sol_constraint.getRhs()+" ]" );
}
SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 1.12
Si consideri il seguente problema di LP identico all'esempio 1.9:
In questo esempio vogliamo recuperare il problema, formulato nel formato sparso, da un file di testo chiamato problem.txt contenete il seguente listato:
max X1 + 3X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 con -1 ≤ X1 ≤ +1 -∞ ≤ X2 ≤ +∞
In questo esempio vogliamo recuperare il problema, formulato nel formato sparso, da un file di testo chiamato problem.txt contenete il seguente listato:
MAX . costo . GE . row1 . LE . row2 . EQ . row3 . UPPER . lim_sup . LOWER . lim_inf . . X1 costo 1 . X1 row1 1 . X1 row2 1 . X1 row3 -5 . X1 lim_sup 1 . X1 lim_inf -1 . X2 costo 3 . X2 row1 1 . X2 row2 1.4 . X2 row3 3 . X2 lim_sup . . X2 lim_inf . . RHS row1 1 . RHS row2 6 . RHS row3 5E' da notare che nel costruttore della classe LP viene passato come argomento un oggetto di tipo InputFile che fa riferimento al file contenente il problema.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.InputFile;
public class Esempio {
public static void main(String[] args) throws Exception {
InputFile input_sparse = new InputFile("C:/ssc_project/problem.txt");
input_sparse.setInputFormat("TYPE:varstring(5), COL_:varstring(3) , ROW_:varstring(7), COEF:double");
LP lp = new LP(input_sparse,FormatType.SPARSE);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 1.13
Nell'esempio sottostante si riporta un problema di LP generato con
numeri pseudocausali, con la particolarità che al vettore b vengono fatti assumere valori dell'ordine di
decine di milioni. La conseguenza di lavorare con numeri di elevata grandezza potrebbe non far convergere
la fase 1 del simplesso.
In questo particolare caso se non si modifica
la tolleranza ε del valore ottimo z della f.o relativo alla fase 1 la risoluzione del problema potrebbe non dare come risultato soluzioni ammissibili.
In altre parole, alla fine della fase 1, se | z | > ε allora il problema non ammette soluzioni.
Per ovviare a questo, nell'esempio riportato, la tolleranza viene aumentata da 1E-8 (valore di default) a 1E-5 [rigo 31] per far si che , a causa
della manipolazione di numeri di grandezza elevata, possa avvenire che | z | < ε.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import java.util.ArrayList;
import java.util.Random;
public class Esempio {
public static void main(String arg[]) throws Exception {
final int M = 445; // rows
final int N = 345; // cols
Random random = new Random();
double[] c = new double[N];
double[] b = new double[M];
double[][] A = new double[M][N];
for (int j = 0; j < N; j++) c[j] = (double) (random.nextInt(20));
for (int i = 0; i < M; i++) b[i] = (double) random.nextInt(100000000);
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++) A[i][j] = (double) random.nextInt(10);
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], ConsType.LE, b[i]));
}
LP lp = new LP(f,constraints);
lp.setCEpsilon(EPSILON._1E_M5);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("Valore f.o. :"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima. Tipo di soluzione:"+solution_type);
}
}
Esempio 1.14
Si consideri il seguente problema di LP:
Per risolvere questo problema (identico al problema 1.1) con una implementazione del simplesso parallelo, occorre semplicemente aggiungere l'istruzione presente nel rigo 24. Con questa istruzione specifichiamo il numero di thread da utilizare per eseguire una istanza del simplesso parallelo (in questo caso 4). Tra i valori selezionabili vi è anche il valore LPThreadsNumber.AUTO, con il quale si delega al sistema la scelta del numero di thread da utilizzare per l'esecuzione del simplesso parallelo. Occorre ricordare che vantaggi sulla durata del metodo si ottengono con almeno 4 o più core fisici e che ha senso utilizzare questa tecnica solo se il problema presenta un numero di variabili/vincoli dell'ordine dei migliaia.
max X1 + 3X2 X1 + X2 ≥-1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 con X1, X2 ≥ 0
Per risolvere questo problema (identico al problema 1.1) con una implementazione del simplesso parallelo, occorre semplicemente aggiungere l'istruzione presente nel rigo 24. Con questa istruzione specifichiamo il numero di thread da utilizare per eseguire una istanza del simplesso parallelo (in questo caso 4). Tra i valori selezionabili vi è anche il valore LPThreadsNumber.AUTO, con il quale si delega al sistema la scelta del numero di thread da utilizzare per l'esecuzione del simplesso parallelo. Occorre ricordare che vantaggi sulla durata del metodo si ottengono con almeno 4 o più core fisici e che ha senso utilizzare questa tecnica solo se il problema presenta un numero di variabili/vincoli dell'ordine dei migliaia.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.LP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
import org.ssclab.pl.milp.util.LPThreadsNumber;
public class Esempio {
public static void main(String[] args) throws Exception {
String lp_string =
" 1 3 max . \n" +
" 1 1 ge -1 \n" +
" 1 1.4 le 6 \n" +
"-5 3 eq 5";
InputString lp_input = new InputString(lp_string);
lp_input.setInputFormat("X1:double, X2:double, TYPE:varstring(3), RHS:double");
LP lp = new LP(lp_input);
lp.setThreadsNumber(LPThreadsNumber.N_4);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 1.15
Si consideri il seguente problema di LP:
Per risolvere questo problema utilizziamo un ArrayList per memorizzare le singole righe dove è formulato il problema.
min 3Y + 2X2 + 4Z + 7X4 + 8X5 5Y + 2X2 ≥ 9 - 3X4 3Y + X2 + Z + 5X5 = 12 6Y + 3X2 + 4Z ≤ 124 - 5X4 Y + 3X2 + 6X5 ≤ 854 - 3X4 con Y, X2, Z3, X4, X5 ≥ 0
Per risolvere questo problema utilizziamo un ArrayList per memorizzare le singole righe dove è formulato il problema.
import java.util.ArrayList;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
ArrayList< String > constraints = new ArrayList< String >();
constraints.add("min: 3Y +2x2 +4Z +7x4 +8X5 ");
constraints.add(" 5Y +2x2 +3X4 >= 9");
constraints.add(" 3Y + X2 + Z +5X5 = 12");
constraints.add(" 6Y +3x2 +4Z +5X4 <= 124");
constraints.add(" Y +3x2 +3X4 +6X5 <= 854");
LP lp = new LP(constraints);
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);
}
}
Esempio 1.16
Si consideri il seguente problema di LP :
Vogliamo risolvere questo problema usando un nuovo formato di rappresentazione che permette di formulare il problema tramite un oggetto JSON. In questo formato la funzione obiettivo deve essere espressa come un oggetto avente chiave "objective" [riga 12], mentre i vincoli vanno inseriti come array di oggetti nella chiave json 'constraints' [riga 22]. Infine gli upper e i lower bounds vanno inseriti nell'oggetto avente chiave "bounds". Possiamo notare come sia possibile dare dei nomi ai vincoli tramite la chiave "name" [riga 31].
Ricordiamo che in questo formato di rappresentazione di un problema di LP occorre scrivere sia le chiavi ("objective","coefficients","constraints", etc) che i valori ("max","min","eq", etc) in minuscolo. Al contrario i nomi da dare alle variabili non sono case-sensitive, per cui "X3" e "x3" rappresentano la stessa variabile. Naturalmente, i nomi dei vincoli possono esssere scritti in maiuscolo o munuscolo o un mix, ricordiamo però che questi sono case-sensitive.
Secondo le specifiche JSON, le chiavi devono essere univoche. Ad esempio nell'oggetto che definisce la funzione obiettivo (quello avente sezione "objective"), una variabile può comparire solo una volta affinchè siano soddisfatte le regole legate alla corretta compilazione di un JSON.
È importante precisare che se si definisce un lower bound negativo, come in questo caso, la variabile interessata (la Y) non è più soggetta ai vincoli di non negatività. Inoltre, 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 JSON il valore indefinito si rappresenta con il null (senza apici).
Uno dei vantaggi di questo formato è che se una variabile non è presente in un vincolo o nella funzione obiettivo, questa può essere tralasciata, a differenza del formato matriciale o a coefficienti dove deve essere rappresentata con un coefficiente uguale a zero. Si ricorda che in SSC, di default, le variabili di un problema di LP sono considerate, se non diversamente specificato, non negative (≥ 0).
Una volta rappresentato il problema, occorre creare un oggetto delle classe JsonProblem, passandogli come argomento la stringa contenente il JSON: questo oggetto è sufficiente per istanziare un oggetto della classe LP ed eseguire in Simplesso. Una volta eseguito il Simplesso, il metodo resolve() ritorna il tipo di soluzione trovata; se la soluzione è ottima è possibile ricavare i valori delle variabili ed il valore ottimo della funzione obiettivo.
min 3Y + 2X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 - 3X4 ≥ 9 3Y + X2 + X3 + 5X5 = 12 6Y + 3X2 + 4X3 - 5X4 ≤ 124 con X3, X4, X5 ≥ 0 -1 ≤ Y ≤ +4 -∞ ≤ X2 ≤ +5
Vogliamo risolvere questo problema usando un nuovo formato di rappresentazione che permette di formulare il problema tramite un oggetto JSON. In questo formato la funzione obiettivo deve essere espressa come un oggetto avente chiave "objective" [riga 12], mentre i vincoli vanno inseriti come array di oggetti nella chiave json 'constraints' [riga 22]. Infine gli upper e i lower bounds vanno inseriti nell'oggetto avente chiave "bounds". Possiamo notare come sia possibile dare dei nomi ai vincoli tramite la chiave "name" [riga 31].
Ricordiamo che in questo formato di rappresentazione di un problema di LP occorre scrivere sia le chiavi ("objective","coefficients","constraints", etc) che i valori ("max","min","eq", etc) in minuscolo. Al contrario i nomi da dare alle variabili non sono case-sensitive, per cui "X3" e "x3" rappresentano la stessa variabile. Naturalmente, i nomi dei vincoli possono esssere scritti in maiuscolo o munuscolo o un mix, ricordiamo però che questi sono case-sensitive.
Secondo le specifiche JSON, le chiavi devono essere univoche. Ad esempio nell'oggetto che definisce la funzione obiettivo (quello avente sezione "objective"), una variabile può comparire solo una volta affinchè siano soddisfatte le regole legate alla corretta compilazione di un JSON.
È importante precisare che se si definisce un lower bound negativo, come in questo caso, la variabile interessata (la Y) non è più soggetta ai vincoli di non negatività. Inoltre, per poter dichiarare variabili libere, ovvero variabili senza limite inferiore (il limite inferiore non sarà più lo zero ma
Uno dei vantaggi di questo formato è che se una variabile non è presente in un vincolo o nella funzione obiettivo, questa può essere tralasciata, a differenza del formato matriciale o a coefficienti dove deve essere rappresentata con un coefficiente uguale a zero. Si ricorda che in SSC, di default, le variabili di un problema di LP sono considerate, se non diversamente specificato, non negative (≥ 0).
Una volta rappresentato il problema, occorre creare un oggetto delle classe JsonProblem, passandogli come argomento la stringa contenente il JSON: questo oggetto è sufficiente per istanziare un oggetto della classe LP ed eseguire in Simplesso. Una volta eseguito il Simplesso, il metodo resolve() ritorna il tipo di soluzione trovata; se la soluzione è ottima è possibile ricavare i valori delle variabili ed il valore ottimo della funzione obiettivo.
import org.ssclab.log.*;
import org.ssclab.pl.milp.*;
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 pl_json = """
{
"objective": {
"type": "min",
"coefficients": {
"Y": 3,
"X2": 2,
"X3": 4,
"X4": 7,
"X5": 8
}
},
"constraints": [
{
"coefficients": {
"Y": 5,
"X2": 2,
"X4":-3
},
"relation": "ge",
"rhs": 9,
"name":"VINCOLO1"
},
{
"coefficients": {
"Y": 3,
"X2": 1,
"X3": 1,
"X5": 5
},
"relation": "eq",
"rhs": 12,
"name":"VINCOLO2"
},
{
"coefficients": {
"Y": 6,
"X2": 3,
"X3": 4,
"X4":-5
},
"relation": "le",
"rhs": 124,
"name":"VINCOLO3"
}
],
"bounds": {
"Y": {
"lower": -1,
"upper": 4
},
"X2": {
"lower": null,
"upper": 5
}
}
}""";
LP lp = new LP(new JsonProblem(pl_json));
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);
}
}
Esempio 1.17
Si consideri il seguente problema di LP :
In questo caso vogliamo risolvere un problema di LP la cui formulazione si trova in un file esterno JSON. Chiamiamo tale file pl_problem.json. Nel file avremo il seguente contenuto:
Per poter referenziare il file json occorre semplicemente creare una istanza della classe JsonProblem, passandogli come argomento un oggetto Path contenente il percorso di dove è situato il file [riga 9].
min 3Y + 2X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 - 3X4 ≥ 9 3Y + X2 + X3 + 5X5 = 12 6Y + 3X2 + 4X3 - 5X4 ≤ 124 con X3, X4, X5 ≥ 0 1 ≤ Y ≤ +4 -∞ ≤ X2 ≤ +5
In questo caso vogliamo risolvere un problema di LP la cui formulazione si trova in un file esterno JSON. Chiamiamo tale file pl_problem.json. Nel file avremo il seguente contenuto:
{
"objective": {
"type": "min",
"coefficients": {
"Y": 3,
"X2": 2,
"X3": 4,
"X4": 7,
"X5": 8
}
},
"constraints": [
{
"coefficients": {
"Y": 5,
"X2": 2,
"X4": -3
},
"relation": "ge",
"rhs": 9,
"name": "VINCOLO1"
},
{
"coefficients": {
"Y": 3,
"X2": 1,
"X3": 1,
"X5": 5
},
"relation": "eq",
"rhs": 12,
"name": "VINCOLO2"
},
{
"coefficients": {
"Y": 6,
"X2": 3,
"X3": 4,
"X4": -5
},
"relation": "le",
"rhs": 124,
"name": "VINCOLO3"
}
],
"bounds": {
"Y": {
"lower": 1,
"upper": 4
},
"X2": {
"lower": null,
"upper": 5
}
}
}
Per poter referenziare il file json occorre semplicemente creare una istanza della classe JsonProblem, passandogli come argomento un oggetto Path contenente il percorso di dove è situato il file [riga 9].
import java.nio.file.Paths;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
LP lp = new LP(new JsonProblem(Paths.get("C:/appo/pl_problem.json")));
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);
}
}
Esempio 1.18
Si consideri il seguente problema di LP :
min 3Y + 2X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 ≥ 9 - 3X4 3Y + X2 + X3 + 5X5 = 12 6Y + 3X2 + 4X3 ≤ 124 - 5X4 Y + 3X2 + 6X5 ≤ 854 - 3X4 con Y, X2, X3, X4, X5 ≥ 0Questo esempio è identico all'esempio 1.1, con la particolarità che i risultati relativi alla soluzione ottima individuata vengono memorizzati in un oggetto della classe JsonSolution, che permette di salvare i risultati o in un file JSON esterno o in una stringa contenente il JSON o infine come oggetto JSON (JsonObject) della libreria jakarta.json. In questo esempio salveremo la soluzione in un file esterno JSON ed otterremo il seguente contenuto:
{
"meta": {
"executionTimestamp": "2024-10-02 20:41:04",
"problemTitle": "Esempio 1.18",
"problemDescription": "LP problem",
"threads": 1,
"iterations": 3,
"optimizationDuration": "00:00:00:021",
"averageError": 2.886579864025407e-14,
"maxError": 1.1368683772161604e-13
},
"objectiveType": "min",
"status": "optimal",
"solution": {
"objectiveValue": 12.0,
"variables": {
"X2": {
"value": 0.0,
"lower": 0.0,
"upper": null
},
"X3": {
"value": 0.0,
"lower": 0.0,
"upper": null
},
"X4": {
"value": 0.0,
"lower": 0.0,
"upper": null
},
"X5": {
"value": 0.0,
"lower": 0.0,
"upper": null
},
"Y": {
"value": 4.0,
"lower": 0.0,
"upper": null
}
}
}
}
È importante sottolineare che le diverse informazioni relative alla soluzione individuata possono essere inserite o meno
nel JSON aggiungendo le relative costanti di tipo SolutionDetail al metodo getSolutionAsJson() della classe LP (o MILP).
In questo caso aggiungendo INCLUDE_BOUNDS e INCLUDE_META, vengono aggiunte, alle informazioni di base, anche quelle relative
agli upper e lower bound e le metainformazioni relative all'elaborazione, quali i tempi di esecuzione, il numero di thread, etc.
Se non vengono passati argomenti al metodo getSolutionAsJson(), vengono memorizzate sole le informazioni di base.
import org.ssclab.pl.milp.*;
import static org.ssclab.pl.milp.SolutionDetail.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String pl_string =
"min: 3Y +2x2 +4x3 +7x4 +8X5 \n"+
" 5Y +2x2 >= 9 -3X4 \n"+
" 3Y + X2 + X3 +5X5 = 12 \n" +
" 6Y+3.0x2 +4X3 <= 124 -5X4 \n" +
" y + 3x2 +6X5 <= 854 -3X4 ";
LP lp=new LP(pl_string).setTitle("Esempio 1.18");
lp.resolve();
lp.getSolutionAsJson(INCLUDE_BOUNDS,INCLUDE_META).saveToFile("c:\\solution.json");
}
}
Esempio 1.19
Si consideri il seguente problema di LP :
Questo esempio è identico all'esempio 1.1, con la particolarità che i rusultati, normalmente visualizzati sulla console standard, vengono salvati in un file di testo esterno (result_lp.txt) tramite la ridirezione del log [rigo 16].
min 3Y + 2X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 ≥ 9 - 3X4 3Y + X2 + X3 + 5X5 = 12 6Y + 3X2 + 4X3 ≤ 124 - 5X4 Y + 3X2 + 6X5 ≤ 854 - 3X4 con Y, X2, X3, X4, X5 ≥ 0
Questo esempio è identico all'esempio 1.1, con la particolarità che i rusultati, normalmente visualizzati sulla console standard, vengono salvati in un file di testo esterno (result_lp.txt) tramite la ridirezione del log [rigo 16].
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 >= 9 -3X4 \n"+
" 3Y + X2 + X3 +5X5 = 12 \n" +
" 6Y+3.0x2 +4X3 <= 124 -5X4 \n" +
" y + 3x2 +6X5 <= 854 -3X4 ";
SscLogger.setLogToFile("c:\\appo\\result_lp.txt");
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);
}
}
Example 2.1
Consideriamo il seguente problema di programmazione lineare misto-intera (MILP) :
Questo problema presenta le variabili X2, X3, X4, X5 intere, mentre la variabile X1 non lo è. In SSC per risolvere un problema di MILP occorre semplicemente introdurre nel formato a coefficienti un rigo aggiuntivo [rigo 20] per dichiarare le variabili intere. Ponendo 1 sul rigo degli "integer" si dichiara la relativa variabile come intera.
Altra differenza è che in questo caso va instanziato l'oggetto MILP [rigo 25] e non l'oggetto LP.
min 3X1 + X2 + 4X3 + 7X4 + 8X5 5X1 + 2X2 + 3X4 ≤ 9 3X1 + X2 + X3 + 5X5 ≥ 12 6X1 + 3X2 + 4X3 + 5X4 ≥ 124 1X1 + 3X2 + 3X4 + 6X5 ≥ 854 con X2, X3, X4, X5 ∈ ℤ 1 ≤ X2 ≤ +6 1 ≤ X3 ≤ +∞ X1, X4, X5 ≥ 0
Questo problema presenta le variabili X2, X3, X4, X5 intere, mentre la variabile X1 non lo è. In SSC per risolvere un problema di MILP occorre semplicemente introdurre nel formato a coefficienti un rigo aggiuntivo [rigo 20] per dichiarare le variabili intere. Ponendo 1 sul rigo degli "integer" si dichiara la relativa variabile come intera.
Altra differenza è che in questo caso va instanziato l'oggetto MILP [rigo 25] e non l'oggetto LP.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Esempio {
public static void main(String[] args) throws Exception {
String milp_string=
"3 1 4 7 8 min . " +"\n"+
"5 2 0 3 0 le 9 " +"\n"+
"3 1 1 0 5 ge 12" +"\n"+
"6 3 4 5 0 ge 124" +"\n"+
"1 3 0 3 6 ge 854" +"\n"+
"0 1 1 0 0 lower . " +"\n"+
". 6 . . . upper . " +"\n"+
"0 1 1 1 1 integer . " +"\n" ;
InputString milp_input = new InputString(milp_string);
milp_input.setInputFormat("X1-X5:double, TYPE:varstring(20), RHS:double");
MILP milp=new MILP(milp_input);
SolutionType solution_type= milp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 2.2
Si consideri il seguente problema di MILP dato da:
Vogliamo risolvere questo problema di programmazione lineare intera utilizzando la notazione matriciale. Per far ciò basta aggiungere alla matrice A dei coefficienti un rigo per esprimere quali sono le variabili intere [rigo 21]. Con il valore 1 si dichiara la variabile intera, con lo 0 la si considera non intera. Occorre anche dichiarare a SSC che l'ulteriore rigo inserito in A non è relativo ai vincoli di tipo GE, LE ,EQ , ma alla dichiarazione delle variabili intere; ciò si realizza aggiungendo al vettore che esprime il tipo di vincolo (array rel[]) il valore ConsType.INT [rigo 26]. Infine occorre aggiungere al vettore b un valore NaN [rigo 23], per adeguare la dimensione di A con quella di b in quanto la dimensione di b deve coincidere con il numero di righi della matrice A.
max X1 + 3.0X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3.0X2 ≤ 5 con X1, X2 ≥ 0 X1, X2 ∈ ℤ
Vogliamo risolvere questo problema di programmazione lineare intera utilizzando la notazione matriciale. Per far ciò basta aggiungere alla matrice A dei coefficienti un rigo per esprimere quali sono le variabili intere [rigo 21]. Con il valore 1 si dichiara la variabile intera, con lo 0 la si considera non intera. Occorre anche dichiarare a SSC che l'ulteriore rigo inserito in A non è relativo ai vincoli di tipo GE, LE ,EQ , ma alla dichiarazione delle variabili intere; ciò si realizza aggiungendo al vettore che esprime il tipo di vincolo (array rel[]) il valore ConsType.INT [rigo 26]. Infine occorre aggiungere al vettore b un valore NaN [rigo 23], per adeguare la dimensione di A con quella di b in quanto la dimensione di b deve coincidere con il numero di righi della matrice A.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.ConsType;
import org.ssclab.pl.milp.Constraint;
import org.ssclab.pl.milp.GoalType;
import org.ssclab.pl.milp.LinearObjectiveFunction;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import static org.ssclab.pl.milp.LP.NaN;
import java.util.ArrayList;
public class Esempio {
public static void main(String[] args) throws Exception {
double A[][]={
{ 1.0 , 1.0 },
{ 1.0 , 1.4 },
{-5.0 , 3.0 },
{ 1.0 , 1.0 }, //rigo della matrice per la definizione degli integer
} ;
double b[]= { 1.0, 6.0 ,5.0, NaN};
double c[]= { 1.0, 3.0 };
ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.LE, ConsType.INT};
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], rel[i], b[i]));
}
MILP lp = new MILP(f,constraints);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 2.3
Si consideri il seguente problema di MILP :
Vogliamo risolvere questo problema di programmazione lineare misto intera utilizzando la notazione sparsa. Per indicare che la variabile Y2 è intera basta aggiungere nella colonna dei ROW_ un valore per indicare quale sarà il marcatore che le definisce. Questo marcatore (da noi chiamato "var_int", ma può avere qualsiasi altro nome) deve avere associato un TYPE di tipo INTEGER [rigo 23].
Una volta definito il marcatore che definisce le variabili intere, basta dichiarare [rigo 38] che la variabile Y2 è di tipo var_int (ovvero INTEGER) ponendo nella colona dei COEF il valore 1. Se al contrario una variabile non è intera si deve valorizzare la colonna COEF con lo 0 o, più brevemente, tralasciare l'intera dichiarazione. Difatti, nella formulazione sottostante, la variabile Y1 non è intera e quindi non è necessario esprimere la mancata associazione tra la variabile e il marcatore var_int ponendo il valore 0 in COEF.
max Y1 + 3.0Y2 Y1 + Y2 ≥ 1 Y1 + 1.4Y2 ≤ 6 -5Y1 + 3.0Y2 = 5 con Y2 ∈ ℤ -1 ≤ Y1 ≤ +1 -∞ ≤ Y2 ≤ +∞
Vogliamo risolvere questo problema di programmazione lineare misto intera utilizzando la notazione sparsa. Per indicare che la variabile Y2 è intera basta aggiungere nella colonna dei ROW_ un valore per indicare quale sarà il marcatore che le definisce. Questo marcatore (da noi chiamato "var_int", ma può avere qualsiasi altro nome) deve avere associato un TYPE di tipo INTEGER [rigo 23].
Una volta definito il marcatore che definisce le variabili intere, basta dichiarare [rigo 38] che la variabile Y2 è di tipo var_int (ovvero INTEGER) ponendo nella colona dei COEF il valore 1. Se al contrario una variabile non è intera si deve valorizzare la colonna COEF con lo 0 o, più brevemente, tralasciare l'intera dichiarazione. Difatti, nella formulazione sottostante, la variabile Y1 non è intera e quindi non è necessario esprimere la mancata associazione tra la variabile e il marcatore var_int ponendo il valore 0 in COEF.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Esempio {
public static void main(String[] args) throws Exception {
String lp_sparse =
// TYPE COL_ ROW_ COEF
" MAX . costo . \n" +
" GE . row1 . \n" +
" LE . row2 . \n" +
" EQ . row3 . \n" +
" UPPER . lim_sup . \n" +
" LOWER . lim_inf . \n" +
" INTEGER . var_int . \n" +
" . Y1 costo 1 \n" +
" . Y1 row1 1 \n" +
" . Y1 row2 1 \n" +
" . Y1 row3 -5 \n" +
" . Y1 lim_sup 1 \n" +
" . Y1 lim_inf -1 \n" +
" . Y2 costo 3 \n" +
" . Y2 row1 1 \n" +
" . Y2 row2 1.4 \n" +
" . Y2 row3 3 \n" +
" . Y2 lim_sup . \n" +
" . Y2 lim_inf . \n" +
" . Y2 var_int 1 \n" +
" . RHS row1 1 \n" +
" . RHS row2 6 \n" +
" . RHS row3 5 \n" ;
InputString lp_input = new InputString(lp_sparse);
lp_input.setInputFormat("TYPE:varstring(7), COL_:varstring(3) , ROW_:varstring(7), COEF:double");
MILP lp = new MILP(lp_input,FormatType.SPARSE);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 2.4
Si consideri il seguente problema di programmazione lineare misto intera
(MILP) con alcune variabili binarie:
Questo problema presenta variabili intere e binarie, mentre la variabile K3 non è soggetta a nessun vincolo di interezza. Per dichiarare una variabile binaria basta aggiungere un rigo avente TYPE "binary" [rigo 22]. Se la i-esima variabile è binaria basta porre 1 nel corrispondente rigo dei binary. Si rammenta che una variabile non può essere definita contemporaneamente sia binaria che intera. Nel nostro caso le variabili K1 e K4 sono binarie mentre le variabili K2 e K5 sono intere.
min 3K1 + K2 + 4K3 + 7K4 + 8K5
5K1 + 2K2 + 3K4 ≤ 9
3K1 + K2 + K3 + 5K5 ≥ 12
6K1 + 3K2 + 4K3 + 5K4 ≥ 124
1K1 + 3K2 + 3K4 + 6K5 ≥ 854
con K2, K5 ∈ ℤ
K1, K4 ∈ {0,1}
1 ≤ K2 ≤ +6
1 ≤ K3 ≤ +∞
con K1, K4, K5 ≥ 0
Questo problema presenta variabili intere e binarie, mentre la variabile K3 non è soggetta a nessun vincolo di interezza. Per dichiarare una variabile binaria basta aggiungere un rigo avente TYPE "binary" [rigo 22]. Se la i-esima variabile è binaria basta porre 1 nel corrispondente rigo dei binary. Si rammenta che una variabile non può essere definita contemporaneamente sia binaria che intera. Nel nostro caso le variabili K1 e K4 sono binarie mentre le variabili K2 e K5 sono intere.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Esempio {
public static void main(String[] args) throws Exception {
String milp_string=
"3 1 4 7 8 min . " +"\n"+
"5 2 0 3 0 le 9 " +"\n"+
"3 1 1 0 5 ge 12" +"\n"+
"6 3 4 5 0 ge 124" +"\n"+
"1 3 0 3 6 ge 854" +"\n"+
"0 1 1 0 0 lower . " +"\n"+
". 6 . . . upper . " +"\n"+
"0 1 0 0 1 integer . " +"\n"+
"1 0 0 1 0 binary . " +"\n";
InputString milp_input = new InputString(milp_string);
milp_input.setInputFormat("K1-K5:double, TYPE:varstring(20), RHS:double");
MILP milp=new MILP(milp_input);
SolutionType solution_type= milp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 2.5
Si consideri il seguente problema di MILP dato da:
Vogliamo risolvere questo problema di programmazione lineare intera, che presenta anche variabili binarie, utilizzando la notazione matriciale. In questa notazione, per rappresentare le variabili binarie, basta aggiungere alla matrice A dei coefficienti un rigo per dichiararle [rigo 15]. Con il valore 1 si dichiara la variabile binaria, con lo 0 la si considera non binaria. Va anche aggiunto il valore ConsType.BIN [rigo 20] per dichiarare che l'ultimo rigo della matrice A è relativo alla definizione delle variabili binarie.
max X1 + 3.0X2
X1 + X2 ≥ 1
X1 + 1.4X2 ≤ 6
-5X1 + 3.0X2 ≤ 5
con X1, X2 ≥ 0
X1 ∈ ℤ
X2 ∈ {0,1}
Vogliamo risolvere questo problema di programmazione lineare intera, che presenta anche variabili binarie, utilizzando la notazione matriciale. In questa notazione, per rappresentare le variabili binarie, basta aggiungere alla matrice A dei coefficienti un rigo per dichiararle [rigo 15]. Con il valore 1 si dichiara la variabile binaria, con lo 0 la si considera non binaria. Va anche aggiunto il valore ConsType.BIN [rigo 20] per dichiarare che l'ultimo rigo della matrice A è relativo alla definizione delle variabili binarie.
import static org.ssclab.pl.milp.LP.NaN;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import java.util.ArrayList;
public class Esempio {
public static void main(String[] args) throws Exception {
double A[][]={
{ 1.0 , 1.0 },
{ 1.0 , 1.4 },
{-5.0 , 3.0 },
{ 1.0 , 0.0 }, //definizione degli integer
{ 0.0 , 1.0 }, //definizione dei binary
} ;
double b[]= { 1.0, 6.0 ,5.0, NaN, NaN};
double c[]= { 1.0, 3.0 };
ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.LE, ConsType.INT , ConsType.BIN};
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ListConstraints constraints = new ListConstraints();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], rel[i], b[i]));
}
MILP lp = new MILP(f,constraints);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 2.6
Si consideri il seguente problema di MILP :
Vogliamo risolvere questo problema di programmazione lineare misto intera, che presenta anche variabili binarie, utilizzando la notazione sparsa. Per indicare che la variabile Y1 è binaria basta aggiungere nella colonna dei ROW_ il marcatore che le definisce. Questo marcatore (da noi chiamato "var_bin" , ma che può avere qualsiasi altro nome) deve avere associato un TYPE di tipo BINARY [rigo 24].
Una volta definito il marcatore delle variabili binarie, basta dichiarare [rigo 32] che la variabile Y1 è di tipo var_bin (ovvero BINARY) ponendo nella colonna dei COEF il valore 1.
max Y1 + 3.0Y2
Y1 + Y2 ≥ 1
Y1 + 1.4Y2 ≤ 6
-5Y1 + 3.0Y2 ≤ 5
con Y1 ∈ {0,1}
Y2 ∈ ℤ
-∞ ≤ Y2 ≤ +∞
Vogliamo risolvere questo problema di programmazione lineare misto intera, che presenta anche variabili binarie, utilizzando la notazione sparsa. Per indicare che la variabile Y1 è binaria basta aggiungere nella colonna dei ROW_ il marcatore che le definisce. Questo marcatore (da noi chiamato "var_bin" , ma che può avere qualsiasi altro nome) deve avere associato un TYPE di tipo BINARY [rigo 24].
Una volta definito il marcatore delle variabili binarie, basta dichiarare [rigo 32] che la variabile Y1 è di tipo var_bin (ovvero BINARY) ponendo nella colonna dei COEF il valore 1.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Esempio {
public static void main(String[] args) throws Exception {
String lp_sparse =
// TYPE COL_ ROW_ COEF
" MAX . costo . \n" +
" GE . row1 . \n" +
" LE . row2 . \n" +
" LE . row3 . \n" +
" UPPER . lim_sup . \n" +
" LOWER . lim_inf . \n" +
" INTEGER . var_int . \n" +
" BINARY . var_bin . \n" +
" . Y1 costo 1 \n" +
" . Y1 row1 1 \n" +
" . Y1 row2 1 \n" +
" . Y1 row3 -5 \n" +
" . Y1 var_bin 1 \n" +
" . Y2 costo 3 \n" +
" . Y2 row1 1 \n" +
" . Y2 row2 1.4 \n" +
" . Y2 row3 3 \n" +
" . Y2 lim_sup . \n" +
" . Y2 lim_inf . \n" +
" . Y2 var_int 1 \n" +
" . RHS row1 1 \n" +
" . RHS row2 6 \n" +
" . RHS row3 5 \n" ;
InputString lp_input = new InputString(lp_sparse);
lp_input.setInputFormat("TYPE:varstring(7), COL_:varstring(3) , ROW_:varstring(7), COEF:double");
MILP milp = new MILP(lp_input,FormatType.SPARSE);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 2.7
Si consideri il seguente problema di LP :
Vogliamo risolvere questo problema di programmazione lineare misto intera usando il formato testuale. In questo formato per aggiungere il vincolo di interezza sulle variabili X2 e X3 basta aggiungere un rigo [rigo 15] con la dichiarazione delle variabili da considerare intere. Nel caso in cui si vogliano definire variabili binare o semicontinue, la sintassi è identica a quella della dichiarazione degli interi, ovvero si antepone invece di "int" la parola chiave "bin" o "sec" e si fa seguire una lista di variabili separate da virgola. Se il problema richiede tutte le variabili intere (o binarie o semicontinue) basta far seguire al tipo di variabile di cui si necessita la parola ALL ("INT ALL"). Attenzione ! Se si è già definito una istruzione "int", altre istruzioni "int" o "bin" o "sec" vanno poste ognuna su righi differenti.
min 3X1 + X2 + 4X3 + 7X4 + 8X5 5X1 + 2X2 + 3X4 ≥ 9 3X1 + X2 + X3 + 5X5 ≥ 12.5 6X1 + 3X2 + 4X3 + 5X4 ≤ 124 X1 + 3X2 + 3X4 + 6X5 ≤ 854 con X1, X2, X3, X4, X5 ≥ 0 X2, X3 ∈ ℤ
Vogliamo risolvere questo problema di programmazione lineare misto intera usando il formato testuale. In questo formato per aggiungere il vincolo di interezza sulle variabili X2 e X3 basta aggiungere un rigo [rigo 15] con la dichiarazione delle variabili da considerare intere. Nel caso in cui si vogliano definire variabili binare o semicontinue, la sintassi è identica a quella della dichiarazione degli interi, ovvero si antepone invece di "int" la parola chiave "bin" o "sec" e si fa seguire una lista di variabili separate da virgola. Se il problema richiede tutte le variabili intere (o binarie o semicontinue) basta far seguire al tipo di variabile di cui si necessita la parola ALL ("INT ALL"). Attenzione ! Se si è già definito una istruzione "int", altre istruzioni "int" o "bin" o "sec" vanno poste ognuna su righi differenti.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String pl_problem =
"min: 3x1 +X2 +4x3 +7x4 +8X5 \n" +
" 5x1 +2x2 +3X4 >= 9\n"+
" 3x1 + X2 +X3 +5X5 >= 12.5\n"+
" 6X1+3.0x2 +4X3 +5X4 <= 124\n"+
" X1 + 3x2 +3X4 +6X5 <= 854\n"+
" int x2, X3 ";
MILP milp = new MILP(pl_problem);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution soluzione=milp.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);
}
}
Esempio 2.8
Si consideri il problema di programmazione lineare intera riportato nella sezione sottostante. In questo esempio si confronta la soluzione ottima finale intera con quella ottenuta dal suo rilassamento (i valori del problema rilassato sono riportati tra parentesi quadre [righi 46-49])
import org.ssclab.context.exception.InvalidSessionException;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import java.util.ArrayList;
import static org.ssclab.pl.milp.LP.NaN;
public class Esempio {
public static void main(String arg[]) throws InvalidSessionException, Exception {
double[] c = { 2, 2, 2, 2, 2 ,2, 2, 2, 2, 2,2 ,2 ,2 };
double[] b = {1000, 1234, 1000, 1000, 1000, 1000, 1000, 1000, 1000};
double[][] A ={ { 2., 9. ,7. ,5. ,9. ,6. ,3., 7., 8. ,7. ,5. ,3. ,1. },
{ 4. ,1. ,2. ,3. ,6. ,4. ,5. ,2. ,8. ,5. ,3. ,4., 7. },
{ 3. ,4. ,2. ,5. ,7. ,6. ,3. ,5. ,7. ,4. ,6. ,8. ,6. },
{ 4. ,6. ,9. ,8. ,7. ,6. ,5. ,4. ,3. ,2. ,3. ,5. ,6. },
{ 4. ,4. ,7. ,5. ,3. ,8. ,5. ,6. ,3. ,5. ,6. ,4. ,6. },
{ 2. ,6. ,4. ,5. ,7. ,5. ,6. ,4. ,6. ,7. ,4. ,4. ,6. },
{ 4. ,6. ,9. ,8. ,3. ,6. ,5. ,5. ,3. ,2. ,9. ,5. ,6. },
{ 4. ,5. ,7. ,8. ,3. ,8. ,3. ,6. ,3. ,5. ,6. ,1. ,6. },
{ 2., 2., 4., 3., 7. ,5. ,9. ,4. ,6. ,7. ,8. ,4., 6. }};
double[] upper ={ 190.5, NaN, NaN, NaN, NaN ,NaN ,NaN ,NaN ,35.0 ,NaN ,NaN ,NaN, NaN };
double[] integer ={ 1.0, 1.0, 1.0, 1.0, 1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0, 1.0 };
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i< A.length; i++) {
constraints.add(new Constraint(A[i], ConsType.LE, b[i]));
}
constraints.add(new Constraint(upper, ConsType.UPPER, NaN));
constraints.add(new Constraint(integer, ConsType.INT , NaN));
MILP milp = new MILP(f,constraints);
SolutionType solution=milp.resolve();
if(solution==SolutionType.OPTIMUM) {
Solution sol=milp.getSolution();
Solution sol_relax=milp.getRelaxedSolution();
Variable[] var_int=sol.getVariables();
Variable[] var_relax=sol_relax.getVariables();
for(int _i=0; _i< var_int.length;_i++) {
SscLogger.log("Nome variabile :"+var_int[_i].getName() + " valore:"+var_int[_i].getValue()+
" ["+var_relax[_i].getValue()+"]");
}
SscLogger.log("valore ottimo:"+sol.getOptimumValue() +" ["+sol_relax.getOptimumValue()+"]");
}
}
}
Esempio 2.9
Si consideri il seguente problema di MILP :
Questo problema è simile al problema 2.7. Nel codice per la sua risoluzione sono state aggiunti dei righi per recuperare il valore che la parte LHS di ogni vincolo (la parte alla sinistra della relazione) assume valorizzando le variabili incognite con la soluzione ottima. Il valore LHS viene poi confrontato con il corrispettivo valore RHS [righi 24-27]. Specifichiamo che le quantià LHS e RHS di cui si parla in questo specifico caso, dato un problema di programmazione lineare AX <=> b, sono date da AX (parte LHS) e b (RHS). Per cui se nella definizione del problema inseriamo delle variabili sulla destra del segno di disuguaglianza/uguaglianza, queste non saranno considerate come parte RHS, ma raggruppate nella forma: AX (parte LHS) e b (RHS). Ai vincoli si può dare un nome, basta anteporre un nome al vincolo e facendolo seguire dai due punti esempio 1.11).
In questo esempio si sono rese intere tutte le variabili. Per dichiararle tutte intere è possibile utilizzare la notazione "int all", oppure utilizzare la notazione che utilizza il catattere jolly *, che indica che tutte le variabili che iniziano per un determinato prefisso siano di un determinato tipo (come nell'esempio). Utilizzando questa notazione è possibile ad esempio utilizzare una notazione come questa: "int XI* \n bin XB*". In questo modo dichiariamo che le variabili che iniziano per "XI" siano intere, quelle che iniziano per "XB" siano binarie e le rimanenti reali.
min 3X1 + X2 + 4X3 + 7X4 + 8X5 5X1 + 2X2 + 3X4 ≥ 9 3X1 + X2 + X3 + 5X5 ≥ 12.5 6X1 + 3X2 + 4X3 + 5X4 ≤ 124 X1 + 3X2 + 3X4 + 6X5 ≤ 854 con X1, X2, X3, X4, X5 ≥ 0 X1, X2, X3, X4, X5 ∈ ℤ
Questo problema è simile al problema 2.7. Nel codice per la sua risoluzione sono state aggiunti dei righi per recuperare il valore che la parte LHS di ogni vincolo (la parte alla sinistra della relazione) assume valorizzando le variabili incognite con la soluzione ottima. Il valore LHS viene poi confrontato con il corrispettivo valore RHS [righi 24-27]. Specifichiamo che le quantià LHS e RHS di cui si parla in questo specifico caso, dato un problema di programmazione lineare AX <=> b, sono date da AX (parte LHS) e b (RHS). Per cui se nella definizione del problema inseriamo delle variabili sulla destra del segno di disuguaglianza/uguaglianza, queste non saranno considerate come parte RHS, ma raggruppate nella forma: AX (parte LHS) e b (RHS). Ai vincoli si può dare un nome, basta anteporre un nome al vincolo e facendolo seguire dai due punti esempio 1.11).
In questo esempio si sono rese intere tutte le variabili. Per dichiararle tutte intere è possibile utilizzare la notazione "int all", oppure utilizzare la notazione che utilizza il catattere jolly *, che indica che tutte le variabili che iniziano per un determinato prefisso siano di un determinato tipo (come nell'esempio). Utilizzando questa notazione è possibile ad esempio utilizzare una notazione come questa: "int XI* \n bin XB*". In questo modo dichiariamo che le variabili che iniziano per "XI" siano intere, quelle che iniziano per "XB" siano binarie e le rimanenti reali.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String problema_pl =
"min: 3x1 +X2 +4x3 +7x4 +8X5 \n"+
"vincolo1: 5x1 +2x2 +3X4 >= 9\n"+
"vincolo2: 3x1 + X2 +X3 +5X5 >= 12.5\n"+
"riga3: 6X1+3.0x2 +4X3 +5X4 <= 124\n"+
"X1 + 3x2 +3X4 +6X5 <= 854\n"+
"int x* ";
MILP milp = new MILP(problema_pl);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution soluzione=milp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore :"+var.getValue());
}
for(SolutionConstraint sol_constraint: soluzione.getSolutionConstraint()) {
SscLogger.log("Vincolo "+sol_constraint.getName()+" : valore="+sol_constraint.getValue() +
"[ "+sol_constraint.getRel()+" "+sol_constraint.getRhs()+" ]" );
}
SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 2.10
Si consideri il seguente problema di programmazione lineare misto intera
(MILP) che presenta anche una variabile semicontinua:
Questo problema è identico al problema 2.4 con l'aggiunta della condizione che la variabile K2 è semicontinua, ovvero essa non è strettamente vincolata ad essere compresa tra i valori di upper e lower, ma può anche assumere il valore 0.
min 3K1 + K2 + 4K3 + 7K4 + 8K5
5K1 + 2K2 + 3K4 ≤ 9
3K1 + K2 + K3 + 5K5 ≥ 12
6K1 + 3K2 + 4K3 + 5K4 ≥ 124
1K1 + 3K2 + 3K4 + 6K5 ≥ 854
con K2, K5 ∈ ℤ
K1, K4 ∈ {0,1}
1 ≤ K2 ≤ 6 oppure K2 =0
1 ≤ K3 ≤ +∞
con K1, K4, K5 ≥ 0
Questo problema è identico al problema 2.4 con l'aggiunta della condizione che la variabile K2 è semicontinua, ovvero essa non è strettamente vincolata ad essere compresa tra i valori di upper e lower, ma può anche assumere il valore 0.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Esempio {
public static void main(String[] args) throws Exception {
String milp_string=
"3 1 4 7 8 min . " +"\n"+
"5 2 0 3 0 le 9 " +"\n"+
"3 1 1 0 5 ge 12" +"\n"+
"6 3 4 5 0 ge 124" +"\n"+
"1 3 0 3 6 ge 854" +"\n"+
"0 1 1 0 0 lower . " +"\n"+
". 6 . . . upper . " +"\n"+
"0 1 0 0 1 integer . " +"\n"+
"1 0 0 1 0 binary . " +"\n"+
"0 1 0 0 0 semicont . " +"\n";
InputString milp_input = new InputString(milp_string);
milp_input.setInputFormat("K1-K5:double, TYPE:varstring(20), RHS:double");
MILP milp=new MILP(milp_input);
SolutionType solution_type= milp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 2.11
Si consideri il seguente problema di MILP dato da:
Vogliamo risolvere questo problema di programmazione lineare intera, che presenta anche una variabile semicontinua intera, utilizzando la notazione matriciale.
max -X1 + 3.0X2
X1 + X2 ≥ 1
X1 + 1.4X2 ≤ 6
-5X1 + 3.0X2 ≤ 5
con X1, X2 ≥ 0
X1 ∈ ℤ
X2 ∈ {0,1}
1 ≤ X1 ≤ 3 oppure X1 =0
Vogliamo risolvere questo problema di programmazione lineare intera, che presenta anche una variabile semicontinua intera, utilizzando la notazione matriciale.
import static org.ssclab.pl.milp.LP.NaN;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import java.util.ArrayList;
public class Esempio {
public static void main(String[] args) throws Exception {
double A[][]={
{ 1.0 , 1.0 },
{ 1.0 , 1.4 },
{-5.0 , 3.0 },
{ 1.0 , 0.0 }, //definizione degli integer
{ 0.0 , 1.0 }, //definizione dei binary
{ 1.0 , 0.0 }, //definizione dei semicontinuous
{ 3.0 , NaN}, //definizione dei upper
{ 1.0 , 0.0 }, //definizione dei lower
} ;
double b[]= { 1.0, 6.0 ,5.0, NaN, NaN, NaN, NaN, NaN};
double c[]= { -1.0, 3.0 };
ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.LE, ConsType.INT, ConsType.BIN,
ConsType.SEMICONT, ConsType.UPPER, ConsType.LOWER};
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], rel[i], b[i]));
}
MILP lp = new MILP(f,constraints);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
}
}
Esempio 2.12
Si consideri il seguente problema di MILP :
Vogliamo risolvere questo problema di programmazione lineare misto intera, che presenta anche variabili semicontinue, utilizzando la notazione sparsa.
max Y1 - 3.0Y2
Y1 + Y2 ≥ 1
Y1 + 1.4Y2 ≤ 6
-5Y1 + 3.0Y2 ≤ 5
con Y1 ∈ {0,1}
Y2 ∈ ℤ
1 ≤ Y2 ≤ +∞ oppure Y2 = 0
Vogliamo risolvere questo problema di programmazione lineare misto intera, che presenta anche variabili semicontinue, utilizzando la notazione sparsa.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Esempio {
public static void main(String[] args) throws Exception {
String lp_sparse =
// TYPE COL_ ROW_ COEF
" MAX . costo . \n" +
" GE . row1 . \n" +
" LE . row2 . \n" +
" LE . row3 . \n" +
" UPPER . lim_sup . \n" +
" LOWER . lim_inf . \n" +
" INTEGER . var_int . \n" +
" BINARY . var_bin . \n" +
" SEMICONT . var_sc . \n" +
" . Y1 costo 1 \n" +
" . Y1 row1 1 \n" +
" . Y1 row2 1 \n" +
" . Y1 row3 -5 \n" +
" . Y1 var_bin 1 \n" +
" . Y2 costo -3 \n" +
" . Y2 row1 1 \n" +
" . Y2 row2 1.4 \n" +
" . Y2 row3 3 \n" +
" . Y2 lim_sup . \n" +
" . Y2 lim_inf 1 \n" +
" . Y2 var_int 1 \n" +
" . Y2 var_sc 1 \n" +
" . RHS row1 1 \n" +
" . RHS row2 6 \n" +
" . RHS row3 5 \n" ;
InputString lp_input = new InputString(lp_sparse);
lp_input.setInputFormat("TYPE:varstring(8), COL_:varstring(3) , ROW_:varstring(7), COEF:double");
MILP milp = new MILP(lp_input,FormatType.SPARSE);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
}
}
Esempio 2.13
Si consideri il problema di programmazione lineare intera riportato nella sezione sottostante . Vogliamo risolvere questo problema utilizzando un'implementazione del B&B parallelo. Per far questo basta aggiugere l'istruzione al rigo [39], con il quale si dichiara il numero di thread (in questo caso 4) da utilizzare per eseguire un B&B parallelo.
import org.ssclab.context.exception.InvalidSessionException;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.pl.milp.util.MILPThreadsNumber;
import static org.ssclab.pl.milp.LP.NaN;
import java.util.ArrayList;
public class Esempio {
public static void main(String arg[]) throws InvalidSessionException, Exception {
double[] c = { 2, 2, 2, 2, 2 , 2, 2, 2, 2, 2, 2 ,2 , 2 };
double[] b = {1000, 1234, 1000, 1000, 1000, 1000, 1000, 1000, 1000};
double[][] A ={ { 2., 9. ,7. ,5. ,9. ,6. ,3., 7., 8. ,7. ,5. ,3. ,1. },
{ 4. ,1. ,2. ,3. ,6. ,4. ,5. ,2. ,8. ,5. ,3. ,4., 7. },
{ 3. ,4. ,2. ,5. ,7. ,6. ,3. ,5. ,7. ,4. ,6. ,8. ,6. },
{ 4. ,6. ,9. ,8. ,7. ,6. ,5. ,4. ,3. ,2. ,3. ,5. ,6. },
{ 4. ,4. ,7. ,5. ,3. ,8. ,5. ,6. ,3. ,5. ,6. ,4. ,6. },
{ 2. ,6. ,4. ,5. ,7. ,5. ,6. ,4. ,6. ,7. ,4. ,4. ,6. },
{ 4. ,6. ,9. ,8. ,3. ,6. ,5. ,5. ,3. ,2. ,9. ,5. ,6. },
{ 4. ,5. ,7. ,8. ,3. ,8. ,3. ,6. ,3. ,5. ,6. ,1. ,6. },
{ 2., 2., 4., 3., 7. ,5. ,9. ,4. ,6. ,7. ,8. ,4., 6. }};
double[] integer ={ 1.0, 1.0, 1.0, 1.0, 1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0, 1.0 };
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i< A.length; i++) {
constraints.add(new Constraint(A[i], ConsType.LE, b[i]));
}
constraints.add(new Constraint(integer, ConsType.INT , NaN));
MILP milp = new MILP(f,constraints);
milp.setThreadsNumber(MILPThreadsNumber.N_4);
SolutionType solutionType=milp.resolve();
if(solutionType==SolutionType.OPTIMUM) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
}
}
Esempio 2.14
Se l'esigenza è quella di ottenere una soluzione ammissibile non necessariamente ottima , basta invocare il metodo setJustTakeFeasibleSolution() passandogli il valore "true" (rigo 24). Questa opzione permette di far eseguire il B&B im modo di ottenere una soluzione ammissibile . In questo caso il valore restituito da resolve() (se esiste una soluzione ammissibile) sarà SolutionType.FEASIBLE. Nel nostro esempio la soluzione ammissibile intera ottenuta (X1=2,X2=2) ha come valore sulla f.o. -6 , mentre la soluzione ottima (X1=3,X2=1) ha come valore -7.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Esempio {
public static void main(String[] args) throws Exception {
String milp_string=
"-2 -1 min ." +"\n"+
"-1 -1 ge -5" +"\n"+
"1 -1 ge 0" +"\n"+
"-6 -2 ge -21" +"\n"+
"4 3 upper ." +"\n"+
"1 1 integer ." +"\n" ;
InputString milp_input = new InputString(milp_string);
milp_input.setInputFormat("X1-X2:double, TYPE:varstring(20), RHS:double");
MILP milp=new MILP(milp_input);
milp.setJustTakeFeasibleSolution(true);
SolutionType solution_type= milp.resolve();
if(solution_type==SolutionType.FEASIBLE) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore soluzione sulla f.o.:"+solution.getValue());
}
else SscLogger.log("Non esiste una soluzione ammissibile :"+solution_type);
}
}
Esempio 2.15
Si consideri il seguente problema di MILP :
Vogliamo risolvere questo problema usando il formato json. Per poter indicare quali varibili debbono essere intere occorre aggiungere la sezione "variables", nella quale si indica il tipo di variabili. A seconda che siano intere, binarie, semicontinue o semicontinue intere, si utilizzano rispettivamente i valori "integer","binary" ,"semicont" e "integer-semicont". Ricordiamo che nel formato json occorre scrivere sia le chiavi (ad esempio "objective","coefficients","constraints",etc) che i valori (ad esempio "max","min","eq",etc) in minuscolo. Al contrario i nomi dati alle variabili non sono case-sensitive, per cui "X3" e "x3" rappresentano la stessa variabile. Infine, i nomi dei vincoli possono esssere scritti in maiuscolo o munuscolo o un mix, ricordando che però questi sono case-sensitive.
min 3Y + 2X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 - 3X4 ≥ 9 3Y + X2 + X3 + 5X5 = 12 6Y + 3X2 + 4X3 - 5X4 ≤ 124 con X3, X4, X5 ≥ 0 1 ≤ Y ≤ +4 -∞ ≤ X2 ≤ +5 Y ∈ ℤ
Vogliamo risolvere questo problema usando il formato json. Per poter indicare quali varibili debbono essere intere occorre aggiungere la sezione "variables", nella quale si indica il tipo di variabili. A seconda che siano intere, binarie, semicontinue o semicontinue intere, si utilizzano rispettivamente i valori "integer","binary" ,"semicont" e "integer-semicont". Ricordiamo che nel formato json occorre scrivere sia le chiavi (ad esempio "objective","coefficients","constraints",etc) che i valori (ad esempio "max","min","eq",etc) in minuscolo. Al contrario i nomi dati alle variabili non sono case-sensitive, per cui "X3" e "x3" rappresentano la stessa variabile. Infine, i nomi dei vincoli possono esssere scritti in maiuscolo o munuscolo o un mix, ricordando che però questi sono case-sensitive.
import org.ssclab.log.*;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String pl_json = "{ "
+ " 'objective': { "
+ " 'type': 'max', "
+ " 'coefficients': { "
+ " 'Y': 3, "
+ " 'X2': 2, "
+ " 'X3': 4, "
+ " 'X4': 7, "
+ " 'X5': 8 "
+ " } "
+ " }, "
+ " 'constraints': [ "
+ " { "
+ " 'coefficients': { "
+ " 'Y': 5, "
+ " 'X2': 2, "
+ " 'X4':-3 "
+ " }, "
+ " 'relation': 'ge', "
+ " 'rhs': 9, "
+ " 'name':'VINCOLO1' "
+ " }, "
+ " { "
+ " 'coefficients': { "
+ " 'Y': 3, "
+ " 'X2': 1, "
+ " 'X3': 1, "
+ " 'X5': 5 "
+ " }, "
+ " 'relation': 'eq', "
+ " 'rhs': 12, "
+ " 'name':'VINCOLO2' "
+ " }, "
+ " { "
+ " 'coefficients': { "
+ " 'Y': 6, "
+ " 'X2': 3, "
+ " 'X3': 4, "
+ " 'X4':-5 "
+ " }, "
+ " 'relation': 'le', "
+ " 'rhs': 124, "
+ " 'name':'VINCOLO3' "
+ " } "
+ " ], "
+ " 'bounds': { "
+ " 'Y': { "
+ " 'lower': 1, "
+ " 'upper': 4 "
+ " }, "
+ " 'X2': { "
+ " 'lower': null, "
+ " 'upper': 5 "
+ " } "
+ " }, "
+ " 'variables': { "
+ " 'Y': 'integer' "
+ " } "
+ "}";
pl_json=pl_json.replace('\'', '"');
MILP lp = new MILP(new JsonProblem(pl_json));
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);
}
}
Esempio 2.16
Si consideri il seguente problema di LP :
Vogliamo risolvere questo problema di programmazione lineare misto intera e memorizzare la soluzione in un file JSON esterno. In questo caso includiamo, tramite le dichiariazioni "INCLUDE_XXX", tutte le ulteriori informazioni disponibili da memorizzare sulla soluzione in formato JSON. Possiamo notare come al metodo resolve() venga passato il valore null per distinguerlo da quello standard che ritorna il tipo di soluzione trovata, a differenza di questo che permette di costruire una catena di chiamate sull'oggetto MILP.
min 3X1 + X2 + 4X3 + 7X4 + 8X5 5X1 + 2X2 + 3X4 ≥ 9 3X1 + X2 + X3 + 5X5 ≥ 12.5 6X1 + 3X2 + 4X3 + 5X4 ≤ 124 X1 + 3X2 + 3X4 + 6X5 ≤ 854 con X1, X2, X3, X4, X5 ≥ 0 1 ≤ X2 ≤ +3 X1, X3 ∈ ℤ
Vogliamo risolvere questo problema di programmazione lineare misto intera e memorizzare la soluzione in un file JSON esterno. In questo caso includiamo, tramite le dichiariazioni "INCLUDE_XXX", tutte le ulteriori informazioni disponibili da memorizzare sulla soluzione in formato JSON. Possiamo notare come al metodo resolve() venga passato il valore null per distinguerlo da quello standard che ritorna il tipo di soluzione trovata, a differenza di questo che permette di costruire una catena di chiamate sull'oggetto MILP.
import static org.ssclab.pl.milp.SolutionDetail.*;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String pl_problem =
"min: 3x1 +X2 +4x3 +7x4 +8X5 \n" +
" 5x1 +2x2 +3X4 >= 9 \n"+
" 3x1 + X2 +X3 +5X5 >= 12.5 \n"+
" 6X1+3.0x2 +4X3 +5X4 <= 124 \n"+
" X1 + 3x2 +3X4 +6X5 <= 854 \n"+
" 1<=X2<=3 \n"+
" int x1, X3 ";
new MILP(pl_problem)
.setTitle("Esempio 2.16")
.resolve(null)
.getSolutionAsJson(INCLUDE_BOUNDS,INCLUDE_META,INCLUDE_CONSTRAINT,INCLUDE_TYPEVAR,INCLUDE_RELAXED)
.saveToFile("solution.json");
}
}
Esempio 2.17
Si consideri il seguente problema di LP :
Vogliamo risolvere questo problema di programmazione lineare che presenta un insieme di variabili di tipo SOS1, ovvero tra le variabili che fanno parte di questo insieme, solo una può essere maggiore di zero.
min 3X1 + X2 + 4X3 + 7X4 + 8X5 5X1 + 2X2 + 3X4 ≥ 9 3X1 + X2 + X3 + 5X5 ≥ 12.5 6X1 + 3X2 + 4X3 + 5X4 ≤ 124 X1 + 3X2 + 3X4 + 6X5 ≤ 854 con X1, X2, X3, X4, X5 ≥ 0 X1, X3, X4, X5 ∈ SOS1 1 ≤ X2 ≤ +3
Vogliamo risolvere questo problema di programmazione lineare che presenta un insieme di variabili di tipo SOS1, ovvero tra le variabili che fanno parte di questo insieme, solo una può essere maggiore di zero.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String pl_problem =
"min: 3x1 +X2 +4x3 +7x4 +8X5 \n" +
" 5x1 +2x2 +3X4 >= 9 \n"+
" 3x1 + X2 +X3 +5X5 >= 12.5 \n"+
" 6X1+3.0x2 +4X3 +5X4 <= 124 \n"+
" X1 + 3x2 +3X4 +6X5 <= 854 \n"+
" 1<=X2<=3 \n"+
" sos1 x1,X3,x4,x5";
MILP lp = new MILP(pl_problem);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 2.18
Si consideri il seguente problema di LP:
Vogliamo risolvere questo problema di programmazione lineare che presenta un insieme di variabili di tipo SOS2 intere, ovvero tra le variabili che fanno parte di questo insieme, solo due possono essere maggiori di zero e devono essere consecutive, ovvero o (X2, X3) obiettivo (X3, X5) o nessuna.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 ≥ 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
X5 ≥ 0
X1,X2,X3,X4,X5 ∈ ℤ
X2,X3,X5 ∈ SOS2
Vogliamo risolvere questo problema di programmazione lineare che presenta un insieme di variabili di tipo SOS2 intere, ovvero tra le variabili che fanno parte di questo insieme, solo due possono essere maggiori di zero e devono essere consecutive, ovvero o (X2, X3) obiettivo (X3, X5) o nessuna.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
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" +
" int x1,X4 \n" +
" sos2:INT x2, X3,x5 ";
MILP milp = new MILP(lp_problem);
SolutionType solution_type = milp.resolve();
if (solution_type == SolutionType.OPTIMUM) {
Solution solution = milp.getSolution();
for (Variable var : solution.getVariables()) {
SscLogger.log("Nome variabile :" + var.getName() + " valore:" + var.getValue());
}
SscLogger.log("Valore ottimo f.o. :" + solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:" + solution_type);
}
}
Esempio 2.19
Si consideri il seguente problema di LP:
Vogliamo risolvere questo problema di programmazione lineare che presenta un insieme di variabili di tipo F-SOS1 binarie e SOS2. Le prime devono essere binarie ed almeno una deve essere uguale a uno (F = Forced), due consecutive delle seconde possono essere maggiori di zero, ovvero o (X4, X2) o (X2, X3) o una o nessuna.
min 3X1 + X2 + 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 ≥ 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≥ 24
1 ≤ X2 ≤ +6
X1, X5 ∈ {0,1}
X1, X5 ∈ F-SOS1, ovvero X1 + X5 =1
X4, X2, X3 ∈ SOS2
Vogliamo risolvere questo problema di programmazione lineare che presenta un insieme di variabili di tipo F-SOS1 binarie e SOS2. Le prime devono essere binarie ed almeno una deve essere uguale a uno (F = Forced), due consecutive delle seconde possono essere maggiori di zero, ovvero o (X4, X2) o (X2, X3) o una o nessuna.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
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 lp_problem = """
min: 3x1 +X2 +4x3 +7x4 +8X5
5x1 +2x2 +3X4 >= 9
3x1 + X2 +X3 +5X5 >= 12.5
6X1+3.1x2 +4X3 +5X4 >= 24
1 <= x2 <= 6
sos1:bin:force x1, X5
sos2 x4,x2,X3 """;
MILP milp = new MILP(lp_problem);
SolutionType solution_type = milp.resolve();
if (solution_type == SolutionType.OPTIMUM) {
Solution solution = milp.getSolution();
for (Variable var : solution.getVariables()) {
SscLogger.log("Nome variabile :" + var.getName() + " valore:" + var.getValue());
}
SscLogger.log("Valore ottimo f.o. :" + solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:" + solution_type);
}
}
Esempio 3.1
Si consideri il seguente problema di LP:
Vogliamo risolvere questo problema usando il formato testo.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
X5 ≥ 0
X2, X3 ∈ ℤ
Vogliamo risolvere questo problema usando il formato testo.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
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 ";
MILP milp = new MILP(lp_problem);
SolutionType solution_type = milp.resolve();
if (solution_type == SolutionType.OPTIMUM) {
Solution solution = milp.getSolution();
for (Variable var : solution.getVariables()) {
SscLogger.log("Nome variabile :" + var.getName() + " valore:" + var.getValue());
}
SscLogger.log("Valore ottimo f.o. :" + solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:" + solution_type);
}
}
Esempio 3.2
Si consideri il seguente problema di LP:
Vogliamo risolvere questo problema usando il formato a coefficienti.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
X5 ≥ 0
X2, X3 ∈ ℤ
Vogliamo risolvere questo problema usando il formato a coefficienti.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
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-X5:double, TYPE:varstring(8), RHS:double");
MILP milp = new MILP(milp_input);
SolutionType solution_type = milp.resolve();
if (solution_type == SolutionType.OPTIMUM) {
Solution solution = milp.getSolution();
for (Variable var : solution.getVariables()) {
SscLogger.log("Nome variabile :" + var.getName() + " valore:" + var.getValue());
}
SscLogger.log("Valore ottimo f.o. :" + solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:" + solution_type);
}
}
Esempio 3.3
Si consideri il seguente problema di LP:
Vogliamo risolvere questo problema usando il formato matriciale.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
X5 ≥ 0
X2, X3 ∈ ℤ
Vogliamo risolvere questo problema usando il formato matriciale.
import org.ssclab.log.SscLogger;
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]));
MILP milp = new MILP(fo,constraints);
SolutionType solution_type = milp.resolve();
if (solution_type == SolutionType.OPTIMUM) {
Solution solution = milp.getSolution();
for (Variable var : solution.getVariables()) {
SscLogger.log("Nome variabile :" + var.getName() + " valore:" + var.getValue());
}
SscLogger.log("Valore ottimo f.o. :" + solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:" + solution_type);
}
}
Esempio 3.4
Si consideri il seguente problema di LP:
Vogliamo risolvere questo problema usando il formato sparso.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
X5 ≥ 0
X2, X3 ∈ ℤ
Vogliamo risolvere questo problema usando il formato sparso.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
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");
MILP milp = new MILP(lp_input,FormatType.SPARSE);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
Esempio 3.5
Si consideri il seguente problema di LP:
Vogliamo risolvere questo problema usando il formato JSON.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
X5 ≥ 0
X2, X3 ∈ ℤ
Vogliamo risolvere questo problema usando il formato JSON.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
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"
}
}""";
MILP milp = new MILP(new JsonProblem(stringJson));
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMUM) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
}
SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
}
else SscLogger.log("Soluzione non ottima:"+solution_type);
}
}
In SSC un problema di LP può risolto utilizzando diversi formati. Vogliamo risolvere questo problema usando un primo formato di rappresentazione denominato formato testuale. In questo formato la funzione obiettivo (f.o.) e i vincoli possono essere espressi mediante equazioni/disequazioni rappresentate all'interno di un testo [righi 12-16]. Le variabili possono avere qualsiasi nome (devono però iniziare con un carattere alfabetico seguito da caratteri alfanumerici) e risultano non essere case-sensitive (ovvero x3 e X3 rappresentano la stessa variabile). In questo formato la f.o e ciascun vincolo devono essere scritti su righi differenti.
Uno dei vantaggi di questo formato è che se una variabile non è presente in un vincolo questa può essere tralasciata, a differenza del formato matriciale o a coefficienti dove deve essere rappresentata con un coefficiente uguale a zero. Si ricorda che in SSC, di default, le variabili di un problema di LP sono considerate, se non diversamente specificato, non negative (≥ 0).
Una volta rappresentato il problema, si esegue l'algoritmo del Simplesso mediante la creazione di un oggetto della classe LP e l'invocazione del metodo resolve() [righi 18-19]. Una volta eseguito il Simplesso, il metodo resolve() ritorna il tipo di soluzione trovata; se la soluzione è ottima è possibile ricavare i valori delle variabili ed il valore ottimo della funzione obiettivo.