SSC (Software for Simplex Calculation) è 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.

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

\( \hspace{3cm} \text{ max/min } \hspace{0.3cm} c^{\mathrm{T}}x \hspace{1cm} \text{è la funzione obiettivo (f.o.) } \)

vincolato a :

\( \hspace{3cm} Ax\, (\le , = , \ge)\, b \)
\( \hspace{3cm} l_{i} \le x_{i} \le u_{i} \hspace{0.5cm} \text{ oppure }\, x_{i}=0\)
\( \hspace{3cm} x_{i} \in \mathbb{Z} \hspace{1.6cm} \forall i \in \text{I} \)
\( \hspace{3cm} x_{i} \in \{0,1\} \hspace{0.8cm} \forall i \in \text{B} \)
\( \hspace{3cm} x_{i} \in \mathbb{R} \hspace{1.6cm} \forall i \notin (\text{I} \cup \text{B}) \)

dove:

\( \hspace{3cm} x\, \in \mathbb{R}^{n} \hspace{5cm} \text{è il vettore delle variabili}\, x_{i} \)
\( \hspace{3cm} A \in \mathbb{Q}^{m \times n} \hspace{4.4cm} \text{è la matrice dei coefficienti} \)
\( \hspace{3cm} c\,\, \in \mathbb{Q}^{n} \hspace{5cm} \text{è il vettore dei coefficienti della f.o.} \)
\( \hspace{3cm} b\,\, \in \mathbb{Q}^{m} \hspace{4.9cm} \text{è il vettore dei coefficienti RHS} \)
\( \hspace{3cm} l\,\,\, \in \mathbb{Q}^{n} \hspace{5cm} \text{è il vettore dei lower bound }\, l_{i} \)
\( \hspace{3cm} u\, \in \mathbb{Q}^{n} \hspace{5cm} \text{è il vettore degli upper bound }\, u_{i} \)
\( \hspace{3cm} \text{I}\,\, \subseteq \{1,..,n\} \hspace{3.7cm} \text{è un sottoinsieme degli indici relativo alla variabili intere} \)
\( \hspace{3cm} \text{B} \subseteq \{1,..,n\}\, : \, (\text{I} \cap \text{B}) = \emptyset \hspace{0.9cm} \text{è un sottoinsieme degli indici relativo alla variabili binarie} \)

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.

Il metodo del simplesso è un algoritmo efficiente per la risoluzione di problemi di programmazione lineare continui (ovvero, quelli privi di variabili intere), il che consente di gestire problemi con un numero elevato di variabili e vincoli. Eseguendo il simplesso con SSC, i limiti sono eventualemnte legati alla disponibilità di memoria della jvm. Ad esempio se si dichiara alla jvm di rendere disponibile una quantità massima di 4 Gigabyte di memoria (tramite la dichiarazione -Xmx4g) è possibile risolvere problemi con migliaia di variabili e migliaia di vincoli.

Al contrario, il metodo del Branch and Bound ha una complessità computazionale maggiore, in quanto deve risolvere una succcessione di simplessi; questo lo rende molto più oneroso in termini di tempo di calcolo e risorse necessarie rispetto al singolo metodo del simplesso. Di conseguenza, la dimensione dei problemi di MILP risolvibili non può che essere limitata.

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