Esempi Java API simplesso

Guida all'uso - Indice degli argomenti

Introduzione
Installazione e Integrazione
Guida Introduttiva
Utilizzo della Libreria

1. Introduzione

La libreria SSC è un versatile strumento progettato per risolvere problemi di Programmazione Lineare (LP) e Programmazione Lineare Misto Intera (MILP). Questa libreria consente di definire e risolvere problemi di ottimizzazione tramite diverse e intuitive sintassi, permettendo agli utenti di modellare vincoli e funzioni obiettivo in modo efficiente. Questa libreria può essere utilizzata per applicazioni in ricerca operativa, economia, ingegneria e gestione; inoltre risulta essere facilmente integrabile in progetti Java tramite Maven e Gradle.

2. Installazione e Integrazione

2.1 Prerequisiti
Per utilizzare la libreria SSC è necessario soddisfare i seguenti requisiti:
- Java 10 o superiore: La libreria richiede Java 10 o versioni successive. Assicurati di avere installata una JDK compatibile con questa versione di Java.
- Ambiente di sviluppo Java: Un ambiente di sviluppo integrato (IDE) come IntelliJ IDEA, Eclipse, o NetBeans è consigliato per facilitare la gestione del progetto e l'integrazione della libreria.
- Gestore di dipendenze: E' raccomandato l'uso di un gestore di dipendenze come Maven o Gradle per l'integrazione della libreria nel tuo progetto. Se utilizzi Maven o Gradle,includi le dipendenze appropriate nel tuo file di configurazione.
  Se non vuoi utilizzare un gestore scarica da questo sito, dalla sezione download, la libreria in formato zip, decomprimila ed estrai il file dei compilati jar, infine includila nel classpath del tuo progetto.
- Conoscenze di programmazione lineare: Per utilizzare efficacemente la libreria, è utile avere una comprensione di base della programmazione lineare e della sua modellazione.
2.2 Integrazione con Maven
Per integrare la libreria SSC in un progetto Maven, aggiungi la seguente dipendenza al file pom.xml:
```

<dependency>
    <groupId>org.ssclab</groupId>
    <artifactId>SSC-LP</artifactId>
    <version>4.6.2</version>
</dependency>
```
Puoi trovare esempi relativi alla gestione delle dipendenze di questa libreria con diversi gestori, sul repository maven al link "https://mvnrepository.com/artifact/org.ssclab/SSC-LP"
2.3 Integrazione con Gradle
Per integrare la libreria SSC in un progetto Gradle, aggiungi la seguente dipendenza al file build.gradle:
```
// https://mvnrepository.com/artifact/org.ssclab/SSC-LP
implementation group: 'org.ssclab', name: 'SSC-LP', version: '4.6.2'
```
2.4 Download manuale della libreria
Per utilizzare la libreria SSC nel tuo progetto Java, puoi scaricarla manualmente e includerla nel tuo classpath. Ecco come procedere:
A. Scarica il File JAR
1. Vai alla pagina del repository Maven per SSC.
2. Seleziona la versione di interesse (ad esempio la 4.6.2) e nella sezione Files della tabella presente nella pagina, seleziona il link dove vi è scritto jar.
3. Questo è il link per scaricare il file jar della libreria. Ad esempio, per la versione 4.6.2, il link sarà simile a https://repo1.maven.org/maven2/org/ssclab/SSC-LP/4.6.2/SSC-LP-4.6.2.jar.
  
  Oppure scarica il file compresso .zip, contenente il file jar, presente nella sezione download di questo sito.
  
  Nota: Il jar scaricato manualmente da Maven non include le librerie presenti nella sezione Dependencies del file pom.xml. Pertanto, se non disponi di queste dipendenze, ti consigliamo di scaricare il file compresso .zip presente nella sezione download di questo sito, il quale include il file jar di SSC comprensivo delle librerie esterne necessarie. Ovviamente, utilizzando Maven come gestore delle dipendenze, tramite il file pom.xml, tutte le dipendenze vengono risolte.
B. Aggiungi il file jar al tuo progetto
1. In un IDE:
  - IntelliJ IDEA:
    1. Apri il progetto in IntelliJ IDEA.
    2. Vai a File > Project Structure (Struttura del Progetto).
    3. Seleziona Modules (Moduli) e poi il modulo in cui desideri aggiungere la libreria.
    4. Vai alla scheda Dependencies (Dipendenze) e clicca su + per aggiungere una nuova dipendenza.
    5. Seleziona JARs or directories e naviga al file jar scaricato. Clicca su OK per aggiungerlo.
    6. Clicca su Apply e poi OK per confermare.
  - Eclipse:
    1. Apri il progetto in Eclipse.
    2. Clicca con il tasto destro sul progetto e seleziona Properties (Proprietà).
    3. Vai a Java Build Path (Percorso di Costruzione Java) e seleziona la scheda Libraries (Librerie).
    4. Clicca su Add External JARs... e naviga al file jar scaricato. Clicca su Open per aggiungerlo.
    5. Clicca su Apply and Close per confermare.
2. In un progetto senza IDE:
  Seguendo questi passaggi, sarai in grado di integrare la libreria SSC nel tuo progetto Java manualmente, senza l'uso di strumenti di gestione delle dipendenze come Maven o Gradle.
  - Copia il file jar scaricato nella directory lib del tuo progetto (se non esiste, puoi crearla). Copia il tuo Programma Esempio.java avente package com.example nella cartella src del tuo progetto
  - Quando compili ed esegui il tuo programma, assicurati di includere il jar nel classpath. Ad esempio, puoi utilizzare il comando javac e java con l'opzione -cp per specificare il classpath (esempi di comandi in ambiente windows):
```
C:\java\jdk-10_0_1\bin\javac -cp ".\lib\SSC-LP-4.6.2.jar" src\com\example\Esempio.java	
C:\java\jdk-10_0_1\bin\java  -cp ".\lib\SSC-LP-4.6.2.jar;.\src" com.example.Esempio				
```

3. Guida introduttiva

3.1 Panoramica sulla Programmazione Lineare (LP)

La Programmazione Lineare (la sigla LP sta per Linear Programming) è una tecnica matematica utilizzata per risolvere problemi di ottimizzazione in cui si desidera massimizzare o minimizzare una funzione obiettivo lineare, soggetta a vincoli lineari espressi attraverso equazioni o disequazioni. Questa metodologia è ampiamente utilizzata in diversi settori, come l'economia, la logistica, l'ingegneria e le scienze gestionali, per prendere decisioni ottimali in situazioni complesse.

Nella LP, la funzione obiettivo rappresenta il valore da ottimizzare, che può essere il profitto, il costo, o altre misure di interesse. I vincoli rappresentano le limitazioni o restrizioni del problema, come le risorse disponibili, i requisiti di produzione, o altre condizioni operative. Questi vincoli sono formulati come espressioni lineari delle variabili decisionali.

La soluzione di un problema di LP consiste nel trovare i valori delle variabili decisionali che ottimizzano la funzione obiettivo rispettando tutti i vincoli imposti. La soluzione può essere trovata graficamente (nel caso di due variabili) o mediante algoritmi numerici, come il metodo del simplesso, che è uno dei più noti ed efficienti per risolvere problemi di PL su larga scala.

La LP è una base fondamentale per altre tecniche di ottimizzazione, come la Programmazione Lineare Intera (ILP) e la Programmazione Lineare Mista Intera (MILP), che estendono i concetti della PL per includere variabili intere e vincoli più complessi.

3.2 Definizione di un Problema LP

Un problema di Programmazione Lineare (LP) mira a ottimizzare una funzione obiettivo lineare, rispettando un insieme di vincoli lineari. Le variabili decisionali rappresentano le scelte da compiere, e la soluzione ottimale si ottiene applicando metodi come il simplesso, che garantiscono efficienza nella risoluzione di problemi con queste caratteristiche. Un esempio di formulazione matematica di un problema LP è:

min  3Y + 2X₂ - 4X₃ + 7X₄ + 8X₅
     5Y + 2X₂        3X₄       ≥   9 
     3Y +  X₂ +  X₃      + 5X₅  =  12
     6Y + 3X₂ + 4X₃   5X₄       ≤  24 
  
con Y, X₂, X₃, X₄, X₅ ≥ 0

La funzione obiettivo è l'espressione da minimizzare o massimizzare, e deve essere una combinazione lineare delle variabili decisionali, nel nostro caso è 3Y +2X₂ -4X₃ +7X₄ +8X₅, con l'obiettivo di trovare il valore minimo possibile.
Le righe rimanenti risultano essere i vincoli, anch'essi lineari, che sono espressioni che limitano il valore delle variabili decisionali. Essi possono essere in forma di disuguaglianza (minore o uguale, maggiore o uguale) o uguaglianza. Nell'esempio, abbiamo disuguaglianze e un'uguaglianza che definiscono le restrizioni sul problema. In genere, le variabili di un problema di PL sono non negative, come indicato dalle condizioni Y, X₂, X₃, X₄, X₅ ≥ 0; questo è il comportamento predefinito per le variabili nella libreria SSC. Tuttavia, è possibile gestire variabili che possono assumere valori negativi, rendendole libere o permettendo loro di assumere valori negativi, a seconda delle necessità del problema specifico.

Generalizzando, un problema di programmazione lineare può essere rappresentato in modo completo attraverso l'uso di vettori e matrici, in questo caso un generico problema di programmazione lineare può essere descritto tramite la seguente sintassi :

	\( \hspace{0.3cm}  \text{ max/min } \hspace{0.3cm} c^{\mathrm{T}}x \hspace{0.3cm} \text{} \) è la funzione obiettivo (f.o.) 
	
	\( \hspace{0.7cm} Ax\, (\le , = , \ge)\, b \)

	\( \hspace{0.7cm} l_{i} \le  x_{i} \le  u_{i} \)

	\( \hspace{0.7cm} x_{i} \in \mathbb{Z} \hspace{1.52cm} \forall i \in \text{I} \)

	\( \hspace{0.7cm} x_{i} \in \{0,1\} \hspace{0.8cm} \forall i \in \text{B} \)

	\( \hspace{0.7cm} x_{i} \in \mathbb{R} \hspace{1.52cm} \forall i \notin (\text{I} \cup \text{B}) \)

	\( \hspace{0.3cm}  \) dove: 

	\( \hspace{0.7cm} x\, \in \mathbb{R}^{n} \hspace{4.23cm}\) è il vettore delle variabili,\(x_{i}\)

	\( \hspace{0.7cm} A \in \mathbb{Q}^{m \times n} \hspace{3.7cm} \) è la matrice dei coefficienti

	\( \hspace{0.7cm} c\,\, \in \mathbb{Q}^{n} \hspace{4.19cm} \) è il vettore dei coefficienti della f.o.

	\( \hspace{0.7cm} b\,\, \in \mathbb{Q}^{m} \hspace{4.12cm} \) è il vettore dei coefficienti RHS 

	\( \hspace{0.7cm} l\,\,\, \in \mathbb{Q}^{n} \hspace{4.18cm} \) è il vettore dei lower bound,\(l_{i}\)

	\( \hspace{0.7cm} u\, \in \mathbb{Q}^{n} \hspace{4.2cm} \) è il vettore degli upper bound,\(  u_{i} \)

	\( \hspace{0.7cm} \text{I}\,\, \subseteq \{1,..,n\} \hspace{3.07cm} \) è un sottoinsieme degli indici relativo alla variabili intere

	\( \hspace{0.7cm} \text{B} \subseteq \{1,..,n\}\, : \, (\text{I} \cap \text{B}) = \emptyset \hspace{0.6cm} \) è un sottoinsieme degli indici relativo alla variabili binarie

Una formulazione come questa consente di applicare algoritmi di ottimizzazione lineare, come il metodo del simplesso, per trovare la soluzione ottimale che soddisfa tutti i vincoli e ottimizza la funzione obiettivo.

3.3 La Programmazione Lineare, Intera e Mista Intera in SSC

La libreria SSC offre due approcci principali per risolvere problemi di programmazione lineare: il metodo del simplesso e l'algoritmo Branch and Bound (B&B). Il simplesso è un algoritmo iterativo che cerca la soluzione ottimale muovendosi lungo i vertici del poliedro definito dai vincoli, risultando particolarmente efficiente anche per problemi su larga scala. L'algoritmo B&B, invece, è utilizzato per problemi di Programmazione Lineare Intera (ILP) e Programmazione Lineare Mista Intera (MILP), gestendo variabili discrete e vincoli complessi attraverso la suddivisione dell'albero di ricerca e la valutazione di limiti inferiori e superiori.

La classe LP della libreria è dedicata alla risoluzione di problemi di Programmazione Lineare standard (LP), dove tutte le variabili decisionali sono continue, ovvero possono assumere valori reali all'interno di un intervallo definito. Quando invece alcune variabili devono assumere valori interi, si passa alla Programmazione Lineare Intera (ILP) o alla Programmazione Mista Intera (MILP), gestite dalla classe MILP. Quest'ultima è in grado di risolvere problemi che combinano variabili intere e continue, così come problemi con variabili semicontinue. I problemi con presenza di variabii semicontinue sono una classe speciale di problemi di ottimizzazione in cui alcune delle variabili decisionali possono assumere solo valori pari a zero o valori all'interno di un intervallo continuo; ad esempio, sia [l, u] un intervallo continuo delimitato da l e u, allora una variabile x può essere definita semicontinua in un problema di PL se l ≤ x ≤ u oppure se x = 0, naturalmente con 0 ∉ [l, u].

Sia la classe LP che la classe MILP supportano il multithreading, permettendo un'implementazione parallela degli algoritmi di risoluzione. Questa funzionalità consente di sfruttare più thread per migliorare le prestazioni e offre vantaggi significativi su architetture con almeno quattro core fisici.

3.4 Special Ordered Sets (SOS)

Un Special Ordered Sets (SOS) è un insieme ordinato di variabili utilizzato nei modelli di ottimizzazione per specificare condizioni di integralità. A differenza della ramificazione su singole variabili, l'algoritmo ramifica su interi set di variabili, sfruttando l'ordine tra esse per migliorare l'efficienza della ricerca. Anche se le variabili nel set possono essere continue o discrete, l'uso di un SOS trasforma il problema in uno di ottimizzazione discreta, richiedendo l'uso di un risolutore di programmazione mista intera come il B&B. Il principale vantaggio è un'accelerazione nella procedura di ricerca. Gli SOS possono essere risolti in SSC attraverso l'utilizzo della classe MILP.

Esitono due tipi di SOS:
• SOS1: si tratta di un insieme di variabili in cui al massimo una di esse può assumere un valore diverso da zero, mentre tutte le altre devono essere pari a zero. Questo tipo di insieme è comunemente utilizzato quando le variabili sono di tipo 0-1, ovvero quando dobbiamo selezionare al massimo un'opzione tra più possibilità, ma possono anche essere intere o continue. Un esempio tipico è la scelta di uno tra diversi investimenti, si può scegliere solo una o nessuna tra le opzioni disponibili.
• SOS2: in questo caso si tratta di un insieme di variabili di cui al massimo due possono essere diverse da zero e, se lo sono, devono essere consecutive nel loro ordinamento. Gli SOS2 sono spesso utilizzati per rappresentare funzioni non lineari all'interno di un modello lineare. Sono un'estensione naturale del Separable Programming, ma integrati in un algoritmo Branch and Bound, permettono di ottenere soluzioni ottimali.

Oltre ai due tipi specificati, in SSC vengono implementati altri due tipi di SOS in presenza di variabili binarie:
• F-SOS1-B: (Forced SOS1-Binary), per indicare gli Special Ordered Sets di tipo 1 binari con la condizione di forzare la valorizzazione di una variabile. In questo caso il vincolo non è quello che solo una variabile può essere diversa da zero, ma quello che una variabile tra quelle costituenti il Set deve essere diversa da zero.
• F-SOS2-B: (Forced SOS2-Binary), per indicare gli Special Ordered Sets binari di tipo 2 con la stessa caratteristica, ovvero che due variabili consecutive tra quelle costituenti il Set devono essere diversa da zero.

3.5 Algortimo del Simplesso

Il metodo del simplesso è un algoritmo iterativo utilizzato per risolvere problemi di Programmazione Lineare. L'algoritmo inizia con una soluzione base iniziale, che è generalmente una soluzione ammissibile dei vincoli. Attraverso una serie di passi, il metodo sposta la soluzione lungo i vertici del poliedro definito dai vincoli, migliorando continuamente il valore della funzione obiettivo fino a raggiungere un punto in cui non è più possibile ottenere un miglioramento.
Il procedimento generale include la scelta della variabile da entrare nella base e quella da uscire, sulla base di un criterio di ottimalità. La complessità computazionale del metodo è nel caso peggiore esponenziale, ma in generale possiamo dire che ha un comportamento medio polinomiale nel numero di variabili e vincoli: nella pratica, l'algoritmo si comporta molto bene per la maggior parte dei problemi reali.
Il metodo del simplesso può essere implementato attraverso il metodo delle due fasi quando non si dispone di una soluzione base ammissibile iniziale. In questa procedura, si introducono delle variabili artificiali per trovare una soluzione iniziale ammissibile, che poi viene migliorata nel secondo stadio.
Le soluzioni restituite possono essere di diversi tipi: una soluzione ottima che soddisfa tutti i vincoli e ottimizza la funzione obiettivo, una soluzione illimitata se la funzione obiettivo può crescere indefinitamente senza violare i vincoli, o una soluzione vuota (o infeasibile) se non esiste alcuna soluzione che soddisfi tutti i vincoli.

3.6 Algortimo del Branch and Bound (B&B)

Il metodo del Branch and Bound (B&B) è un algoritmo utilizzato per risolvere problemi di Programmazione Lineare Intera (ILP) e misto intera (MILP), dove tutte o alcune variabili devono assumere valori interi. Questo metodo esplora sistematicamente un albero di decisioni, dove ogni nodo rappresenta un sottoproblema ottenuto rilassando o fissando alcune variabili intere. L'algoritmo parte da un rilassamento lineare del problema originale, risolvendo inizialmente questo rilassamento utilizzando il metodo del simplesso. Se la soluzione ottimale del rilassamento soddisfa i vincoli di integrità, allora essa è una soluzione ottima per il problema originale. In caso contrario, l'algoritmo suddivide il problema in due o più sottoproblemi (branching), ciascuno con ulteriori vincoli sulle variabili intere.
Ogni sottoproblema viene poi risolto nuovamente con il simplesso. Se un sottoproblema fornisce una soluzione ottimale intera, viene aggiornata la soluzione migliore trovata finora. I nodi dell'albero che non possono fornire una soluzione migliore vengono scartati (bounding). Il processo continua fino a quando tutti i sottoproblemi sono stati esplorati o eliminati. Sebbene il B&B abbia una complessità computazionale elevata, può risolvere molti problemi di ILP reali in tempi ragionevoli.

3.7 Dimensioni dei problemi e richiesta di memoria

Il metodo del simplesso è un algoritmo efficiente per risolvere problemi di programmazione lineare continui (cioè senza variabili intere), consentendo di affrontare problemi con un gran numero di variabili e vincoli. Quando si utilizza SSC per eseguire il simplesso, i limiti operativi sono legati principalmente alla quantità di memoria disponibile per la JVM. Ad esempio, specificando un massimo di 4 gigabyte di memoria con l'opzione -Xmx4g, è possibile risolvere problemi che coinvolgono migliaia di variabili e vincoli.
Per quanto riguarda il metodo Branch and Bound, la complessità è significativamente maggiore, poiché prevede la risoluzione di una serie di problemi tramite il simplesso. Ciò comporta un costo computazionale più elevato sia in termini di tempo che di risorse, rendendo i problemi di Programmazione Lineare Mista Intera (MILP) molto più limitati in termini di dimensioni rispetto ai problemi di LP puri.

3.8 Scalabilità e Stabilità numerica

Durante la risoluzione di problemi di programmazione lineare, la precisione dei calcoli può essere compromessa quando si operano valori molto grandi o molto piccoli insieme. Questo effetto, noto come instabilità numerica, può derivare da errori di arrotondamento o dall'accumulo di piccoli errori nei calcoli iterativi, come quelli dell'algoritmo del Simplesso. Per migliorare sia la stabilità numerica che le prestazioni, è fondamentale ridimensionare opportunamente i dati di input, mantenendo i coefficienti dei vincoli e della funzione obiettivo in intervalli simili, ancor meglio se idealmente vicino a 1. Ad esempio un vincolo :

10000X1 + 20000X2 <= 60000

È opportuno ridimensionarlo in un vincolo come :

X1 + 2X2 <= 6

Un metodo consigliato consiste nell'utilizzare unità di misura adeguate come migliaia di euro invece di euro se gli ammontari sono molto grandi, tonnellate al posto dei chili se i pesi sono rilevanti, etc. Un modello ben scalato minimizza l'impatto di questi errori e migliora l'efficacia dell'algoritmo nella selezione degli elementi pivot, portando a soluzioni più stabili e rapide.

4. Utilizzo della libreria

4.1 Formulazione del problema

In SSC per formulare un problema LP (o MILP) può essere utilizzato uno tra i diversi formati a disposizione. I formati utilizzabili risultano essere rispettimamente i seguenti :

Formato testo
Formato JSON
Formato a coefficienti
Formato matriciale
Formato sparso

Indipendentemente dal tipo di formato utilizzato per modellare il problema, i risultati dell'elaborazione sono ottenibili utilizzando le stesse interfaccie. Per cui indipendentemente dal formato utilizzato il modo per recuperare i risultati risulta sempre lo stesso.

4.1.1 Formato testo

Consideriamo la seguente formulazione matematica di un problema di Programmazione Lineare :

funzione obiettivo:
     min  3X₁ + X₂ - 4X₃ + 7X₄ + 8X₅
	 
vincoli:
     5X₁ +  2X₂      + 3X₄       ≥    9
     3X₁ +   X₂ +  X₃      + 5X₅  = 12.5
     6X₁ +3.1X₂ + 4X₃ + 5X₄       ≤   24
	 
limiti delle variabili:	  
           X₁ ≥ -1
      -1 ≤ X₂ ≤ +6
           X₃ ≤ -2
      -∞ ≤ X₄ ≤ +∞  
  
condizioni :   
         X₅ ≥ 0
         X₂, X₃ ∈ ℤ

Per rappresentare questo problema di Programmazione Lineare affinché sia elaborabile dalla libreria SSC si può utilizzare il formato testo (o testuale). In questo formato occorre fornire alla libreria il problema sotto forma di una stringa strutturata, che verrà successivamente parserizzata dalla libreria stessa. Questa stringa deve seguire una sintassi specifica che per l'esempio matematico appena descritto risulta essere :

public class Esempio {
    public static void main(String[] args) throws Exception {
         
        String lp_problem = 
        " min:  3x1 +X2 -4x3 +7x4 +8X5  \n"+ 
        " 5x1 +2x2 +3X4        >= 9     \n"+
        " 3x1 + X2 +X3 +5X5    =  12.5  \n"+
        " 6X1+3.1x2 +4X3 +5X4  <= 24    \n"+
        " x1 >= -1                      \n"+
        "-1 <= x2 <= 6                  \n"+
        " x3 <= -2                      \n"+
        " . <= x4 <= .                  \n"+
        " int x2, X3 ";
	}
}

Variabili: Nel formato testo le variabili possono avere qualsiasi nome (devono però iniziare con un carattere alfabetico seguito da caratteri alfanumerici) e risultano non essere case-sensitive (ovvero le variabili indicate con "x3" e "X3" rappresentano la stessa variabile).
Non è necessario elencare le variabili in un ordine specifico all'interno della funzione obiettivo o dei vincoli. Le variabili possono apparire in qualsiasi ordine, ad esempio "3x1 + X2" è equivalente a "X2 + 3x1".
Tra una variabile ed il suo coefficiente non deve essere mai presente uno spazio, mentre in tutti gli altri casi è possibile inserirne uno o più Ad esempio, "3x1+X2" è equivalente a "3x1 + X2".
Inoltre, se una variabile appare più volte all'interno della stessa espressione, sia nella funzione obiettivo che nei vincoli, i coefficienti associati a quella variabile verranno sommati automaticamente. Per esempio, le espressioni "4Y + 2X2 + Y >= 9" e "3Y +X2 >= 9 - X2 -2Y" saranno interpretate entrambe come "5Y + 2X2 >= 9". Questo avviene sia per garantire più flessibilità che per evitare errori di ridondanza nella definizione delle variabili.
Le variabili e i vincoli non devono essere allineati verticalmente o orizzontalmente. Le espressioni possono essere scritte in modo disallineato, senza la necessità di formattare il testo per allineare i termini. Questo permette di scrivere le espressioni in maniera più libera e meno vincolata dalla formattazione.

Coeficienti delle variabili: Nel formato testo i coefficienti delle variabili possono essere semplici numeri sia interi che decimali, naturalmente ha senzo mettere la parte frazionaria solo se questa è presente. Nell'esempio sopra riportato, il vincolo :

6X1 +3.1x2 +4X3 +5X4 <= 24

ha la variabile X₂ che ha per coefficiente 3.1 che ha una parte frazionaria. Occorre ricordare che il coefficiente della prima variabile presente a partire dalla sinistra di un vincolo o il numero presente dopo il segno di uguaglianza o disuguaglianza di un vincolo, se positivo, non necessita del segno + , in tutti gli altri casi occorre inserire il segno del coefficiente. Naturalmente se una variabile ha coefficiente 1 questo può essere omesso.

Funzione obiettivo: La prima riga della stringa specifica la funzione obiettivo; essa è preceduta da "min:" o "max:" per indicare se si desidera minimizzare o massimizzare tale funzione. Nel nostro esempio:

min: 3x1 +X2 -4x3 +7x4 +8X5

rappresenta la funzione obiettivo da minimizzare.

Vincoli: Le righe successive specificano i vincoli del problema, che devono essere espressi come disuguaglianze (">=" , "<=") o uguaglianze ("="). Ogni vincolo deve essere una combinazione lineare delle variabili. Ad esempio:

5x1 +2x2 +3X4 >= 9

è un vincolo di disuguaglianza. In un vincolo le variabili possono anche essere poste sul lato destro della disuguaglianza o uguaglianza, ovvero :

5x1 +2x2 >= 9 -3X4

è sempre una formulazione valida di vincolo.

Ai vincoli del problema possono essere assegnate delle etichette o nomi. Questi nomi non devono essere necessariamente univoci per ciascun vincolo, in tal caso una singola etichetta puo essere utilizzata per più vincoli per identificarli come appartenenti ad un gruppo specifico. Dare un nome o una etichetta ha il solo scopo di identificare un vincolo o un gruppo di vincoli; difatti in fase di recupero ed interpretazione dei risultati sarà possibile identificare ciascun vincolo a partire dalla sua etichetta insieme alle altre caratteristiche. Per definire una etichetta su un vincolo, basta anteporre al vincolo stesso il nome seguito dai due punti ":", come nell'esempio seguente :

vincolo1: 5X1 +2X2 +3X4 >= 9

Le etichette dei vincoli sono singole parole (non separate da spazi) che devono iniziare con un carattere alfabetico seguito da caratteri alfanumerici (lettere e numeri).

Vincoli sulle variabili: È possibile specificare limiti inferiori e superiori per le variabili (upper bound e lower bound) utilizzando la sintassi "l <= x <= u" oppure "x >= l" o "x <= u", dove l e u rappresentano i limiti. Se non sono specificati, le variabili sono considerate non negative di default. Nell'esempio sopra riportato, la seguente dichiarazione :

X1 >= -1

indica un lower bound sulla variabile X₁. Quando si definisce un lower bound negativo, come in questo caso, la variabile non è più vincolata alla non negatività e può assumere valori anche inferiori a zero. È importante notare che questa dichiarazione implica che la variabile X₁ può avere qualsiasi valore maggiore o uguale a -1, inclusi valori negativi. Tuttavia, se specifichiamo il segno della variabile sulla definizione di un upper o lower bound, come ad esempio:

+X1 >= -1

stiamo in realtà solo definendo un vincolo e non un lower bound, senza eliminare il vincolo di non negatività In altre parole, stiamo dicendo che X₁ deve essere maggiore o uguale a -1, ma, poiché la variabile è esplicitamente non negativa per impostazione predefinita, X₁ sarà limitata a valori non negativi che soddisfano la condizione X₁ >= -1. Pertanto, la variabile non potrà mai essere minore di zero, anche se il vincolo è fissato a -1. Questo significa che:

• se dichiariamo X₁ >= -1 , stiamo definendo un lower bound e la variabile è libera di assumere qualsiasi valore a partire da -1, inclusi valori negativi.
• se inseriamo il segno (+/-) e dichiariamo +X₁ >= -1, stiamo definendo un vincolo e la variabile rimane soggetta alla condizione di non negatività e assumerà solo valori maggiori o uguali a zero, anche se il vincolo stabilisce che deve essere maggiore di -1.

Partendo dal nostro esempio consideramo la vairabile X₂ che ha un vincolo del tipo "l <= x <= u", ovvero :

-1 <= X2 <= 6

Questo vincolo può essere espresso in modo equivalente con la notazione inversa "u >= x >= l", ovvero:

6 >= X2 >= -1

Le due notazioni sono perfettamente equivalenti e descrivono lo stesso intervallo per la variabile X₂.

Variabili libere o negative: Per poter dichiarare variabili libere, ovvero variabili senza limite inferiore (il limite inferiore non sarà più lo zero ma -infinito), basta specificare un lower bound indefinito. Se si dichiara un valore indefinito su un lower bound o su un upper bound, SSC trasforma tali valori in -infinito nel primo caso ed in +infinito nel secondo. Nel formato testo il valore indefinito si rappresenta con il punto ".". In generale per poter impostare delle variabili libere basta valorizzare un lower bound indefinito; ad esempio nel nostro caso la variabile X₄ può assumere valori in [-∞,+∞] tramite la dichiarazione :

. <= X4 <= .

Per poter impostare delle variabili che possono assumere valori anche in un range negativo basta valorizzare o un lower bound negativo o un upper bound negativo. Nell'esempio sopra riportato si definisce una variabile x₁ che può assumere valori in [-1,+∞] (ovvero valori negativi maggiori di -1 e positivi) e una variabile x₃ che può assumere solo valori negativi in [-∞,-2] con le seguenti istruzioni:

x1 >= -1        
x3 <= -2

Variabili Intere: Per problemi di programmazione lineare intera mista (MILP), le variabili che devono assumere valori interi vengono dichiarate con il prefisso "int". Ad esempio nel nostro esempio:

int X2, X3

specifica che X₂ e X₃ devono essere intere.

Variabili binarie: Per problemi di programmazione lineare con variabili binarie, le variabili che devono assumere valori in {0,1} vengono dichiarate con il prefisso "bin". Per cui usando la notazione :

bin X2, X3

si specifica che X₂ e X₃ devono essere binarie.

Variabili semicontinue: È possibile risolvere problemi di programmazione lineare con variabili semicontinue. Ricordiamo che una variabile semicontinua può essere o pari a zero oppure deve appartenere a un intervallo continuo delimitato; ad esempio, sia [l, u] un intervallo continuo delimitato da l e u tale che "l > 0", allora una variabile x è semicontinua in un problema LP se "l ≤ x ≤ u" oppure se "x = 0", naturalmente con 0 ∉ [l, u]. Per definire delle variabili semicontinue, occorre far precedere le variabili interessate dal prefisso "sec", ad esempio :

sec x4, X5

Naturalmente se definiamo una qualsiasi variabile X semicontinua con il prefisso "sec", questa deve anche essere dichiarata limitata tramite un vincolo del tipo :

l <= X <= u

Caratteri o parole Jolly: Se in un problema di Programmazione lineare occorre impostare che la totalità delle variabili sia intera è possibile utilizzare la parola "ALL"; ad esempio se, utilizzando il formato testo, usiamo questa sintassi :

int ALL

stiamo allora dichiarando che tutte le variabili del problema sono intere. Questa sintassi può essere usata per dichiararle tutte binarie ("bin ALL") o semicontinue ("sec ALL"). Nel formato testo è possibile usare anche il carattere jolly "*", per dichiarare che tutte le variabili che iniziano con un determinato prefisso appartengano ad una determinata classe di variabili. Ad esempio con la notazione:

int X*
bin Y*

si dichiara che tutte le variabili che iniziano per X sono intere, mentre quelle che iniziano per Y sono binarie e le rimanenti reali. Ricordiamo che ciascuna dichiarazione di tipo "int", "bin", "sec", se usate contemporaneamente nella stessa formulazione, vanno poste su righi distinti.

SOS (Special Ordered Set): In SSC è possibile definire gli Special Ordered Sets (SOS) che sono insiemi ordinati di variabili con vincoli aggiuntivi sul loro comportamento, utili per problemi di ottimizzazione complessi. La libreria supporta sia SOS di tipo 1 (SOS1) che SOS di tipo 2 (SOS2), incluse varianti binarie, intere e forzate.

Un insieme SOS1 limita il set di variabili in modo che solo una variabile possa essere diversa da zero, mentre tutte le altre devono essere pari a zero. Ecco un esempio di istruzione da aggiungere nella formulazione del problema per dichiarare un insieme SOS1 :

sos1 X1,X2,X3

Questo dichiara che solo una tra X₁, X₂ e X₃ può essere diversa da zero, mentre le altre devono essere uguali a zero.
Se le variabili del set SOS1 devono essere binarie (cioè 0 o 1), si utilizza :

sos1:bin X1,X2,X3

In questo caso, solo una tra X₁, X₂ e X₃ puè essere uguale a 1, mentre tutte le altre devono essere 0.
Per dichiarare che le variabili sono intere, si può usare:

sos1:int X1,X2,X3

Questo vincola le variabili X₁, X₂ e X₃ ad assumere valori interi, con il vincolo che solo una di queste può assumere valori diversi da zero.
Nel caso volessimo forzare in un insieme SOS1 di variabili binarie, una variabile a essere valorizzata, possiamo utilizzare la notazione:

sos1:bin:force X1,X2,X3

In questo caso, una delle variabili sarà necessariamente diversa da zero, mentre le altre saranno pari a zero. L'opzione force può essere usata solo su insiemi binari di variabili.
La libreria consente di usare un carattere jolly "*" per includere tutte le variabili che iniziano con un certo prefisso ad appartenere ad un SOS di tipo 1. Ad esempio:

sos1 X*

Questo include tutte le variabili che iniziano con "X" nel set di tipo SOS1.

Un insieme SOS2 limita il set di variabili in modo che al massimo due variabili possano essere diverse da zero e, se entrambe sono diverse da zero, devono essere contigue nel loro ordine. L'ordine delle variabili è fondamentale:

sos2 X2,X3,X1

In questo caso, al massimo due delle variabili X₂, X₃ e X₁ possono essere diverse da zero, e devono essere contigue nell'ordine dichiarato, ad esempio, (X₂, X₃) o (X₃, X₁). Se vogliamo che le variabili in un SOS2 siano binarie o intere o forzate binarie, possiamo utilizzare le seguenti sintassi analoghe al SOS1:

sos2:bin X2,X3,X1
sos2:int X2,X3,X1
sos2:bin:force X2,X3,X1

A differenza di SOS1, in SOS2 non è possibile usare il carattere jolly *, poiché va esplicitamente dichiarato l'ordine delle variabili attraverso la dichiarazione "sos2 Z,X,Y,K...".

È possibile dichiarare più set SOS nello stesso problema di programmazione lineare, basta scrivere le dichiarazioni su righe separate. Ad esempio, se si desidera dichiarare un set SOS1 con variabili binarie e un altro set SOS1 binario con una variabile forzata nella valorizzazione, si può fare così:

sos1:bin X1,X2,X3
sos1:bin:force X4,X5,X6

Possiamo ora fare un esempio di utilizzo degli SOS con variabili miste. Supponiamo di voler dichiarare una serie di set SOS1 e SOS2 in un problema di programmazione lineare. Il codice potrebbe essere simile a questo:

// Dichiarazione di un set SOS1 di variabili miste
sos1 X1,X2,X3,X4,X5
int X1,X2
bin X3,X4

// Dichiarazione di un set SOS2 di variabili binarie
sos2:bin Y1,Y2,Y3

// Dichiarazione di un set SOS1 binario con variabile forzata
sos1:bin:force Z1,Z2,Z3

Esempi completi di modellazione di problemi che utilizzano il formato testuale sono riportati nella sezione Esempi di questo sito, dimostrando come rappresentare sia problemi di LP standard (esempi 1.1 , 1.6 , 1.11) che MILP (esempi 2.7, 2.9, 2.16, 2.17, 2.18, 2.19, 3.1). La libreria parserizza automaticamente le espressioni presenti nella stringa e le traduce in un modello matematico che può essere risolto utilizzando algoritmi come il simplesso o il branch and bound.

4.1.2 Formato JSON

Consideriamo la seguente formulazione matematica di un problema di Programmazione Lineare :

funzione obiettivo:
     min  3X₁ + X₂ - 4X₃ + 7X₄ + 8X₅
	 
vincoli:
     5X₁ +  2X₂      + 3X₄       ≥    9
     3X₁ +   X₂ +  X₃      + 5X₅  = 12.5
     6X₁ +3.1X₂ + 4X₃ + 5X₄       ≤   24
	 
limiti delle variabili:	  
           X₁ ≥ -1
      -1 ≤ X₂ ≤ +6
           X₃ ≤ -2
      -∞ ≤ X₄ ≤ +∞  
  
condizioni :   
         X₅ ≥ 0
         X₂, X₃ ∈ ℤ

La libreria supporta la formulazione di problemi di Programmazione Lineare (LP) in formato JSON, che consente una rappresentazione strutturata della funzione obiettivo, dei vincoli, dei limiti sulle variabili. Ecco come è possibile rappresentare un problema con questo formato:


public class Esempio {
    public static void main(String[] args) throws Exception {
    	    	
	//Questo esempio utilizza i Text Blocks """, presenti da java 15. 
	//Se si dispone di una versione di java precedente usare le stringhe standard.

	String stringJson = """
	 { 
		"objective": { 
			"type": "min", 
			"coefficients": {  
				"X1": 3, 
				"X2": 1, 
				"X3":-4, 
				"X4": 7, 
				"X5": 8 
			} 
		}, 
		"constraints": [ 
			{ 
				"coefficients": { 
					"X1": 5, 
					"X2": 2, 
					"X4": 3 
				}, 
				"relation": "ge", 
				"rhs": 9, 
				"name":"ConstraintA" 
			}, 
			{ 
				"coefficients": { 
					"X1": 3, 
					"X2": 1, 
					"X3": 1, 
					"X5": 5 
				}, 
				"relation": "eq", 
				"rhs": 12.5, 
				"name":"ConstraintB" 
			}, 
			{ 
				"coefficients": { 
					"X1": 6, 
					"X2":3.1, 
					"X3": 4, 
					"X4": 5 
				}, 
				"relation": "le", 
				"rhs": 24, 
				"name":"ConstraintC" 
			} 
		], 
		"bounds": { 
			"X1": { 
				"lower": -1 
			}, 
			"X2": { 
				"lower": -1, 
				"upper": 6 
			}, 
			"X3": { 
				"upper": -2 
			}, 
			"X4": { 
				"lower": null,
				"upper": null 
			} 
		}, 
		"variables": { 
			"x2": "integer", 
			"X3": "integer" 
		} 
	 }""";

	JsonProblem jsonProb=new JsonProblem(stringJson); 
	}
}

Il codice sopra descritto vuole mettere in evidenza, in questa parte iniziale della guida, solo il formato di rappresentazione di un problema di LP, di conseguenza non risulta completo. L'esempio completo è riportato nella pagina Esempi (esempio 3.5) di questo sito.

Il formato JSON utilizzato è suddiviso in sezioni, ognuna delle quali è rapresentata da una chiave JSON. Ad esempio per rappresentare la funzione obiettivo occorre definire la chiave "objective". Va ricordato che tutte le chiavi ed i valori stringa devono essere riportati in minuscolo, fatto salvo i nomi delle variabili del problema di LP ed il nome (facoltativo) da assegnare ai vincoli.

La libreria SSC utilizza una implementazione di jakarta.json per gestire il parsing dei file JSON. Va notato che tale implementazione non genera un errore di parsing quando trova chiavi duplicate all'interno di un oggetto JSON. In tali casi, solo l'ultima chiave duplicata viene considerata valida, e il suo valore sovrascrive eventuali valori precedenti associati alla stessa chiave. Questo comportamento potrebbe non essere immediatamente evidente, quindi è consigliato evitare chiavi duplicate all'interno delle definizioni JSON per garantire risultati corretti.

Una volta rappresentato il problema, si crea un oggetto delle classe JsonProblem, passandogli come argomento la stringa contenente il JSON stesso (nel caso di un file JSON, si passa l'oggetto Path relativo al percorso del file, vedi esempio 1.17). Ma analizziamo ciascun elemento del formato JSON.

Funzione obiettivo: Nella formulazione del problema, la funzione obiettivo è descritta tramite la sezione "objective". Qui puoi specificare il tipo (type) di ottimizzazione, che può essere "max" o "min", e definire i coefficienti (coefficients) delle variabili da ottimizzare, come di seguito specificato:

"objective": {
    "type": "min",
    "coefficients": {
        "X1": 3,
        "X2": 1, 
        "x3":-4, 
        "X4": 7, 
        "X5": 8 
    }
}

Come possiamo notare sia i nomi delle chiavi ("objective","type", "coefficients") che i valori "min" vanno indicati in minuscolo. Al contrario i nomi da dare alle variabili non sono case-sensitive, per cui "X3" e "x3" rappresentano la stessa variabile.

Vincoli: I vincoli sono specificati nella sezione "constraints", dove ogni vincolo è un elemento di un array e viene descritto tramite i coefficienti delle variabili coinvolte, la relazione (maggiore o uguale "ge", minore o uguale "le" , uguale "eq") e il valore del termine destro "rhs". Opzionalmente è possibile assegnare un nome al vincolo tramite la proprietà "name". Di seguito una rappresenttazione di un vincolo del problema sopra specificato:

"constraints": [
    {
        "coefficients": {
            "Y" : 5,
            "X2": 2,
            "X4": 3
        },
        "relation": "ge",
        "rhs": 9,
        "name": "VINCOLO1"
    },
    ...
    ...
]

Limiti delle variabili: I limiti sulle variabili sono definiti nella sezione "bounds". Se non specificati (ovvero se mancano tali sezioni), le variabili sono considerate non negative di default. Puoi specificare i limiti inferiori e superiori per ciascuna variabile, indicando null se ci sono limiti infiniti inferiori o superiori:

"bounds": { 
	"X1": { 
		"lower": -1 
	}, 
	"X2": { 
		"lower":-1, 
		"upper": 6 
	}, 
	"X3": { 
		"upper": -2 
	}, 
	"X4": { 
		"lower": null,
		"upper": null 
	} 
}

Il codice JSON sopra riportato sta ad indicare :

1) che la variabile X₁ può assumere valori in [-1,+∞].
2) che la variabile X₂ può assumere valori in [-1,6] , ovvero una variabile che può assumere valori negativi maggiori di -1 o positivi minori di 6.
3) che la variabile X₃ può assumere solo valori negativi in [-∞,-2].
4) che la variabile X₄ può assumere valori [-∞,+∞] o libera.
5) che la variabile X₅, non essendo stata modificata nei limiti, può assumere valori in [0,+∞].

Naturalmente specificare un upper bound infinito (con l'istruzione "upper": null ) è in realtà superfluo dato che le variabili, essendo per default non negative, hanno gia tale limite. Abbiamo inserito questo esempio per specificare quali valori possono essere assegnati alle proprietà "upper" e "lower" ed il loro significato.

Variabili libere o negative: Per poter dichiarare variabili libere, ovvero variabili senza limite inferiore (il limite inferiore non sarà più lo zero ma -infinito), basta specificare un lower bound indefinito. Se si dichiara un valore indefinito sulle proprietà "lower" o "upper", SSC trasforma tali valori in -infinito nel primo caso ed in +infinito nel secondo. Nel formato JSON il valore indefinito si rappresenta con il null. In generale per poter impostare delle variabili che possono assumere valori anche in un range negativo, basta valorizzare un lower bound indefinito (come sulla X₄) o negativo (come sulla X₁), oppure un upper bound negativo (come sulla X₃).

Tipologia delle variabili: Per problemi di Programmazione Lineare Intera Mista (MILP), è possibile dichiarare quali variabili devono assumere valori interi, binari o semicontinui. La natura delle variabili (ad esempio, se sono continue, intere, binarie) può essere definita nella sezione "variables". In questo esempio, le variabili X₂ e X₃ sono dichiarate intere:

"variables": { 
	"x2": "integer",
	"X3": "integer" 
}

A seconda che siano intere, binarie, semicontinue o semicontinue intere, si utilizzano rispettivamente i valori "integer","binary" ,"semicont" e "integer-semicont". Ricordiamo che il JSON è un formato che richiede chiavi univoce sugli oggetti in esso definiti, per cui se una variabile è intera e semicontinua, non usate sulla stessa variabile i valori "integer" e "semicont" duplicando la chiave relativa al nome di qualche variabile per assegnarli tali valori, ma usate il valore predisposto, ovvero "integer-semicont".

4.1.3 Formato a coefficienti

Consideriamo la seguente formulazione matematica di un problema di Programmazione Lineare :

funzione obiettivo:
     min  3X₁ + X₂ - 4X₃ + 7X₄ + 8X₅
	 
vincoli:
     5X₁ +  2X₂      + 3X₄       ≥    9
     3X₁ +   X₂ +  X₃      + 5X₅  = 12.5
     6X₁ +3.1X₂ + 4X₃ + 5X₄       ≤   24
	 
limiti delle variabili:	  
           X₁ ≥ -1
      -1 ≤ X₂ ≤ +6
           X₃ ≤ -2
      -∞ ≤ X₄ ≤ +∞  
  
condizioni :   
         X₅ ≥ 0
         X₂, X₃ ∈ ℤ

Per rappresentare questo problema di Programmazione Lineare affinché sia elaborabile dalla libreria SSC si può utilizzare il formato a coefficienti. In questo formato si definiscono dei dati strutturati dove ciascun rigo (record) rappresenta o la funzione obiettivo, o un vincolo, o la definizione di caratteristiche per le variabili. Per separare le diverse espressioni, queste devono appunto trovarsi su righi differenti; per questo motivo alla fine di ogni espressione è presente il catattere "\n" di nuova linea.
In questo formato le colonne rappresentano i coefficienti delle variabili, le relazioni, i termini noti (o valori rhs). Questi dati strutturati devono seguire una sintassi che viene definita dall'utilizzatore come nell'esempio riportato di seguito :

import org.ssclab.ref.InputString;
public class Esempio {
    public static void main(String[] args) throws Exception {
 
        String milp_coeff =     " 3   1 -4  7  8 min      .       \n"+
                                " 5   2  0  3  0 ge       9       \n"+
                                " 3   1  1  0  5 eq       12.5    \n"+
                                " 6 3.1  4  5  0 le       24      \n"+
                                "-1  -1  .  .  0 lower    .       \n"+
                                " .   6 -2  .  . upper    .       \n"+
                                " 0   1  1  0  0 integer  .         " ;  
 
        InputString milp_input = new InputString(milp_coeff);
        milp_input.setInputFormat("X1:double,X2:double,X3:double,X4:double,X5:double, TYPE:varstring(8),  RHS:double");
	}
}

InputString milp_input = new InputString(milp_coeff);
milp_input.setInputFormat("X1:double,X2:double,X3:double,X4:double,X5:double, TYPE:varstring(8),  RHS:double");

La stringa che contiene la formulazione del problema (milp_coeff) viene passata al costruttore della classe InputString per creare una istanza di questa classe; su tale istanza è possibile invocare il metodo setInputFormat(). Ebbene, la definizione del formato di input si effettua attraverso una stringa da passare come argomento al metodo setInputFormat(); in questa stringa si susseguono, separate da virgola, le notazioni "nome variabile:tipologia variabile" per definire, in sequenza, i nomi delle variabili da associare alla colonne ed il tipo di dato presente nelle colonne.

Sebbene si parli di 'colonne', ciò serve solo a semplificare la comprensione: il primo dato di ogni riga presente nella stringa milp_coeff viene associato alla prima variabile dichiarata, il secondo dato alla seconda variabile dichiarata, e così via. Non è necessario che i coefficienti siano allineati rigorosamente in verticale (ovvero che si trovino tutti sul k-esimo carattere di ciascun rigo); l'importante è che siano separati da almeno uno spazio e che seguano la sequenza corretta. Il termine 'colonna' è stato introdotto solo per identificare in modo concettuale i coefficienti di una variabile sui vari vincoli e sulla funzione obiettivo o i termini noti.

Riprendendo il nostro esempio abbiamo che i valori delle prime 5 colonne relative alle variabili del problema di LP vengono memorizzate nelle variabili X1, X2, X3, X4, X5 di tipo numerico double; i valori della colonna delle relazioni vengono memorizzati in una variabile chiamata TYPE (di tipo stringa e con lunghezza di 8 caratteri); i valori della colonna dei termini noti vengono memorizzati nella variabile RHS di tipo double.
I nomi da assegnare alle variabili del problema di LP sono scelti dall'analista (devono però iniziare con un carattere alfabetico seguito da caratteri alfanumerici), mentre la colonna delle relazioni e quella dei termini noti devono necessariamente essere memorizzate in variabili chiamate TYPE e RHS.

Di norma possiamo chiamare le variabili anche con nomi non necessariamente seguiti da un numero, ad esempio: "PRICE:double, AMOUNT:double, WEIGHT:double", etc, etc. Di solito è preferibile dichiarare le n variabili di un problema con una diversa notazione, chiamata ad intervalli, che risulta particolarmente utile se le variabili del problema sono decine o centinaia. In questo caso la dichiarazione "X1:double, X2:double, X3:double, .... , Xn:double" di n variabili, può essere sostituita con la notazione "X1-Xn:double". Consideriamo un esempio teorico: supponiamo di avere un problema con 7 variabili che desideriamo suddividere in due gruppi; in questo caso, possiamo utilizzare due distinti prefissi, ad esempio "PRICE1-PRICE3:double,COST1-COST4:double". Tornando al nostro esempio ed utilizzando la notazione ad intervalli, il formato di input cambia in :

milp_input.setInputFormat("X1-X5:double, TYPE:varstring(8),  RHS:double");

Questa seconda notazione, certamente più compatta, permette di dichiarare tutte le variabili comprese nell'intervallo che va da X1 a X5. Ricordiamo inoltre che la dichiarazione delle variabili ad intervalli non deve partire necessariamente da 1, nel nostro caso possiamo anche scrivere "X6-X10:double"

La colonna da associare alla variabile TYPE viene utilizzata per definire il 'tipo' di espressione contenuta in una riga, ad esempio: vincolo o funzione obiettivo. Se il valore è "min" oppure "max" , la riga verrà interpretata cone un f.o; mentre se assume uno dei valori in {"eq","le","ge"} verrà interpretata come vincolo. La variabile TYPE può assumere solo i seguenti valori che possono essere scritti sia in minuscolo che in maiuscolo:

min, max, eq, le, ge, lower, upper, integer, binary, semicont

La variabile TYPE è dichiara di tipo varstring(8) affichè possa contenere valori con al più 8 catatteri (difatti il valore "semicont" è il piu lungo e conta 8 caratteri). Infine occorre dichiarare la variabile RHS che contiene i termini noti. Ricordiamo ancora che nella definizione del formato di input è obbligatorio dichiarare una variabile TYPE e una variabile RHS da associare ai relativi valori presenti nella formulazione del problema.

Analizziamo ora le diverse espressioni (righi) attraverso le quali si formula un problema di Programmazione Lineare utilizzando il formato a coefficienti:

Funzione obiettivo: Nella formulazione del problema riportata sopra, la prima riga della stringa milp_coeff specifica i coefficienti della funzione obiettivo e l'operazione di ottimizzazione ("min" o "max"). Ovvero la riga :

3 1 -4 7 8 min .

indica la funzione obiettivo (f.o.) da minimizzare, con i coefficienti 3, 1, -4, 7 e 8 rispettivamente associati alle variabili X₁, X₂, X₃, X₄ e X₅. Segue poi il tipo di funzione obiettivo che è di tipo "min". Infine sulla colonna rhs abbiamo un punto (".") che rappresenta un valore indefinito. Ciò è dovuto al fatto che nel formato a coefficienti ogni variabile dichiarata deve avere, su ogni rigo, associato un valore; in questo caso inseriamo un valore indefinito, da associare alla colonna relativa ai valori rhs, in quanto irrilevante nella definizione della funzione obiettivo.
Nel formato a coefficienti, a differenza di quello testuale, ogni singolo valore letto, separato dagli altri da uno o più spazi, deve essere compiutamente significativo, per cui quando si inserisce il segno davanti ad un numero questo deve essere rigorosamente unito al numero stesso senza nessun spazio che li separi. Infine i vari coefficienti non necessitano di segno se questo è positivo.

Vincoli: Le righe successive rappresentano i vincoli del problema. Ogni vincolo è specificato dai coefficienti delle variabili, seguito dal tipo (TYPE) di disuguaglianza ("ge" per ≥, "le" per ≤, "eq" per =) e dal valore del lato destro rhs (o termine noto). Ad esempio, la riga :

5 2 0 3 0 ge 9

rappresenta il vincolo 5X₁+2X₂+3X₄ ≥ 9. Da quanto detto in precedenza, ovvero che ogni variabile dichiarata deve avere un valore su ogni rigo, ne consegue che se su un vincolo una variabile non è presente, il relativo coefficiente dovrà comunque essere indicato, ma uguale a zero.

Limiti sulle variabili: È possibile specificare limiti superiori e inferiori per le variabili utilizzando righe dedicate. La sintassi segue lo schema "u a b c d e upper ." per i limiti superiori e "l n o p q r lower ." per i limiti inferiori, dove "u" ed "l" rappresentano i valori dei limiti per la prima variabile dichiarata nel formato di imput, "a" ed "n" rappresentano i valori dei limiti per la seconda e cosi via. Se non specificati (ovvero se mancano tali righi), le variabili sono considerate non negative di default. Nell'esempio sopra riportato, l'espressione:

-1  -1  .  .  0 lower    . 
 .   6 -2  .  . upper    .

sta ad indicare :

1) che la prima variabile dichiarata nel formato di input (la X₁) può assumere valori in [-1,.] , ovvero [-1,+∞].
2) che la seconda variabile dichiarata (la X₂) può assumere valori in [-1,6] , ovvero una variabile che può assumere valori negativi maggiori di -1 o positivi minori di 6.
3) che la terza variabile dichiarata (la X₃) può assumere valori in [.,-2] , ovvero può assumere solo valori negativi in [-∞,-2].
4) che la quarta variabile dichiarata (la X₄) può assumere valori in [.,.] , ovvero [-∞,+∞] o libera.
5) che la quinta variabile dichiarata (la X₅) può assumere valori in [0,.] , ovvero [0,+∞] .

Variabili libere o negative: Per poter dichiarare variabili libere, ovvero variabili senza limite inferiore (il limite inferiore non sarà più lo zero ma -infinito), basta specificare un lower bound indefinito. Se si dichiara un valore indefinito sulla riga dei lower bound o sulla riga degli upper bound, SSC trasforma tali valori in -infinito nel primo caso ed in +infinito nel secondo. Nel formato a coefficienti il valore indefinito si rappresenta con il punto "." . In generale per poter impostare delle variabili che possono assumere valori anche in un range negativo, basta valorizzare un lower bound indefinito (come sulla X₄) o negativo (come sulla X₁), oppure un upper bound negativo (come sulla X₃).

Variabili Intere: Per problemi di Programmazione Lineare Intera Mista (MILP), è possibile dichiarare quali variabili devono assumere valori interi. Ciò viene fatto utilizzando una riga che ha per TYPE il valore "integer" e che specifica, tramite i valori 1 e 0, quali variabili devono essere intere e quali no. La dichiarazione presente nell'esempio sopra riportato:

0 1 1 0 0 integer .

specifica che le variabili X₂ e X₃ devono essere intere.

Variabili Binarie: Per problemi di Programmazione Lineare Intera Mista (MILP) , è possibile dichiarare quali variabili devono assumere valori binari {0,1}. Ciò viene fatto utilizzando una riga che ha per TYPE il valore "binary" e che specifica, tramite i valori 1 e 0, quali variabili devono essere binarie e quali no. Ad esempio, la dichiarazione:

1 0 0 0 0 binary .

specifica che la prima variabile dichiarata nel formato di input deve essere binaria.

Variabili semicontinue: È possibile risolvere problemi di programmazione lineare con variabili semicontinue. Ricordiamo che una variabile semicontinua può essere o pari a zero oppure deve appartenere a un intervallo continuo delimitato. Ad esempio, sia [l, u] un intervallo continuo delimitato da l e u, allora una variabile x può essere definita semicontinua in un problema LP se l ≤ x ≤ u oppure se x = 0, naturalmente con 0 ∉ [l, u]. Per definire delle variabili semicontinue, occorre aggungere una riga che ha per TYPE il valore "semicont" e che specifica, tramite i valori 1 e 0, quali variabili devono essere semicontinue e quali no, ad esempio con la notazione:

1 0 0 1 0 semicont .

Stiamo dichiarando che la prima e la quarta variabile dichiarate nel formato di input sono semicontinue. Naturalmente se definiamo una variabile x semicontinua , questa deve essere dichiarata anche limitata tramite un vincolo del tipo l ≤ x ≤ u , e quindi occorre definire per la suddetta variabile anche i valori di upper e lower bound.

Esempi completi di modellazione di problemi che utilizzano il formato a coefficienti sono riportati nella sezione Esempi di questo sito, dimostrando come rappresentare sia problemi di LP standard (esempi 1.2 , 1.4 , 1.8 , 1.10 1.14), sia problemi di MILP (esempi 2.1, 2.4 , 2.10, 3.2). La libreria parserizza automaticamente le espressioni presenti nella stringa e le traduce in un modello matematico che può essere risolto utilizzando algoritmi come il simplesso o il branch and bound.

4.1.4 Formato matriciale

Consideriamo la seguente formulazione matematica di un problema di Programmazione Lineare :

funzione obiettivo:
     min  3X₁ + X₂ - 4X₃ + 7X₄ + 8X₅
	 
vincoli:
     5X₁ +  2X₂      + 3X₄       ≥    9
     3X₁ +   X₂ +  X₃      + 5X₅  = 12.5
     6X₁ +3.1X₂ + 4X₃ + 5X₄       ≤   24
	 
limiti delle variabili:	  
           X₁ ≥ -1
      -1 ≤ X₂ ≤ +6
           X₃ ≤ -2
      -∞ ≤ X₄ ≤ +∞  
  
condizioni :   
         X₅ ≥ 0
         X₂, X₃ ∈ ℤ

Per rappresentare questo problema di Programmazione Lineare affinché sia elaborabile dalla libreria SSC si può utilizzare il formato matriciale. Questo formato è simile a quello di Apache Simplex Solver ed è particolarmente utile per rappresentare problemi di programmazione lineare in modo strutturato, consentendo di manipolare facilmente le varie componenti del problema attraverso l'uso di vettori e matrici (array e matrici java). Occorre quindi definire la matrice A[][] dei coefficienti, il vettore c[] dei coefficienti della f.o. ed il vettore b[] dei valori rhs (o termini noti). Naturalmente alla matrice ed ai vettori possono esssere dati nomi diversi.
Il codice Java che segue mostra un esempio di sintassi per rappresentare il problema di LP sopra riportato utilizzando il formato matriciale:

import org.ssclab.pl.milp.*;
import static org.ssclab.pl.milp.ConsType.*;
import static org.ssclab.pl.milp.LP.NaN;

public class Esempio {
     
    public static void main(String[] args) throws Exception {
	
        double c[]  = 
                { 3.0,  1.0, -4.0,  7.0,  8.0 };  //vettore dei coefficienti della f.o. 
		
        double A[][]={ 
                { 5.0 , 2.0 , 0.0 , 3.0 , 0.0 },
                { 3.0 , 1.0 , 1.0 , 0.0 , 5.0 },
                { 6.0 , 3.1 , 4.0 , 5.0 , 0.0 },
                { NaN , 6.0 ,  -2 , NaN , NaN },  //rigo degli upper bound
                {  -1 ,-1.0 ,  NaN, NaN , 0.0 },  //rigo dei lower bound
                { 0.0 , 1.0 , 1.0 , 0.0 , 0.0 }}; //rigo per la definizione degli integer
               
        double b[]=     { 9.0, 12.5 ,24.0,   NaN,   NaN, NaN};  //vettore dei termini noti
     
        ConsType rel[]= { GE, EQ, LE, UPPER, LOWER, INT};  //vettore delle relazioni
 
        LinearObjectiveFunction fo = new LinearObjectiveFunction(c, GoalType.MIN);
        ListConstraints constraints  = new ListConstraints();
        for(int i=0; i < A.length; i++) constraints.add(new Constraint(A[i], rel[i], b[i]));
    }
}

 double c[]= { 3.0, 1.0, -4.0, 7.0, 8.0 };

rappresenta la funzione 3X₁+X₂-4X₃+7X₄+8X₅. Se una variabile assume coefficiente nullo sulla f.o., il valore 0 deve essere comunque riportato nel vettore c[]. La direzione dell'ottimizzazione (minimizzazione o massimizzazione) viene specificata tramite un parametro di tipo GoalType, come "GoalType.MAX" o "GoalType.MIN". Il GoalType va specificato, insieme al vettore c[], come argomento nel costruttore della classe LinearObjectiveFunction :

 LinearObjectiveFunction fo = new LinearObjectiveFunction(c, GoalType.MIN);

questo permette di creare un oggetto che rappresenta in modo completo la funzione obiettivo.

Vincoli: I vincoli del problema sono definiti utilizzando una matrice A[][], dove ogni sua riga (vettore riga) rappresenta un vincolo. Il vettore b[] contiene i termini noti associati ai vincoli, e l'array rel[] specifica il tipo di vincolo o relazione, ad esempio "GE" per i vincoli ≥ , "LE" per ≤ , "EQ" per =. Ogni vincolo viene creato utilizzando il costruttore "new Constraint(A[i], rel[i], b[i])". Se prendiamo l'esempio sopra riportato e se consideriamo i=0, ovvero selezioniamo i valori della matrice e dei vettori corrispondenti all'indice i=0 e li utilizziamo per definire il primo vincolo, otterremo per sostituzione l'equivalente istruzione :

new Constraint( new double[]{ 5.0 , 2.0 , 0.0 , 3.0 , 0.0 }, GE, 9);

Che rappresenta appunto il primo vincolo 5X₁+2X₂+3X₄ ≥ 9 del nostro problema.
Poichè gli oggetti della classe Constraint vengono di norma creati ed aggiunti alla lista dei vincoli ciclando sui righi della matrice A[][]:

for(int i=0; i < A.length; i++) constraints.add(new Constraint(A[i], rel[i], b[i]));

ed avendo nel nostro esempio inserito nella matrice A[][] anche dei righi per rappresentare altre limitazioni del problema (come gli Upper e i Lower Bound), è necessario che il vettore b[] dei termini noti abbia tanti elementi quanti sono i righi della matrice A[][]. Per rendere il vettore b[] della lunghezza corretta si inseriscono degli "NaN" (che nel formato a matrice significa valore indefinito) in corrispondenza di quelle relazioni che non hanno necessità di un valore rhs, che poi sono quelle che hanno per ConsType i valori "UPPER", "LOWER", "INT", "BIN", "SEMICONT". Lo sviluppatore, se vuole, può anche definire in A[][] solo ed esclusivamente i righi relativi ai vincoli reali (quelli ≤ , ≥, =) e inserire in array separati i vettori che rappresentano le restanti limitazioni, come nel codice riportato in questo esempio (Esempio 2.8 righi 34-35).

Volendo elencare la totalità dei valori che ogni elemento dell'array rel[] può assumere, abbiamo :

LE, GE, EQ, UPPER, LOWER, INT, BIN, SEMICONT

Ai vincoli del problema possono essere assegnate delle etichette o nomi. Questi nomi non devono essere necessariamente univoci per ciascun vincolo, in tal caso una singola etichetta può essere utilizzata per più vincoli per identificarli come appartenenti ad un gruppo specifico. Dare un nome o una etichetta ha il solo scopo di identificare un vincolo o un gruppo di vincoli; difatti in fase di recupero ed interpretazione dei risultati sarà possibile identificare ciascun vincolo a partire dalla sua etichetta insieme alle altre caratteristiche. Per definire una etichetta su un vincolo, basta aggiungere il nome del vincolo come ultimo argomento al costruttore della classe Constraint, come nell'esempio seguente :

new Constraint(A[i], rel[i], b[i],"Vincolo"+i);

In questo caso ciclando sull'indice i assegneremo i seguenti nomi: "Vincolo0", "Vincolo1", "Vincolo2", e così via. Naturalmente si possono dare nomi diversi non necessariamente numerati.

Variabili: Nel formato matriciale i nomi delle variabili del problema di programmazione lineare vengono assegnati in automatico dal sistema. La prima variabile avrà nome X1, la seconda X2, e cosi via.

Limiti delle variabili: I limiti superiori e inferiori delle variabili possono essere specificati utilizzando due righe separate nella matrice A[][], identificate dai valori di ConsType pari ad "UPPER" e "LOWER" nell'array rel[]. Ad esempio, per la variabile X₂ che presenta un limite inferiore -1 e un limite superiore 6, si possono inserire tali due righe nella matrice A[][] per specificare tali limiti. Se tali righi non vengono specificati, le variabili sono considerate non negative di default. Rocordiamo ancora che lo sviluppatore può definire limiti superiori e inferiori anche in array separati. Nell'esempio sopra riportato, i due vettori riga della matrice A[][] :

{ NaN , 6.0 ,  -2 , NaN , NaN },  //rigo degli upper bound
{  -1 ,-1.0 ,  NaN, NaN , 0.0 },  //rigo dei lower bound

stanno ad indicare :

1) che la variabile X₁ può assumere valori in [-1,NaN], ovvero [-1,+∞].
2) che la variabile X₂ può assumere valori in [-1,6] , ovvero una variabile che assume valori negativi maggiori di -1 o positivi minori di 6.
3) che la variabile X₃ può assumere valori in [NaN,-2], ovvero una variabile che assume solo valori negativi in [-∞,-2].
4) che la variabile X₄ può assumere valori in [NaN,NaN], ovvero [-∞,,+∞] o libera.
5) che la variabile X₅ può assumere valori in [0,NaN], ovvero [0,+∞].

Variabili libere o negative:Per poter dichiarare variabili libere, ovvero variabili senza limite inferiore (il limite inferiore non sarà più lo zero ma -infinito), basta specificare un lower bound indefinito. Se si dichiara un valore indefinito sulla riga dei lower bound o sulla riga degli upper bound, SSC trasforma tali valori in -infinito nel primo caso ed in +infinito nel secondo. Nel formato matriciale il valore indefinito si rappresenta con il "NaN". In generale per poter impostare delle variabili che possono assumere valori anche in un range negativo, basta valorizzare un lower bound indefinito (come sulla X₄) o negativo (come sulla X₁), oppure un upper bound negativo (come sulla X₃).

Variabili intere: Le variabili che devono assumere valori interi sono indicate tramite una riga nella matrice A[][] che ha associato un ConsType, presente nel vettore rel[] delle relazioni, pari a "INT". Questa riga deve contenere 1 per le variabili intere e 0 per le altre.

Variabili binarie: Le variabili che devono assumere valori binari sono indicate tramite una riga nella matrice A[][] che ha associato un ConsType, presente nel vettore rel[] delle relazioni, pari a "BIN". Questa riga deve contenere 1 per le variabili binarie e 0 per le altre.

Variabili semicontinue: È possibile risolvere problemi di programmazione lineare con variabili semicontinue. Ricordiamo che una variabile semicontinua può essere o pari a zero oppure deve appartenere a un intervallo continuo delimitato. Ad esempio, sia [l, u] un intervallo continuo e delimitato, allora una variabile x può essere definita semicontinua se l ≤ x ≤ u oppure se x = 0, naturalmente con 0 ∉ [l, u].
Le variabili che devono assumere valori semicontinui sono indicate tramite una riga nella matrice A[][] che ha associato un ConsType, presente nel vettore rel[], pari a "SEMICONT". Questa riga contiene 1 per le variabili che devono essere semicontinue e 0 per le altre. Se nella matrice A[][] si dichiarasse una riga con valore di ConsType pari a "SEMICONT" ed in tale riga ci fossero i valori:

{ 1.0 , 0.0 , 0.0 , 0.0 , 1.0 },

stiamo dichiarando che la prima e la quinta variabile sono semicontinue. Naturalmente se definiamo una variabile x semicontinua, questa deve anche essere dichiarata limitata tramite un vincolo del tipo l ≤ x ≤ u , e quindi occorre definire per la suddetta variabile anche i valori di upper e lower bound.

Esempi completi di modellazione di problemi che utilizzano il formato matriciale sono riportati nella sezione Esempi di questo sito, dimostrando come rappresentare sia problemi di LP standard (esempi 1.3 , 1.5 , 1.13), sia problemi di MILP (esempi 2.2, 2.5 , 2.8, 2.11, 2.13, 3.3). La libreria parserizza automaticamente le espressioni presenti nella stringa e le traduce in un modello matematico che può essere risolto utilizzando algoritmi come il simplesso o il branch and bound.

4.1.5 Formato sparso

Consideriamo la seguente formulazione matematica di un problema di Programmazione Lineare :

funzione obiettivo:
     min  3X₁ + X₂ - 4X₃ + 7X₄ + 8X₅
	 
vincoli:
     5X₁ +  2X₂      + 3X₄       ≥    9
     3X₁ +   X₂ +  X₃      + 5X₅  = 12.5
     6X₁ +3.1X₂ + 4X₃ + 5X₄       ≤   24
	 
limiti delle variabili:	  
           X₁ ≥ -1
      -1 ≤ X₂ ≤ +6
           X₃ ≤ -2
      -∞ ≤ X₄ ≤ +∞  
  
condizioni :   
         X₅ ≥ 0
         X₂, X₃ ∈ ℤ

Per rappresentare questo problema di Programmazione Lineare affinchè sia elaborabile dalla libreria SSC si può utilizzare il formato sparso. Questo formato è simile a quello fornito da SAS® (LP procedure) e fornisce un metodo flessibile per rappresentare problemi di programmazione lineare utilizzando una struttura dati che descrive le relazioni tra variabili, vincoli e la funzione obiettivo. Il codice Java che segue mostra un esempio di sintassi per rappresentare il problema sopra riportato utilizzando il formato sparso:

import org.ssclab.ref.InputString;
 
public class Esempio {
    public static void main(String[] args) throws Exception {
 
           String lp_sparse = 
         
            //   TYPE    COL_    ROW_       COEF 
                  
                " MIN     .    fo_costo       .    \n" +   
                " GE      .    vincolo1       .    \n" +  
                " EQ      .    compenso       .    \n" +
                " LE      .    autonomia      .    \n" +
                " UPPER   .    lim_superiore  .    \n" +
                " LOWER   .    lim_inferiore  .    \n" +     
                " INTEGER .    var_intere     .    \n" +  
         
                " .      X1    fo_costo       3    \n" +
                " .      X1    vincolo1       5    \n" +      
                " .      X1    compenso       3    \n" +  
                " .      X1    autonomia      6    \n" +
                " .      X1    lim_inferiore -1    \n" +               
                  
                " .      X2    fo_costo       1    \n" +
                " .      X2    vincolo1       2    \n" +      
                " .      X2    compenso       1    \n" +  
                " .      X2    autonomia    3.1    \n" +
                " .      X2    lim_superiore  6    \n" +     
                " .      X2    lim_inferiore -1    \n" +     
                " .      X2    var_intere     1    \n" +     
                
                " .      X3    fo_costo      -4    \n" +
                " .      X3    compenso       1    \n" +  
                " .      X3    autonomia      4    \n" +
                " .      X3    lim_superiore -2    \n" +     
                " .      X3    var_intere     1    \n" +      
			    
                " .      X4    fo_costo       7    \n" +
                " .      X4    vincolo1       3    \n" +      
                " .      X4    autonomia      5    \n" +
                " .      X4    lim_superiore  .    \n" +     
                " .      X4    lim_inferiore  .    \n" +     

                " .      X5    fo_costo       8    \n" +
                " .      X5    compenso       5    \n" +  
                                
                " .      RHS   vincolo1       9    \n" +      
                " .      RHS   compenso    12.5    \n" +  
                " .      RHS   autonomia     24    \n" ;
             
        InputString lp_input = new InputString(lp_sparse); 
        lp_input.setInputFormat("TYPE:varstring(10), COL_:varstring(3) , ROW_:varstring(14), COEF:double"); 
    }
}

InputString lp_input = new InputString(lp_sparse); 
lp_input.setInputFormat("TYPE:varstring(10), COL_:varstring(3) , ROW_:varstring(14), COEF:double");

La stringa che contiene la formulazione del problema (lp_sparse) viene passata al costruttore della classe InputString per creare una istanza di questa classe; su tale istanza è possibile invocare il metodo setInputFormat(). Ebbene, la definizione del formato di input si effettua attraverso una stringa da passare come argomento al metodo setInputFormat(); in questa stringa si susseguono, separate da virgola, le notazioni "nome variabile:tipologia variabile" per definire, in sequenza, i nomi delle variabili da associare alla colonne ed il tipo di dato presente nelle colonne.

Sebbene si parli di 'colonne', ciò serve solo a semplificare la comprensione: il primo dato di ogni riga viene associato alla prima variabile dichiarata, il secondo dato alla seconda variabile dichiarata, e così via. Non è necessario che i valori siano allineati rigorosamente in verticale (ovvero che si trovino tutti sul k-esimo carattere di ciascun rigo); l'importante è che siano separati da almeno uno spazio e che seguano la sequenza corretta. E' da menzionare che in questo formato, il carattere punto (".") rappresenta il valore indefinito o mancante (analogo ad un null).

Essendo un formato rigidamente costituito da 4 colonne, indipendentemente dal numero di variabili decisionali e vincoli presenti nel problema, questo formato può essere utilizzato anche per importare problemi di programmazione lineare da una tabella di un database (vedi esempio 1.9). Un secondo vantaggio del formato sparso è che consente di specificare solo i coefficienti diversi da zero nella descrizione del problema di programmazione lineare. Vediamo in dettaglio le diverse parti costituenti questo formato:

1) TYPE : I valori che la colonna TYPE può assumere sono i seguenti :

MAX  MIN  EQ  LE  GE  UPPER  LOWER  INTEGER  BINARY  SEMICONT

Questi valori possono essere scritti sia in maiuscolo che in minuscolo; in entrambi i casi verranno convertiti in maiuscolo.

Quando il motore di elaborazione analizza una riga con TYPE valorizzato (diverso da "."), inizia a definire una nuova entità ed assegna ad essa un marcatore, quello indicato nella colonna dei ROW_. Piu specificatamente, se il motore rileva che il TYPE assume il valore "MAX" o "MIN", inizia la definizione della funzione obiettivo; se invece il valore di TYPE è uno dei valori "EQ" (=) , "LE" (≤) o "GE" (≥), inizia la definizione di un vincolo. Consideriamo il primo rigo dell'esempio sopra riportato:

MIN     .    fo_costo       .

Durante il processamento di questo rigo, nel quale sono solo le variabili TYPE e ROW_ ad essere valorizzate, il motore di elaborazione inizia a creare la definizione della funzione obiettivo associandogli come marcatore il valore "fo_costo" e come direzione dell'ottimizazione la minimizzazione. Come possiamo notare nella riga sono presenti dei punti (".") che rappresentano un valore indefinito. Ciò è dovuto al fatto che nel formato sparso ogni variabile dichiarata deve avere, su ogni rigo, associato un valore; in questo caso inseriamo un valore indefinito, da associare alla relative colonne, in quanto irrilevanti nella creazione della funzione obiettivo. Consideriamo il secondo rigo:

GE      .    vincolo1       .

Quando questo rigo viene interpretato si inizia a creare la definizione di un vincolo di disuguaglianza (≥) al quale viene assegnato il marcatore "vincolo1".
Questo meccanismo permette di definire tutte le caratteristiche del problema. Difatti, proseguendo nell'esposizione, se la variabile TYPE assume il valore "UPPER" o "LOWER", stiamo definendo i marcatori che permettono di impostare i limiti superiori e inferiori delle variabili. Infine, se la variabile TYPE assume uno dei valori "INTEGER", "BINARY", o "SEMICONT", stiamo definendo i marcatori necessari per indicare quali variabili sono intere, binarie o semicontinue.

2) ROW_ : Ogni riga con TYPE valorizzato ha associato un marcatore (specificato nella colonna ROW_) che identifica in modo univoco il nome di una entità. I nomi di questi marcatori sono scelti liberamente dallo sviluppatore, ma è importante notare che essi sono case-sensitive.
Se una riga contiene un valore in ROW_ ma ha TYPE indefinito (".") non si sta definendo una nuova entità ma si sta specificando il coefficiente che una variabile assume su quella entità. In questo caso il valore COEF indica il coefficiente che la variabile, specificata in COL_, assume per l'entità corrispondente al marcatore presente in ROW_. Consideriamo il rigo presente nel nostro esempio :

.      X1    fo_costo       3

Questo rigo dichiara che la variabile X₁ assume il coefficiente 3 sulla funzione obiettivo. Consideriamo un altro rigo presente nel nostro esempio :

.      X1    vincolo1       5

Questo rigo dichiara che la variabile X₁ assume il coefficiente 5 sul vincolo identificato dal marcatore "vincolo1".

3) COL_ : I valori COL_ identificano i nomi delle colonne (ovvero delle variabili). Per rappresentare la colonna dei valori rhs (termini noti) si utilizza la parola riservata "RHS", che quindi non deve essere utilizzata per identificare altro.

4) COEFF : I valori COEFF risultano o i coefficienti che le variabili assumono sulle diverse entità (vincolo o f.o.) o i valori dei termini noti se il valore della colonna COL_ è uguale a "RHS".

Occorre ribadire che i valori della colonna TYPE e COL_ possono essere espressi sia in maiuscolo che in minuscolo; in entrambi i casi essi verranno ricondotti al maiuscolo; mentre per la colonna ROW_ esprimere il marcatore di una stessa entità in minuscolo e in maiuscolo, nell'ambito di una stessa formulazione, significa dichiarare due marcatori (e quindi due entità) distinti. In funzione di quanto detto vediamo come definire le diverse componenti che costituiscono un problema di LP:

Funzione obiettivo : Per definire con il formato sparso la funzione obiettivo 3X₁+X₂-4X₃+7X₄+8X₅ da minimizzare presente nel nostro esempio iniziale, occorrono i seguenti record :

MIN     .    fo_costo       .
.      X1    fo_costo       3
.      X2    fo_costo       1 
.      X3    fo_costo      -4
.      X4    fo_costo       7  
.      X5    fo_costo       8

Il primo record, attraverso il valore del TYPE pari a "MIN", informa che si sta definendo una f.o. da minimizzare e che il marcatore utilizzato per identificarla è "fo_costo"; con i successivi record si dichiarano i coefficienti che ogni variabile ha su quel marcatore, che rappresenta appunto la f.o..

Vincoli : Per definire il vincolo 5X₁+ 2X₂+3X₄≥ 9 occorre definire i seguenti record :

GE      .    vincolo1       . 
.      X1    vincolo1       5 
.      X2    vincolo1       2   
.      X4    vincolo1       3  
.      RHS   vincolo1       9

Nome dei vincoli: Nel momento in cui si definisce un marcatore per un vincolo, questo risulta essere anche il suo nome; questo permette di identificare un vincolo in fase di recupero ed interpretazione dei risultati insieme alle altre caratteristiche. Non vi sono restrizioni particolari sui nomi dei vincoli, devono però essere una singola parola senza contenere spazi. Naturamente se si defiscono nomi particolamernte lunghi occorre che nel formato di input la variabile ROW_ sia definita con una lunghezza adeguata, maggiore di quella dichiarata per questo esempio che è di 14 caratteri (ROW_:varstring(14)).

Nomi delle variabili: Non vi sono restrizioni particolari sui nomi delle variabili, devono pero essere una singola parola senza spazi. Naturamente se si defiscono nomi particolamernte lunghi occorre che nel formato di input la variabile COL_ sia definita con una lunghezza adeguata, maggiore di quella dichiarata per questo esempio che è di 3 caratteri (COL_:varstring(3)).

Limiti delle variabili : Per definire gli upper bound e i lower bound, occorre preliminarmante definire i marcatori con TYPE valorizzato a "UPPER" e "LOWER". Questi consentono di definire i limiti sulle variabili. Ad esempio, per impostare il limite sulla variabile X₁, limitata in X₁ ≥ -1, occorre che siano presenti i seguenti record :

LOWER   .    lim_inferiore  .    
.      X1    lim_inferiore -1

Il primo record, attraverso il valore del TYPE pari a "UPPER", informa che si sta definendo il marcatore dei lower bound "lim_inferiore"; con il successivo record si dichiara il lower bound per la variabile X₁ .

Variabili libere o negative: Per poter dichiarare variabili libere, ovvero variabili senza limite inferiore (il limite inferiore non sarà più lo zero ma -infinito), basta specificare un lower bound indefinito. Se si dichiara un valore indefinito di lower bound o di upper bound per una variabile, SSC trasforma tali valori in -infinito nel primo caso ed in +infinito nel secondo. Nel formato sparso il valore indefinito si rappresenta con il punto ("."). In generale per poter impostare delle variabili che possono assumere valori anche in un range negativo, basta valorizzare un lower bound indefinito (come sulla X₄) o negativo (come sulla X₁), oppure un upper bound negativo (come sulla X₃).

Variabili intere: Le variabili che devono assumere valori interi sono indicate tramite il marcatore definito dallo sviluppatore "var_intere" che ha associato un TYPE pari a "INTEGER". La variabile intera si indica poi ponendo un 1 sulla colonna dei COEF come di seguito:

INTEGER .    var_intere     .  
.      X2    var_intere     1

Variabili binarie: Le variabili che devono assumere valori binari sono indicate tramite un marcatore definito dallo sviluppatore che ha associato un TYPE pari a "BINARY". La variabile intera si indica poi ponendo un 1 sulla colonna dei COEF.

Variabili semicontinue: È possibile risolvere problemi di programmazione lineare con variabili semicontinue. Ricordiamo che una variabile semicontinua può essere o pari a zero oppure deve appartenere a un intervallo continuo delimitato. Ad esempio, sia [l, u] un intervallo continuo e delimitato, allora una variabile x può essere definita semicontinua se l ≤ x ≤ u oppure se x = 0, naturalmente con 0 ∉ [l, u].
Le variabili che devono assumere valori semicontinui sono indicate tramite un marcatore definito dallo sviluppatore che ha associato un TYPE pari a "SEMICONT". La variabile semicontinua si indica poi ponendo un 1 sulla colonna dei COEF.

Esempi completi di modellazione di problemi che utilizzano il formato sparso sono riportati nella sezione Esempi di questo sito, dimostrando come rappresentare sia problemi di LP standard (esempi 1.7 , 1.9 , 1.12) , sia problemi di MILP (esempi 2.3 , 2.6 , 2.12 , 3.4). La libreria parserizza automaticamente le espressioni presenti nella stringa e le traduce in un modello matematico che può essere risolto utilizzando algoritmi come il simplesso o il branch and bound.

4.1.6 Formulazione del Problema in un file esterno

La libreria SSC supporta la possibilità di definire un problema di programmazione lineare in un file esterno utilizzando quattro dei cinque formati disponibili: formato testo, formato JSON, formato a coefficienti e formato sparso. I dati del problema sono memorizzati in un file esterno e interpretati dalla libreria, garantendo flessibilità e facilità d'uso. Di seguito, vediamo come gestire ciascun formato.
Formato Testo: Nel formato testo, il problema è descritto in forma verbale all'interno di un file di testo esterno che viene referenziato utilizzando la classe Paths e poi interpretato dalla classe LP o MILP (vedere esempio 1.11).
Formato JSON: Nel formato JSON, il problema è descritto in un oggetto JSON all'interno di un file esterno che viene referenziato utilizzando la classe Paths e poi interpretato dalla classe JsonProblem (vedere esempio 1.17).
Formato a Coefficienti: Nel formato a coefficienti, il problema è descritto in un file di testo esterno con una strutura dati contenente i valori dei coefficienti delle variabili, i tipi di vincoli e i termini noti. Il file viene referenziato utilizzando la classe InputFile (vedere esempio 1.8).
Formato Sparso: Nel formato sparso, il problema è descritto in un file di testo esterno contenente una tabella con i valori delle quattro colonne necessarie a definire il problema: TYPE, COL_, ROW_, e COEF . Il file viene referenziato utilizzando la classe InputFile (vedere esempio 1.12).

4.1.7 Formulazione del Problema in database esterno

La libreria SSC supporta la possibilità di definire un problema di programmazione lineare in un database esterno (RDBMS) utilizzando il formato sparso. Viene utilizzato il formato sparso in quanto è l'unico formato rigidamente costituito da 4 colonne, di conseguenza è indipendentemente dal numero di variabili decisionali e vincoli presenti nel problema. Questo si sposa con la necessità di una tabella di database di essere costituita da un numero prefissato di campi. Per poter effettuare questa operazione occorre quindi che il database abbia quattro campi (colonne) nei quali memorizzare le informazioni contenute nei campi TYPE, ROW_, COL_ e COEF del formato sparso.
Per poter recuperare la formulazione del problema da una tabella presente in un database, occorre scaricare il driver JDBC per il database in questione e istanziare un oggetto Connection. Una volta ottenuta una connessione al DB, tramite l'oggetto Connection è possibile, da SSC, accedere al DB attraverso il concetto di libreria. Gli oggetti di tipo Library rappresentano una interfaccia al database; da questa interfaccia possiamo ottenere, tramite una query SQL, un oggetto di tipo Input che fa riferimento ai record relativi al problema inserito nella tabella (vedere esempio 1.9).

4.2 Risoluzione del problema

4.2.1 Esecuzione dell'ottimizzazione

Per risolvere un problema di Programmazione Lineare (LP) o di Programmazione Lineare Mista Intera (MILP), è innanzitutto necessario definire il problema utilizzando il formato desiderato, come descritto nei paragrafi precedenti. A seconda del formato scelto, la formulazione del problema viene memorizzata in oggetti di classi specifiche o che implementano interfacce specifiche (come l'interfaccia Input). Di seguito, i diversi formati e le relative classi da utilizzare:

Formato testo : String.
Formato JSON : JsonProblem.
Formato a coefficienti : Input, InputString, InputFile.
Formato matriciale : LinearObjectiveFunction e ListConstraints.
Formato sparso : Input, InputString, InputFile.

Questi oggetti consentono di memorizzare il problema nel formato scelto; l'interprete presente in SSC converte queste diverse formulazioni in una struttura uniforme, rendendola comprensibile al motore di risoluzione della libreria. La conversione in una struttura unificata avviene attraverso la creazione di un oggetto della classe LP (per problemi senza variabili intere) o della classe MILP (per problemi misti interi), passando al costruttore l'oggetto contenente il problema. Una volta creato l'oggetto LP o MILP, su entrambe le istanze è possibile invocare il metodo resolve() per avviare il processo di risoluzione. Questo metodo restituisce un valore appartenente alla classe SolutionType, che indica se è stata trovata una soluzione ottimale o no. Ecco un esempio completo di risoluzione di un problema di programmazione lineare utilizzando il formato testo e la classe LP :

import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
 
public class Esempio {
    public static void main(String[] args) throws Exception {
         
        String  pl_string = 
		
        "min:  3Y  +2x2 +4x3 +7x4 +8X5             \n"+ 
        "      5Y  +2x2      +3X4          >=   9  \n"+
        "      3Y  + X2 + X3      +5X5      =  12  \n" +
        "      6Y+3.0x2 +4X3 +5X4          <=  24  \n";
         
        LP lp = new LP(pl_string); 
        SolutionType solution_type=lp.resolve();
         
        if(solution_type==SolutionType.OPTIMUM) {
            Solution soluzione=lp.getSolution();
            for(Variable var:soluzione.getVariables()) {
                SscLogger.log("Nome variabile :"+var.getName() + " valore :"+var.getValue());
            }
            SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
        }
        else SscLogger.log("Soluzione non ottima:"+solution_type);      
    }
}

Se nell'esempio fosse stata dichiarata qualche variabile intera, occorre semplicemente sostituire la classe LP con la classe MILP.

A seconda del formato prescelto occorre utilizzare l'appropriato costruttore per creare un oggetto di una delle due classi. Vediamo quali sono i costruttori disponibili per la classe LP elencati nella seguente tabella in base ai parametri passati come argomento:

Costruttore classe `LP`	Descrizione	Formato da utilizzare	Esempio
`LP(String text)`	Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in una stringa. `String text` : è la stringa contenente la formulazione del problema in formato testo.	TESTO	1.1
`LP(ArrayList<String> text)`	Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in un ArrayList. `ArrayList<String> text` : è un ArrayList contenente una lista ordinata di stringhe, ognuna delle quali memorizza una riga del problema formulato con il formato testo.	TESTO	1.15
`LP(Path path)`	Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in un file esterno. `Path path` : l'oggetto Path deve riferirsi al percorso in cui si trova il file contenente il problema di LP formulato con il formato testo.	TESTO	1.11
`LP(JsonProblem jsonProb)`	Costruttore da utilizzare con la formulazione del problema in formato JSON memorizzato in una stringa o in un file. `JsonProblem jsonProb` : è l'oggetto contenente la formulazione del problema in formato JSON.	JSON	1.17
`LP(LinearObjectiveFunction fo,ArrayList<Constraint> constraints)`	Costruttore da utilizzare con la formulazione del problema in formato matriciale `A[][],b[],c[]`. `LinearObjectiveFunction fo` : è l'ogggetto contenente la formulazione della funzione obiettivo. `ArrayList<Constraint> constraints` : è la lista contenente i singoli vincoli di tipo Constraint.	MATRICIALE	1.13
`LP(LinearObjectiveFunction fo,ListConstraints constraints)`	Costruttore da utilizzare con la formulazione del problema in formato matriciale `A[][],b[],c[]`. `LinearObjectiveFunction fo` : è l'ogggetto contenente la formulazione della funzione obiettivo. `ListConstraints constraints` : è la lista contenente i singoli vincoli di tipo Constraint.	MATRICIALE	1.3
`LP(Input input)`	Costruttore da utilizzare con la formulazione del problema in formato a coefficienti. `Input input` : l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti, deve implementare questa interfaccia.	COEFFICIENTI	1.2
`LP(Input input,Session session)`	Costruttore da utilizzare con la formulazione del problema in formato a coefficienti. `Input input` : l'ogggetto che memorizza la formulazione del problema avente formato a coefficienti deve implementare questa interfaccia. `Session session` : è la sessione di lavoro SSC se ne è stata già istanziata una.	COEFFICIENTI	-
`LP(Input input,FormatType format)`	Costruttore da utilizzare con la formulazione del problema in formato a coefficienti o sparso. `Input input` : l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti o sparso, deve implementare questa interfaccia. `FormatType format` : è il tipo di formato utilizzato nella definizione del problema; si può indicare `FormatType.SPARSE o FormatType.COEFF`.	SPARSO O COEFFICIENTI	1.7
`LP(Input input,Session session, FormatType format)`	Costruttore da utilizzare con la formulazione del problema in formato a coefficienti o sparso. `Input input` :l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti o sparso, deve implementare questa interfaccia. `Session session` : è la sessione di lavoro SSC se ne è stata già istanziata una. `FormatType format` : è il tipo di formato utilizzato nella definizione del problema; si può indicare `FormatType.SPARSE o FormatType.COEFF`.	SPARSO O COEFFICIENTI	1.9

Vediamo ora i costruttori disponibili per la classe MILP (Programmazione Lineare Mista Intera) elencati nella seguente tabella in base ai parametri passati come argomento:

Costruttore classe `MILP`	Descrizione	Formato da utilizzare	Esempio
`MILP(String text)`	Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in una stringa. `String text` : è la stringa contenente la formulazione del problema in formato testo.	TESTO	2.7
`MILP(ArrayList<String> text)`	Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in un ArrayList. `ArrayList<String> text` : è un ArrayList contenente una lista ordinata di Stringhe, ognuna delle quali memorizza una riga del problema formulato con il formato testo.	TESTO	-
`MILP(Path path)`	Costruttore da utilizzare con la formulazione del problema in formato testo memorizzato in un file esterno. `Path path` : l'oggetto Path deve riferirsi al percorso in cui si trova il file contenente il problema di LP formulato con il formato testo.	TESTO	-
`MILP(JsonProblem jsonProb)`	Costruttore da utilizzare con la formulazione del problema in formato JSON memorizzato in una stringa o in un file. `JsonProblem jsonProb` : è l'oggetto contenente la formulazione del problema in formato JSON.	TESTO	2.15
`MILP(LinearObjectiveFunction fo,ArrayList<Constraint> constraints)`	Costruttore da utilizzare con la formulazione del problema in formato matriciale `A[][],b[],c[]`. `LinearObjectiveFunction fo` : è l'ogggetto contenente la formulazione della funzione obiettivo. `ArrayList<Constraint> constraints` : è la lista contenente i singoli vincoli di tipo Constraint.	MATRICIALE	2.2
`MILP(LinearObjectiveFunction fo,ListConstraints constraints)`	Costruttore da utilizzare con la formulazione del problema in formato matriciale `A[][],b[],c[]`. `LinearObjectiveFunction fo` : è l'ogggetto contenente la formulazione della funzione obiettivo. `ListConstraints constraints` : è la lista contenente i singoli vincoli di tipo Constraint.	MATRICIALE	2.5
`MILP(Input input)`	Costruttore da utilizzare con la formulazione del problema in formato a coefficienti. `Input input` : l'ogggetto che memorizza la formulazione del problema, avente formato a coefficienti, deve implementare questa interfaccia.	COEFFICIENTI	2.1
`MILP(Input input,Session session)`	Costruttore da utilizzare con la formulazione del problema in formato a coefficienti. `Input input` : l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti, deve implementare questa interfaccia. `Session session` : è la sessione di lavoro SSC se ne è stata già istanziata una.	COEFFICIENTI	-
`MILP(Input input,FormatType format)`	Costruttore da utilizzare con la formulazione del problema in formato a coefficienti o sparso. `Input input` : l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti o sparso, deve implementare questa interfaccia `FormatType format` : è il tipo di formato utilizzato nella definizione del problema; si può indicare `FormatType.SPARSE o FormatType.COEFF`.	SPARSO O COEFFICIENTI	2.3
`MILP(Input input,Session session, FormatType format)`	Costruttore da utilizzare con la formulazione del problema in formato a coefficienti o sparso. `Input input` : l'oggetto che memorizza la formulazione del problema, avente formato a coefficienti o sparso, deve implementare questa interfaccia. `Session session` : è la sessione di lavoro SSC se ne è stata già istanziata una. `FormatType format` : è il tipo di formato utilizzato nella definizione del problema; si può indicare `FormatType.SPARSE o FormatType.COEFF`.	SPARSO O COEFFICIENTI	-

4.2.2 Configurazione e Opzioni di Esecuzione

Come detto, sull'oggetto appartenente alla classe LP o MILP, si può invocare il metodo resolve() per avviare il processo di risoluzione. Prima di eseguire il run dell'ottimizzazione, la libreria offre diverse opzioni di configurazione per adattare la risoluzione del problema alle esigenze specifiche dell'utente. Queste opzioni consentono di controllare la tolleranza, l'utilizzo del multithreading, la possibilità di ottenere una soluzione fattibile, etc, offrendo un ulteriore controllo sull'algoritmo di risoluzione.

Esecuzione parallela con multithreading
Per migliorare le prestazioni, la libreria consente l'uso del simplesso parallelo, specificando il numero di thread con il metodo setThreadsNumber() della classe LP (vedi esempio 1.14). Per esempio:

LP lp = new LP(lp_input);
lp.setThreadsNumber(LPThreadsNumber.N_4);

In questo caso stiamo specificano 4 thread per l'esecuzione. È possibile utilizzare anche il parametro LPThreadsNumber.AUTO per delegare al sistema la scelta del numero di thread. L'uso del multithreading è consigliato principalmente per problemi con migliaia di variabili o vincoli e su macchine con almeno 4 core fisici.

Numero massimo di iterazioni
La libreria permette di limitare il numero massimo di iterazioni tramite setNumMaxIteration() della classe LP (vedi esempio 1.10) , il cui valore di default è 100.000.000:

LP lp = new LP(lp_input);
lp.setNumMaxIteration(500);

In questo modo limitiamo il numero di iterazioni a 500.

Determinazione di una soluzione ammissibile
È possibile configurare l'algoritmo per restituire una soluzione ammissibile, anche se non ottima, utilizzando il metodo setJustTakeFeasibleSolution(true) della classe LP (vedi esempio 1.10). Questo approccio, adatto in situazioni in cui si cerca una soluzione ammissibile rapida, esegue solo la prima fase del simplesso:

LP lp = new LP(lp_input);
lp.setJustTakeFeasibleSolution(true);

Se esiste una soluzione ammissibile, il metodo resolve() restituirà SolutionType.FEASIBLE, permettendo di ottenere una soluzione basica senza procedere alla ricerca dell'ottimo.

Modifica della tolleranza
Una delle opzioni riguarda la tolleranza utilizzata per determinare la convergenza della 'fase uno' dell'algoritmo del simplesso. Questa opzione può essere configurata utilizzando il metodo setCEpsilon() della classe LP (vedi esempio 1.13). Per esempio:

LP lp = new LP(fo,constraints);
lp.setCEpsilon(EPSILON._1E_M5);

La tolleranza di default è impostata su 1E-8. Tuttavia, in presenza di numeri molto grandi, potrebbe essere necessario aumentarla a un valore maggiore per garantire che il valore ottimo della funzione obiettivo, nella fase uno del simplesso, soddisfi la condizione di ottimalità. Ricordiamo che condizione necessaria affinchè il problema ammetta una soluzione ammissibile è che il valore ottimo della fase uno del simplesso sia uguale a zero. Ciò potrebbe non avvenire a causa della manipolazione di numeri di grandezza molto elevata. In questo particolare caso se non si modifica la tolleranza ε del valore ottimo z della f.o relativo alla fase uno la risoluzione del problema potrebbe non dare come risultato soluzioni ammissibili. In altre parole, se alla fine della fase uno |z| > ε , allora il problema non ammette soluzioni. Per ovviare a questo, nelle righe sopra riportate, la tolleranza viene aumentata da 1E-8 (valore di default) a 1E-5. per far si che possa avvenire che |z| < ε. Senza questa modifica, il problema potrebbe risultare privo di soluzioni ammissibili, nonostante esistano. Naturalmente i valori di tolleranza usabili sono diversi : 1E-4, 1E-5, 1E-6, etc

Elenchiamo nella tabella che segue i metodi della classe LP e MILP da utilizzare per impostare le varie opzioni di configurazione:

Metodo	Descrizione	Classe	Esempio
`setEpsilon(EPSILON epsilon)`	Questo metodo consente di impostare il valore epsilon relativo alla tolleranza che interviene in vari contesti. Viene utilizzato nei seguenti casi: 1) Durante la fase uno, sia nella determinazione della variabile in entrata che in quella in uscita con o senza la regola Bland. 2) Viene utilizzato per determinare se la base è degenere. 3) Viene utilizzato alla fine della fase uno: se nella base è presente una variabile ausiliaria, epsilon viene utilizzato per determinare se è possibile eliminare le righe e le colonne di queste sulla tabella estesa. 4) Durante la fase due, sia nella determinazione della variabile in entrata che in quella in uscita con o senza la regola Bland. `EPSILON epsilon` : è l'unumerazione con i diversi valori di tolleranza impostabili : _1E_M12 , _1E_M11 , _1E_M10 , _1E_M9 , _1E_M8 , etc.	LP	-
`setCEpsilon(EPSILON epsilon)`	Questo metodo consente di impostare il valore epsilon (`ε`) relativo alla tolleranza permessa sulla soluzione finale della fase 1. Ovvero, se il valore `z` della soluzione ottimale espressa dalla fase 1 è prossima allo zero, ovvero se `\|z\| < ε`, allora il problema ammettte soluzioni ammissibili. `EPSILON epsilon` : è l'unumerazione con i diversi valori di tolleranza impostabili : _1E_M12 , _1E_M11 , _1E_M10 , _1E_M9 , _1E_M8 , etc.	LP	1.13
`setNumMaxIteration(int num_max_iteration)`	Questo metodo consente di limitare il numero massimo di iterazioni del simplesso (iterazioni fase 1 + iterazioni fase 2). `int num_max_iteration` : è un intero che esprime il numero massimo di iterazioni.	LP	1.10
`setParallelSimplex(boolean isParallelSimplex)`	Permette di attivare il multithreading. Le prestazioni del simplesso possono essere migliorate eseguendo i processi di ottimizzazione in parallelo su più thread. Il numero di thread è impostato su AUTO, il sistema decide il numero di thread da utilizzare. `boolean isParallelSimplex` : un booleano che se true attiva il multithreading.	LP	-
`setThreadsNumber(LPThreadsNumber threadsNumber)`	Permette di attivare il multithreading e imposta trasmite il parametro passato il numero di thread da utilizzare nell'esecuzione. Se il valore passato è AUTO, il sistema decide in autonomia numero di thread da utilizzare. `LPThreadsNumber threadsNumber` : una enumerazione che specifica il numero di thread da utilizzare, ammette i valori : AUTO, N_1, N_2 , N_4 , N_6 , N_8 , etc.	LP	1.14
`setJustTakeFeasibleSolution(boolean isStopPhase2)`	Impostandolo su true è possibile interrompere il simplesso alla fine della fase 1, per determinare non una soluzione ottimale ma solo una soluzione fattibile del problema. `boolean isStopPhase2` un booleano che se true interrompere il simplesso alla fine della fase 1.	LP	1.10
`setEpsilon(EPSILON epsilon)`	Questo metodo consente di impostare il valore epsilon relativo alla tolleranza che interviene in vari contesti. Viene utilizzato nei seguenti casi: 1) Durante la fase uno, sia nella determinazione della variabile in entrata che in quella in uscita con o senza la regola Bland. 2) Viene utilizzato per determinare se la base è degenere. 3) Viene utilizzato alla fine della fase uno: se nella base è presente una variabile ausiliaria, epsilon viene utilizzato per determinare se è possibile eliminare le righe e le colonne di queste sulla tabella estesa. 4) Durante la fase due, sia nella determinazione della variabile in entrata che in quella in uscita con o senza la regola Bland. `EPSILON epsilon` : è l'unumerazione con i diversi valori di tolleranza impostabili : _1E_M12 , _1E_M11 , _1E_M10 , _1E_M9 , _1E_M8 , etc.	MILP	-
`setCEpsilon(EPSILON cepsilon)`	Questo metodo consente di impostare il valore epsilon (`ε`) relativo alla tolleranza permessa sulla soluzione finale della fase 1 dei simplessi. Ovvero, se il valore `z` della soluzione ottimale espressa dalla fase 1 è prossima allo zero, ovvero se `\|z\| < ε`, allora il simplesso ammettte soluzioni ammissibili. `EPSILON epsilon` : è l'unumerazione con i diversi valori di tolleranza impostabili : _1E_M12 , _1E_M11 , _1E_M10 , _1E_M9 , _1E_M8 , etc.	MILP	-
`setIEpsilon(EPSILON iepsilon)`	Questo metodo consente di impostare il valore epsilon relativo alla tolleranza per determinare se un numero debba essere considerato intero o meno. Questo controllo avviene quando alla fine del simplesso la soluzione trovata viene valutata per soddisfare la condizione intera sulle variabili che devono essere intere. Sia x un numero e Int(x) l'intero più vicino a x, se \| Int(x) - x \| < ε , allora x ∈ Z `EPSILON epsilon` : è l'unumerazione con i diversi valori di tolleranza impostabili : _1E_M12 , _1E_M11 , _1E_M10 , _1E_M9 , _1E_M8 , etc.	MILP	-
`setThreadsNumber(MILPThreadsNumber lpThreadsNumber)`	Questo metodo consente di impostare il numero di thread da utilizzare per l'esecuzione di Branch and Bound. `MILPThreadsNumber lpThreadsNumber` : una enumerazione che specifica il numero di thread da utilizzare, ammette i valori : N_1, N_2 , N_4 , N_6 , N_8 , N_16 etc.	MILP	2.13
`setJustTakeFeasibleSolution(boolean isJustTakeFeasibleSolution)`	Impostandolo su true è possibile interrompere il Branch and Bound per determinare non una soluzione ottimale ma solo una soluzione fattibile al problema. `boolean isJustTakeFeasibleSolution` un booleano interrompe il B&B appena trovata una soluzione ammissibile.	MILP	2.14
`setNumMaxSimplexs(int num_max_simplex)`	Essendo il B&B una successione di esecuzioni di simplessi, imposta il numero massimo di simplessi eseguibili. Defalt 1.000.000 `int num_max_simplex` : è un intero che esprime il numero massimo di simplessi.	MILP	-
`setNumMaxIterationForSingleSimplex(int num_max_iteration)`	Questo metodo consente di limitare il numero massimo di iterazioni del singolo simplesso (iterazioni fase 1 + iterazioni fase 2). Defalt 10.000.000. `int num_max_iteration` : è un intero che esprime il numero massimo di iterazioni per simplesso.	MILP	-

4.3 Recupero e interpretazione dei risultati

Abbiamo visto nei precedenti paragrafi che per eseguire l'ottimizzazione di una formulazione di un problema di LP occorre istanzire un oggetto della classe LP (o MILP se ci sono delle variabili intere) ed invocare il metodo resolve(), come indicato nelle seguenti istruzioni :

LP lp = new LP(pl_string); 
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMUM) { 
...
...

Possiamo notare come il metodo resolve() restituisca un oggetto di tipo SolutionType che puo assumere i seguenti valori (vedi esempio 1.10) :

 OPTIMUM  FEASIBLE  ILLIMITATUM  VUOTUM  MAX_ITERATIUM  MAX_NUM_SIMPLEX

Analizziamo nel dettaglio ognuno di questi valori:

OPTIMUM : Se l'istanza della classe LP (o MILP) riesce ad convergere verso la soluzione ottima, viene restituito questo valore; è possibile quindi recuperale i valori ottimi della variabili decisionali e della funzione obiettivo insieme a molte altre informazioni inerenti la risoluzione del problema.
FEASIBLE : Se sull'istanza della classe LP (o MILP) viene richiamato il metodo setJustTakeFeasibleSolution(true) il motore di risoluzione non cerca la soluzione ottima, ma determina la prima soluzione ammissibile determinata. Se l'istanza della classe LP (o MILP) riesce ad convergere verso la soluzione ammissibile, viene restituito questo valore; è possibile quindi recuperale i valori della variabili decisionali e della funzione obiettivo relativi a tale soluzione ammissibile insieme a molte altre informazioni inerenti la risoluzione del problema.
ILLIMITATUM : Il problema non ammette soluzione ottima, ma solo un ottimo illimitato.
VUOTUM : Il problema non ammette soluzioni.
MAX_ITERATIUM : L'istanza della classe LP ha raggiunto il numero massimo di iterazioni.
MAX_NUM_SIMPLEX : L'istanza della classe MILP ha raggiunto il numero massimo di Simplessi eseguibili.

4.3.1 Interfaccia Solution

Dopo aver eseguito il metodo resolve() ed ottenuto una soluzione ottimale o ammissibile, puoi accedere ai dettagli della soluzione individuata. Per farlo, è necessario richiamare il metodo getSolution() sull'istanza di LP (o MILP). Consideriamo la seguente porzione di codice:

LP lp = new LP(pl_string); 
SolutionType solution_type=lp.resolve();
         
if(solution_type==SolutionType.OPTIMUM) {
    Solution soluzione=lp.getSolution();
    for(Variable var:soluzione.getVariables()) {
       	SscLogger.log("Variabile "+var.getName() +": "+var.getLower() + " <= ["+var.getValue()+"] <= "+var.getUpper());
    }
    SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
}

Il metodo getSolution() restituisce un oggetto che implementa l'interfaccia Solution, dal quale è possibile ottenere informazioni sulla soluzione ottimale o ammissibile. Attraverso l'oggetto Solution, puoi accedere a un array di oggetti Variable, che contengono i valori che le variabili decisionali assumono nella soluzione, oltre a recuperare il valore ottimale della funzione obiettivo con il metodo getOptimumValue().
Oltre ai valori assunti dalle variabili decisionali, gli oggetti Variable permettono di ottenere i relativi upper e lower bound richiamando i metodi getUpper() e getLower(). Questa funzionalità consente di verificare facilmente i limiti inferiori e superiori definiti in fase di formulazione del problema su ciascuna variabile.
Se invece hai impostato la ricerca di una soluzione ammissibile ma non ottimale, tramite il metodo setJustTakeFeasibleSolution(true), dovrai utilizzare al posto di getOptimumValue() il metodo getValue() per ottenere il valore della funzione obiettivo, poiché non verrà calcolato il valore ottimale (vedi esempio 2.14).

L'oggetto Solution fornisce anche altre informazioni utili. Ad esempio, tramite il metodo getSolutionConstraint(), è possibile ottenere dettagli sui vincoli. Ecco un esempio pratico:

LP lp = new LP(pl_string); 
SolutionType solution_type=lp.resolve();
                 
if(solution_type==SolutionType.OPTIMUM) {
    Solution soluzione=lp.getSolution();
    for(SolutionConstraint constraint: soluzione.getSolutionConstraint()) {
        SscLogger.log("Vincolo "+constraint.getName()+" : value ="+constraint.getValue()+
                      "[ "+constraint.getRel()+"  "+constraint.getRhs()+" ]" );
    }
}

In questo codice, richiamando il metodo getSolutionConstraint(), otteniamo un array di oggetti SolutionConstraint, che rappresentano i vincoli risolti, ovvero i valori dei vincoli nella soluzione individuata. Questi valori, chiamati LHS (Left Hand Side), sono confrontati con i corrispettivi valori RHS (Right Hand Side) tramite il metodo getRhs().
Nel contesto di un problema di programmazione lineare della forma AX<=>b, LHS rappresenta il prodotto AX, mentre RHS rappresenta b. È importante notare che le variabili inserite nella parte destra del segno di disuguaglianza o uguaglianza durante la definizione del problema in formato testo non saranno considerate come parte del RHS, ma verranno raggruppate nei valori AX.
Il codice mostra anche il nome del vincolo (ottenuto tramite getName()) e il tipo di vincolo (getRel()), consentendo una visione completa delle caratteristiche dei vincoli risolti.

Infine, nel caso di un problema di programmazione lineare intera (MILP), tramite l'oggetto Solution è possibile ottenere informazioni non solo sulla soluzione ottima misto intera individuata, ma anche sul suo rilassamento lineare. Ricordiamo che un rilassamento lineare è una versione semplificata di un problema di ottimizzazione ottenuta rimuovendo o allentando alcuni vincoli, in questo caso quelli di integrità. Per cui i vincoli che richiedono che le variabili siano intere vengono rimossi, consentendo alle variabili di assumere valori continui.
Per ottenere informazioni in merito alla soluzione rilassata occorre invocare sull'istanza MILP il metodo getRelaxedSolution() che restituirà sempre un oggetto Solution contenente però le informazioni inerenti la soluzione rilassata, come da esempio che segue:

MILP milp = new MILP(fo,constraints);
SolutionType solution=milp.resolve();
 
if(solution==SolutionType.OPTIMUM) { 
    Solution sol=milp.getSolution();
    Solution sol_relax=milp.getRelaxedSolution();
    Variable[] var=sol.getVariables();
    Variable[] var_relax=sol_relax.getVariables();
    for(int _i=0; _i< var.length;_i++) {
        SscLogger.log("Nome variabile :"+var[_i].getName() + " valore:"+var[_i].getValue()+ 
                      " ["+var_relax[_i].getValue()+"]");
    }
    SscLogger.log("valore ottimo:"+sol.getOptimumValue() +" valore rilassamento : ["+sol_relax.getOptimumValue()+"]"); 
}

È importante precisare che anche sulle variabili semicontinue si applica il rilassamento; questo determinerà che se x è una variabile semicontinua per la quale x puo assumere valori in \( x \in \text{{0}} \cup [l, u] \), la soluzione rilassata verrà calcolata in x su un nuovo insieme di valori più ampio (rilassato): \( x \in [0, u] \).

4.4 Salvataggio dei Risultati in Formato JSON

La libreria permette di salvare la soluzione di un problema di Programmazione Lineare Mista Intera (MILP) o Programmazione Lineare (LP) in formato JSON. Utilizzando il metodo resolve(null) è possibile costruire una catena di chiamate per salvare i risultati su un file esterno o manipolare direttamente la rappresentazione JSON della soluzione.

Ecco un esempio di come creare una catena per salvare il risultato in un file JSON:

new MILP(pl_string)
    .setTitle("Esempio risultati in JSON")
    .resolve(null)
    .getSolutionAsJson()
    .saveToFile("c:\\sscResult\\solution.json");

In questo esempio, la soluzione del problema viene risolta e memorizzata in un file JSON esterno. È importante notare che viene passato il valore null al metodo resolve() per abilitare il concatenamento dei metodi, permettendo di ottenere la soluzione senza restituire un tipo di risultato specifico.

In alternativa, è possibile memorizzare la soluzione in una stringa JSON:

String json = new MILP(pl_string)
    .resolve(null)
    .getSolutionAsJson()
    .toString();

Se nel salvataggio del JSON, in un file esterno o in una stringa, si vuole che esso sia formattato, ovvero che presenti indentazione e ritorni a capo, richiamare il metodo formatted(true), come nell'esempio seguente:

String json = new MILP(pl_string)
    .resolve(null)
    .getSolutionAsJson()
    .formatted(true)
    .toString();

Se si preferisce lavorare con un oggetto JSON direttamente, come JsonObject della libreria jakarta.json, è possibile fare in questo modo:

JsonObject jsonObject = new MILP(pl_string)
    .resolve(null)
    .getSolutionAsJson()
    .getJsonObject();

La struttura JSON generata avrà diverse sezioni, che possono includere informazioni come meta-dati, vincoli e bounds delle variabili (vedi esempio 1.18). La struttura del JSON è la seguente:

{
    "meta": { ... },
    "objectiveType": "min",
    "status": "optimal",
    "solution": { ... },
    "relaxedSolution": { ... }
}

Le diverse sezioni presenti nel JSON possono essere aggiunte o rimosse specificando le costanti SolutionDetail nel metodo getSolutionAsJson(). Ad esempio, per includere i bounds delle variabili e la soluzione rilassata:

MILP milp=new MILP(pl_string);
milp.resolve();
String json=milp.getSolutionAsJson(SolutionDetail.INCLUDE_BOUNDS,SolutionDetail.INCLUDE_RELAXED).toString();

I valori che SolutionDetail può assumere includono:
INCLUDE_BOUNDS: Aggiunge i bounds (limiti superiori e inferiori) delle variabili specificati in fase di formulazione del problema.
INCLUDE_RELAXED: Include la soluzione rilassata (vedi paragrafo precedente).
INCLUDE_CONSTRAINT: Aggiunge i valori LHS e RHS dei vincoli del problema (vedi paragrafo precedente).
INCLUDE_META: Fornisce meta-informazioni sull'ottimizzazione, come il tempo di esecuzione e il numero di thread.
INCLUDE_TYPEVAR: Include il tipo di ciascuna variabile (es. intera, binaria, continua).

4.5 Logging

In SSC è attivo di default un logger che mostra le informazioni della avvenuta esecuzione, informando l'utente mediante messaggi sulla console. Prendiamo ad esempio il log relativo all'esecuzione del problema 1.1 presente nella sezione Esempi di questo sito :


11/09/24 15:03:57 - INFO:  
11/09/24 15:03:57 - INFO: ##############################################
11/09/24 15:03:57 - INFO: SSC Version 4.2.2
11/09/24 15:03:57 - INFO: ##############################################
11/09/24 15:03:57 - INFO:  
11/09/24 15:03:57 - INFO: Aperta sessione con ID: 1700441298
11/09/24 15:03:57 - INFO: Assegnata libreria WORK C:\ssclab\ssc_work\work_1720063492
11/09/24 15:03:58 - INFO: Avviata procedura utilizzando il seguente numero di Thread: 1
11/09/24 15:03:58 - INFO: ---------------------------------------------
11/09/24 15:03:58 - INFO: Valore funzione obiettivo fase Uno :8.881784197001252E-16
11/09/24 15:03:58 - TIME: Durata fase Uno Simplesso 00:00:00:007 (hh:mm:ss:mmm)
11/09/24 15:03:58 - INFO: Numero iterazioni fase Uno Simplesso :2
11/09/24 15:03:58 - TIME: Durata fase Due Simplesso 00:00:00:013 (hh:mm:ss:mmm)
11/09/24 15:03:58 - INFO: Numero iterazioni totali (fase Uno + fase Due)  Simplesso :3
11/09/24 15:03:58 - TIME: Durata totale Simplesso 00:00:00:020 (hh:mm:ss:mmm)
11/09/24 15:03:58 - INFO: Il simplesso ha trovato una soluzione ottima. 
11/09/24 15:03:58 - INFO: ---------------------------------------------
11/09/24 15:03:58 - INFO: Accuratezza soluzione ottima x :  
11/09/24 15:03:58 - INFO: Ax + s = b ->  Ax + s - b = e (errore).  
11/09/24 15:03:58 - INFO: x >= 0, b >= 0, s >= 0 variabili slacks. 
11/09/24 15:03:58 - INFO: Errore medio, Mean(e):2.886579864025407E-14
11/09/24 15:03:58 - INFO: Errore massimo, Max(e):1.1368683772161603E-13
11/09/24 15:03:58 - INFO: ---------------------------------------------
11/09/24 15:03:58 - INFO: Chiusa sessione con ID: 1700441298
11/09/24 15:03:58 - LOG: Nome variabile :X2 valore :0.0
11/09/24 15:03:58 - LOG: Nome variabile :X3 valore :0.0
11/09/24 15:03:58 - LOG: Nome variabile :X4 valore :0.0
11/09/24 15:03:58 - LOG: Nome variabile :X5 valore :0.0
11/09/24 15:03:58 - LOG: Nome variabile :Y valore :4.0
11/09/24 15:03:58 - LOG: Valore ottimo:12.0

Il sistema di logging della libreria fornisce informazioni sull'esecuzione dell'algoritmo di risoluzione. Le voci marcate come "INFO" offrono un quadro generale sull'avanzamento, inclusa l'apertura e la chiusura della sessione di lavoro, il numero di thread utilizzati e i risultati del metodo del simplesso, come il numero di iterazioni e l'accuratezza della soluzione. Le voci "TIME" indicano la durata di ciascuna fase del processo. Al contrario, le voci con "LOG" sono generate dallo sviluppatore utilizzando la classe SscLogger e, nel nostro esempio, permettono di visualizzare dettagli specifici sulla soluzione trovata, come i valori delle variabili e il valore ottimo della f.o.. In questo caso è lo sviluppatore a decidere se scrivere determinati risultati nel log oppure gestirli diversamente per memorizzarli su altre locazioni. Per scrivere sul log, che di default stampa i messaggi nella console standard (di solito, System.out), basta invocare il metodo log() della classe SscLogger, come nell'esempio:

SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());

Questa istruzione generera sulla console standard il seguente messaggio :

11/09/24 15:03:58 - LOG: Valore ottimo:12.0

Ricordiamo che le classi per il logging (SscLogger, SscLevel) sono contenute nel package org.ssclab.log.
Lo sviluppatore se vuole può non solo generare messaggi di tipo "LOG" , ma anche degli altri "livelli", utilizzando i metodi disponibili. Ad esempio per generare un messaggio "INFO", uno "WARNIG" ed uno "ERROR" occorre utilizzare le seguenti istruzioni :

SscLogger.info("Avvio programma ottimizzazione.");
SscLogger.warning("Il numero di variabili e' molto elevato.");
SscLogger.error("C'e stato un errore durante l'elaborazione.");

Queste istruzioni genereranno sulla console standard i seguenti messaggi :

11/09/24 16:47:26 - INFO: Avvio programma ottimizzazione.
11/09/24 16:47:26 - WARNING: Il numero di variabili e' molto elevato.
11/09/24 16:47:26 - ERROR: C'e stato un errore durante l'elaborazione.

Se lo sviluppatore non ha necessità di avere un log, può disabilitarlo ponendo all'inizio del suo codice la seguente istruzione :

SscLogger.setLevel(SscLevel.OFF);

L'istruzione appena utilizzata non fa altro che impostare il log ad un determinato livello attraverso il metodo setLevel(). Ciò sta ad indicare che esistono diversi livelli, impostabili dallo sviluppatore, ognuno dei quali permette di visualizzare solo i messaggi che appartengono al livello impostato e ai livelli gerarchicamente superiori. La gerarchia, e quindi anche i livelli selezionabili, sono i seguenti:

ALL FINE CONFIG INFO LOG TIME NOTE WARNING ERROR

Nel momento in cui si seleziona un livello, tutti i restanti livelli posizionati alla destra della lista, insieme al livello prescelto, risultano visualizzabili sulla console. Ad esempio se si sceglie "WARNING" (con l'istruzione SscLogger.setLevel(SscLevel.WARNING)), verranno visualizzati soli i "WARNING" e gli "ERROR".
Se il log deve essere memorizzato su file esterno è possibile inviare il logging su file utilizzando la seguente istruzione :

SscLogger.setLogToFile("c:\\logs\\simplesso.log",true);

Che permette di memorizzare il log nel file di nome simplesso.log; il secondo parametro permette, se true, di andare in append.

4.6 Documentazione API

La documentazione API è disponibile al seguente link API.