Software per il calcolo del simplesso

SSC (Software per il Calcolo del Simplesso) è una libreria java per la risoluzione di problemi di programmazione lineare. SSC utilizza l'algoritmo del Simplesso per risolvere questa classe di problemi di ottimizzazione di norma indicati con la sigla LP (Linear Programming).

In SSC è possibile risolvere anche problemi con variabili libere, intere, binarie, semicontinue e semicontinue intere. Questa sottoclasse di problemi sono di norma denominati con la sigla MILP (Mixed Integer Linear Programming). Nel caso di problemi MILP, che presentano tutte o una parte di variabili intere o binarie o semicontinue, SSC utilizza l'algoritmo del Branch and Bound (B&B) per la loro risoluzione.

A partire dalla versione 2.1.0.r6 è possibile eseguire una implementazione del metodo del simplesso parallelo. Questa opzione (vedi esempio 1.14) permette di sfruttare thread multipli per la risoluzione del simplesso è da significativi vantaggi nel caso di architetture con almeno 4 o più core fisici. A partire da questa versione è possibile eseguire anche una implementazione del Branch and Bound parallelo (vedi esempio 2.13); con questa implementazione si hanno dei vantaggi sulla durata anche a partire da due core fisici.

Un problema da risolvere

La forma di problemi che le API fornite da SSC risolvono è la seguente :

		max/min  cTx	è la funzione obiettivo (f.o.)
vincolato a
		Ax (≤,=,≥) b		
		lxu oppure xᵢ=0
		xᵢ∈ ℤ ∀i ∈ I 
		xᵢ∈ {0,1} ∀i ∈ B 
		xᵢ∈ ℝ ∀i∉ (I ∪ B); 
dove
		x ∈ ℝn  	è il vettore delle variabili    
		A ∈ ℚmxn	è la matrice dei coefficienti 
		c ∈ ℚn  	è il vettore dei coefficienti della f.o.
		b ∈ ℚm  	è il vettore dei coefficienti RHS
		l ∈ ℚn  	è il vettore dei lower bound 
		u ∈ ℚn  	è il vettore degli upper bound 
		I ∈ {1,...,n}   è un sottoinsieme degli indici 
		B ∈ {1,...,n} : (I ∩ B) = ∅ 

Dettagli

Il metodo del simplesso puo' essere suddiviso in due fasi. Nella fase 1 si trova una soluzione di base ammissibile, mentre nella fase 2 si trova una soluzione ottimale. La procedura gestisce variabili libere, variabili delimitate inferiormente e superiormente e le diverse gamme di vincoli. Se non vengono specificati limiti inferiori espliciti, SSC definisce le variabili delimitate inferiormente dallo zero (variabili non negative).

In SSC quando una variabile viene definita come una variabile intera o binaria, la procedura utilizza l'algoritmo del Branch and Bound per l'ottimizzazione. Nel Branch and Bound si risolve una successione di problemi rilassati (ovvero privati dei vincoli di interezza); per risolvere questi problemi rilassati si utilizza l'algoritmo del Simplesso.

Dimensioni dei problemi e richiesta di memoria

Il metodo del simplesso implementato in SSC risulta molto efficiente in quanto si č cercato di ottimizzare tutte le fasi dell'algoritmo stesso. I problemi risolvibili con SSC non hanno limiti nel numero di variabili e vincoli, i limiti sono dati dalla disponibilità di memoria della jvm. Ad esempio se si dichiara alla jvm di rendere disponibile una quantità masssima di 4 Gigabyte di memoria (tramite la dichiarazione -Xmx4g) è possibile risolvere problemi con decine di migliaia di variabili e migliaia di vincoli.

Al contrario il metodo del Branch and Bound non ha una grande efficienza; esistono in letteratura metodi certamente molto pių efficienti dal punto di vista della complessità computazionale e nell'utilizzo della memoria (ad esempio Branch and Cut and Price). Di conseguenza la dimensione dei problemi di MILP risolvibili non può che essere limitata.

Requisiti tecnici

Il requisito per far eseguire i programmi SSC è quello di poter disporre di un JDK (o SDK) java versione 8.x o successive. Nessun altro requisito è richiesto.