Esempi Java API simplesso

Indice degli esempi

Programazione lineare
Programazione lineare intera, misto intera e binaria

Esempio 1.1

Si consideri il seguente problema di LP:

	 max  X₁ +   3X₂
	 
	      X₁ +    X₂ ≥-1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ +   3X₂ = 5
   	    
   	 con X₁, X₂ ≥ 0

Per risolvere questo problema con SSC basta creare del testo dove ciascun rigo rappresenta o la funzione obiettivo o un vincolo, mentre le colonne rappresentano i coefficienti delle variabili, le relazioni, i valori rhs [righi 14-17 del codice sottostante]. Questa rappresentazione è denominata a coefficienti.

Formulato il problema occorre specificare il suo tracciato record (o formato di input). Per formato di input intendiamo una dichiarazione che descrive come vanno lette ed interpretate le colonne presenti nel testo in cui si è formulato il problema [righi 14-17]. La definizione del formato di input si effettuata attraverso una stringa da passare come argomento al metodo setInputFormat() [rigo 21]; in questa stringa si susseguono le notazioni "nome colonna : tipologia colonna" per definire, in sequenza, il nome ed il tipo delle colonne. In definitiva si dichiarano: i nomi delle prime due colonne che rappresentano le variabili del problema di LP (in questo caso X₁ e X₂, di tipo numerico double), la colonna delle relazioni (chiamata TYPE e di tipo stringa), la colonna dei valori rhs (chiamata RHS e di tipo double). I nomi da assegnare alle variabili del problema di LP possono essere qualsiasi, mentre la colonna delle relazioni e quella dei valori rhs devono necessariamente chiamarsi TYPE e RHS [rigo 21].

Di norma possiamo chiamare le variabili in qualsiasi modo, anche con nomi non necessariamente seguiti da un numero, ad esempio : "FUEL:double, AMOUNT:double, WEIGHT:double", etc, etc. Di solito però è preferibile dichiarare le n variabili di un problema con una diversa notazione, chiamata ad intervalli, che risulta particolarmente utile se le variabili del problema sono decine o centinaia. In questo caso la dichiarazione "X1:double, X2:double, X3:double, .... , Xn:double" di n variabili, può essere sostituita con la notazione "X1-Xn:double". Questa seconda notazione, certamente più compatta, permette di dichiarare tutte le variabili comprese nell'intervallo che va da X₁ a X_n.

Una volta rappresentato il problema e assegnati i nomi alle variabili, si esegue l'algoritmo del Simplesso mediante la creazione di un oggetto della classe LP e l'invocazione del metodo resolve() [righi 23-24]. Una volta eseguito il Simplesso, il metodo resolve() ritorna il tipo di soluzione trovata; se la soluzione è ottima è possibile ricavare i valori delle variabili ed il valore ottimo della funzione obiettivo. Si ricorda che in SSC, di default, le variabili di un problema di LP sono considerate, se non diversamente specificato, non negative ( ≥ 0).


import it.ssc.log.SscLogger;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;


public class Esempio {
	
	public static void main(String[] args) throws Exception {

		String lp_string = 
			                " 1    3    max      .    \n" +  
			                " 1    1    ge      -1    \n" +	  
			                " 1  1.4    le       6    \n" +  
			                "-5    3    eq       5";
			

		InputString lp_input = new InputString(lp_string); 
		lp_input.setInputFormat("X1:double, X2:double, TYPE:varstring(3), RHS:double"); 

		LP lp = new LP(lp_input); 
		SolutionType solution_type=lp.resolve();
		
		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=lp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
		else SscLogger.log("Soluzione non ottima:"+solution_type);
	}
}

Esempio 1.2

Si consideri il problema di LP riportato nell'esempio precedente e dato da:

	 max  X₁ +   3X₂
	 
	      X₁ +    X₂ ≥-1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ +   3X₂ = 5
   	    
   	 con X₁, X₂ ≥ 0

Il problema dell'esempio precedente può essere espresso anche attraverso l'uso di vettori e matrici. Il formato di rappresentazione utilizzato è simile a quello di Apache simplex solver. In questo caso occorre definire la matrice A dei coefficienti , il vettore c dei coefficienti della f.o. ed il vettore b dei valori RHS.

Definite tali entità [righi 18-23] si crea un oggetto LinearObjectiveFunction [rigo 27] che rappresenta la funzione obiettivo e gli oggetti Constraint [rigo 31] che rappresentano i vincoli. Il tipo di vincolo (LE, GE, EQ) viene specificato attraverso gli elementi dell'array delle relazioni "rel", array contenente oggetti di tipo ConsType [rigo 25]. Infine, la lista di vincoli e la funzione obiettivo sono parametri sufficienti per istanziare un oggetto della classe LP [rigo 34].


import it.ssc.log.SscLogger;
import it.ssc.pl.milp.ConsType;
import it.ssc.pl.milp.Constraint;
import it.ssc.pl.milp.GoalType;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.LinearObjectiveFunction;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.pl.milp.ListConstraints;
import java.util.ArrayList;


public class Esempio {

	public static void main(String[] args) throws Exception {

		double A[][]={ 
				{ 1.0 , 1.0 },
				{ 1.0 , 1.4 },
				{-5.0 , 3.0 } } ;
		double b[]= {-1.0, 6.0 ,5.0 };
		double c[]= { 1.0, 3.0  };	

		ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.EQ};

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

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

		LP lp = new LP(fo,constraints); 
		SolutionType solution_type=lp.resolve();

		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=lp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
	}
}

Esempio 1.3

Si consideri il seguente problema di LP :

	 max  X₁ +   3X₂
	 
	      X₁ +    X₂ ≥ 1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ +   3X₂ = 5
   	    
   	 con -1 ≤ X₁ ≤ +1
   	     -∞ ≤ X₂ ≤ +∞

In questo esempio la variabile X₁ risulta delimitata sia inferiormente (non dallo zero) che superiormente. Nella rappresentazione del problema in formato a coefficienti, per poter definire una variabile con tali limiti, basta aggiungere un rigo per gli upper bound e uno per i lower bound [righi 16-17]. Nel caso della variabile X₂ (ovvero di una variabile senza limiti), basta specificare un lower bound e un upper bound indefinito (rappresentato dal ".").

È importante sottolineare che per poter impostare delle variabili libere, ovvero delle variabili che possono assumere anche valori negativi, basta valorizzare un lower bound indefinito (.) o negativo, oppure un upper bound negativo. Al contrario, introdurre un vincolo del tipo X₁ ≥ -1, (ovvero un vincolo di tipo GE) non determina che la variabile diventi libera, ma si vincola solo il problema a soddisfare tale condizione; condizione che non potrà essere vagliata pienamente (permettendo alla variabile di assumere valori negativi) se non si rende la variabile effettivamente libera. Per renderla libera si deve usare esclusivamente la notazione degli upper e lower bound. In questo esempio sia X₁ che X₂ sono variabili libere.

Infine in fase di stampa della soluzione è possibile recuperare per ogni variabile gli upper ed i lower precedentemente valorizzati in fase di formulazione del problema [rigo 29].

import it.ssc.log.SscLogger;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;
 
public class Esempio {
    public static void main(String[] args) throws Exception {
 
        String lp_string = 
                            " 1    3    max      .    \n" + 
                            " 1    1    ge       1    \n" + 
                            " 1  1.4    le       6    \n" +
                            "-5    3    eq       5    \n" + 
                            " 1    .    upper    .    \n" +
                            "-1    .    lower    .    \n" ; 
             
 
        InputString lp_input = new InputString(lp_string); 
        lp_input.setInputFormat("X1-X2:double, TYPE:varstring(8), RHS:double"); 
 
        LP lp = new LP(lp_input); 
        SolutionType solution_type=lp.resolve();
             
        if(solution_type==SolutionType.OPTIMUM) {
            Solution solution=lp.getSolution();
            for(Variable var:solution.getVariables()) {
                SscLogger.log("Variabile "+var.getName() +": "+var.getLower() + " <= ["+var.getValue()+"] <= "+var.getUpper());
            }
            SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
        }   
    }
}

Esempio 1.4

Si consideri il seguente problema di LP riportato nell'esempio precedente:

	 max  X₁ +   3X₂
	 
	      X₁ +    X₂ ≥ 1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ +   3X₂ = 5
   	    
   	 con -1 ≤ X₁ ≤ +1
   	     -∞ ≤ X₂ ≤ +∞

Risolviamo l'esempio precedente utilizzando il formato matriciale. Per poter rappresentare la variabile X₁, che risulta delimitata sia inferiormente che superiormente, occorre aggiungere alla matrice A un rigo per gli upper bound e uno per i lower bound [righi 21-22]. Nel caso della variabile X₂, ovvero di una variabile libera senza limiti , basta specificare un lower bound e un upper bound indefinito con il valore NaN.

Ricordiamo che per poter impostare delle variabili libere, ovvero delle variabili che possono assumere anche valori negativi, basta valorizzare un lower bound indefinito (.) o negativo, oppure un upper bound negativo. In questo esempio sia X₁ che X₂ sono libere.

Occorre poi aggiungere nel vettore delle relazioni [rigo 27] le costanti che dichiarano che gli ultimi due righi della matrice A sono relativi agli upper e lower bound (si aggiunge ConsType.UPPER e ConsType.LOWER). Infine, va aggiornata anche la dimensione del vettore b (aggiungendo due valori NaN) che deve essere uguale al numero di righi della matrice A.

import it.ssc.log.SscLogger;
import it.ssc.pl.milp.ConsType;
import it.ssc.pl.milp.Constraint;
import it.ssc.pl.milp.GoalType;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.LinearObjectiveFunction;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import static it.ssc.pl.milp.LP.NaN;
import java.util.ArrayList;

public class Esempio {
	
	public static void main(String[] args) throws Exception {

		double A[][]={ 
				{ 1.0 , 1.0  },
				{ 1.0 , 1.4  },
				{-5.0 , 3.0  },
				{ 1.0 , NaN },
				{-1.0 , NaN }} ;
		
		double b[]= { 1.0, 6.0 ,5.0, NaN, NaN };
		double c[]= { 1.0, 3.0  };	

		ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.EQ, ConsType.UPPER, ConsType.LOWER};

		LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);

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

		LP lp = new LP(f,constraints); 
		SolutionType solution_type=lp.resolve();

		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=lp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
	}
}

Esempio 1.5

Si consideri il seguente problema di LP :

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

Vogliamo risolvere questo problema usando un altro formato di rappresentazione denominato a disequazioni. In questo formato la funzione obiettivo e i vincoli possono essere espressi mediante equazioni/disequazioni rappresentate all'interno di stringhe [righi 17-21]. Le variabili possono avere qualsiasi nome (devono però iniziare con un carattere alfabetico seguito da caratteri alfanumerici) e risultano non essere case-sensitive (ovvero x3 e X3 rappresentano la stessa variabile).

Uno dei vantaggi di questo formato è che se una variabile non è presente in un vincolo questa può essere tralasciata, a differenza del formato matriciale o a coefficienti dove deve essere rappresentata con un coefficiente uguale a zero. E' importante ricordare che la totalità delle variabili del problema devono però essere espresse nella funzione obiettivo.

				
import java.util.ArrayList;
import it.ssc.log.SscLogger;
import it.ssc.pl.milp.GoalType;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.LinearObjectiveFunction;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;

public class Esempio {
	
	public static void main(String[] args) throws Exception {

		
		ArrayList< String > constraints = new ArrayList< String >();
		constraints.add("min:  3Y +2x2 +4x3 +7x4 +8X5 "); 
		constraints.add("5Y +2x2 +3X4       >= 9");
		constraints.add("3Y + X2 +X3 +5X5   >= 12");
		constraints.add("6Y+3.0x2 +4X3 +5X4 <= 124");
		constraints.add(" y + 3x2 +3X4 +6X5 <= 854");
		
		LP lp = new LP(constraints); 
		SolutionType solution_type=lp.resolve();
		
		if(solution_type==SolutionType.OPTIMUM) {
			Solution soluzione=lp.getSolution();
			for(Variable var:soluzione.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore :"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
		}
	}
}

Esempio 1.6

Si consideri il seguente problema di LP :

	
   	 min  3Y + 2X₂ + 4Z + 7X₄ + 8X₅
   	 
   	      5Y + 2X₂      + 3X₄       ≥   9
   	      3Y +  X₂ +  Z      + 5X₅  ≥  12
   	      6Y + 3X₂ + 4Z + 5X₄       ≤ 124
   	       Y + 3X₂      + 3X₄ + 6X₅  ≤ 854
   	      
   	 con Y, X₄, X₅ ≥ 0
   	    -1 ≤ X₂ ≤ +6
   	     1 ≤ Z ≤ +∞

Vogliamo risolvere questo problema usando il formato di rappresentazione a disequazioni. In questo formato per definire gli upper e lower bound occorre aggiunge rispettivamente un rigo per ogni variabile da limitare [righi 15-16].



import java.util.ArrayList;
import it.ssc.log.SscLogger;
import it.ssc.pl.milp.*;

public class Esempio {
	
	public static void main(String[] args) throws Exception {
		
		ArrayList< String > constraints = new ArrayList< String >();
		constraints.add("min:  3Y +2x2   +4Z +7x4 +8X5 ");
		constraints.add("      5Y +2x2       +3X4      >= 9");
		constraints.add("      3Y + X2   + Z       +5X5 >= 12");
		constraints.add("      6Y +3.0x2 +4Z +5X4      <= 124");
		constraints.add("       Y +3x2       +3X4 +6X5 <= 854");
		constraints.add("-1<=  x2 <= 6");
		constraints.add("1 <=  z  <= .");
			
		LP lp = new LP(constraints); 
		SolutionType solution_type=lp.resolve();
		
		if(solution_type==SolutionType.OPTIMUM) {
			Solution soluzione=lp.getSolution();
			for(Variable var:soluzione.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore :"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
		}
	}
}

Esempio 1.7

Si consideri il seguente problema di LP riportato nell'esempio 1.4:

	 max  X₁ +   3X₂
	 
	      X₁ +    X₂ ≥ 1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ +   3X₂ = 5
   	    
   	 con -1 ≤ X₁ ≤ +1
   	     -∞ ≤ X₂ ≤ +∞

L'esempio 1.4 può essere rappresentato con un quarto formato denominato "sparso" [righi 17-40]. Ogni espressione del tipo EQ, LE, GE, UPPER, LOWER, MAX, MIN, ha associato un nome (nome del rigo). Tale nome inizialmente viene dichiarato nella colonna dei ROW_ con associato un TYPE per indicarne appunto la tipologia [righi 17-22]. La colonna TYPE può assumere di conseguenza solo uno dei seguenti valori: EQ, LE, GE, UPPER, LOWER, MAX, MIN.

Successivamente vanno dichiarate le variabili del problema valorizzando la colonna COL_, attraverso questa colonna si esprimere il valore che la variabile assume su quel rigo . Oltre alle variabili, nella COL_ va indicato anche il marcatore dei valori rhs. Se i nomi delle variabili possono essere qualsiasi, il marcatore dei valori rhs deve essere espresso necessariamente con la notazione RHS. In definitiva la definizione del coefficiente che ogni variabile assume su ogni rigo si effettua valorizzando, per ogni combinazione ROW_ e COL_, il relativo valore nella colonna COEF. Definito il problema occorre dichiarare nel formato di lettura [rigo 44] il nome e il tipo (con la relativa lunghezza) delle quattro entità richieste da questo formato : TYPE, COL_, ROW_ e COEF.

Per poter istanziare con questo formato un oggetto LP occorre passare come argomento al costruttore la costante FormatType.SPARSE per informare l'oggetto LP del tipo di formato utilizzato [rigo 46]. Questo formato è particolarmente indicato per prelevare problemi presenti in tabelle di database, in quanto la struttura della tabella richiesta è sempre la stessa: basta che questa definisca le colonne TYPE, COL_, ROW_ e COEF.

Occorre infine ricordare che i valori della colonna TYPE e COL_ possono essere espressi sia in maiuscolo che in minuscolo; in entrambi i casi essi verranno ricondotti al maiuscolo; mentre per la colonna ROW_ esprimere il nome di un rigo contemporaneamente in minuscolo e in maiuscolo, nell'ambito di una stessa formulazione, significa dichiarare due nomi (e quindi due righi ) distinti.


import it.ssc.log.SscLogger;
import it.ssc.pl.milp.FormatTypeInput.FormatType;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;

public class Esempio {
	
	public static void main(String[] args) throws Exception {

		String lp_sparse = 
		
			//    TYPE   COL_   ROW_    COEF 
				 
				" MAX     .    costo      .    \n" +   
                " GE      .    row1       .    \n" +	  
                " LE      .    row2       .    \n" +  
                " EQ      .    row3       .    \n" +
                " UPPER   .    lim_sup    .    \n" +
                " LOWER   .    lim_inf    .    \n" +              
		
				" .      X1    costo      1    \n" +
				" .      X1    row1       1    \n" +	  
		        " .      X1    row2       1    \n" +  
		        " .      X1    row3      -5    \n" +
		        " .      X1    lim_sup    1    \n" +
		        " .      X1    lim_inf   -1    \n" +		       
				 
				" .      X2    costo      3    \n" +
				" .      X2    row1       1    \n" +	  
		        " .      X2    row2     1.4    \n" +  
		        " .      X2    row3       3    \n" +
		        " .      X2    lim_sup    .    \n" +
		        " .      X2    lim_inf    .    \n" +	       
		         
				" .      RHS   row1       1    \n" +	  
				" .      RHS   row2       6    \n" +  
				" .      RHS   row3       5    \n"   ;
			

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

		LP lp = new LP(lp_input,FormatType.SPARSE); 
		SolutionType solution_type=lp.resolve();
		
		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=lp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
	}
}

Esempio 1.8

Si consideri il seguente problema di LP :

	
   	 min  3Y₁ +  Y₂ + 4Y₃ + 7Y₄ + 8Y₅
   	 
   	      5Y₁ + 2Y₂      + 3Y₄       ≥   9
   	      3Y₁ +  Y₂ +  Y₃      + 5Y₅  ≥  12
   	      6Y₁ + 3Y₂ + 4Y₃ + 5Y₄       ≤ 124
   	      1Y₁ + 3Y₂      + 3Y₄ + 6Y₅  ≤ 854
   	      
   	 con Y₁, Y₄, Y₅ ≥ 0
   	     0 ≤ Y₂ ≤ +6
   	     1 ≤ Y₃ ≤ +∞

In questo caso vogliamo risolvere un problema di LP la cui formulazione si trova in un file di testo (.txt). Chiamiamo tale file pl_problem.txt e utilizziamo, per la rappresentazione del problema, il formato a coefficienti. Nel file pl_problem.txt avremo il seguente contenuto:

   	     
3 1 4 7 8 min      . 
5 2 0 3 0 ge       9 
3 1 1 0 5 ge       12
6 3 4 5 0 le       124
1 3 0 3 6 le       854
. 6 . . . upper    . 
0 0 1 0 0 lower    .

Definito tale file di testo, occorre informare SSC che il problema è contenuto nel file pl_problem.txt [rigo 12]. Se si hanno un numero significativo di variabili (in questo caso solo 5, ma possono essere molte di più) queste si possono dichiarare mediante notazione ad intervallo [rigo 13], dove con la sintassi "Y1-Y5:double" si dichiarano 5 variabili distinte (Y1, Y2, Y3, Y4, Y5) di tipo double.



import it.ssc.log.SscLogger;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputFile;

public class Example {
	
	public static void main(String[] args) throws Exception {

		InputFile input = new InputFile("c:/dati_pl/pl_problem.txt");
		input.setInputFormat("Y1-Y5:double, TYPE:varstring(10),  RHS:double");

		LP lp=new LP(input);
		SolutionType solution_type=lp.resolve();
		
		if(solution_type==SolutionType.OPTIMUM) {
			Solution soluzione=lp.getSolution();
			for(Variable var:soluzione.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore :"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
		}
	}
}

Esempio 1.9

Si consideri il seguente problema di LP riportato nell'esempio 1.7:

	 max  X₁ +   3X₂
	 
	      X₁ +    X₂ ≥ 1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ +   3X₂ = 5
   	    
   	 con -1 ≤ X₁ ≤ +1
   	     -∞ ≤ X₂ ≤ +∞

In questo esempio vogliamo recuperare il problema, formulato nel formato sparso, da una tabella di un database (DB) Oracle. Ricordiamo che nel formato sparso l'input necessario per la risoluzione di un problema di LP richiede la presenza delle colonne TYPE, ROW_, COL_ e COEF. Per cui la tabella Orache che contiene il problema deve avere tali colonne. Chiamiamo questa tabella con il nome TAB_PL_PROBLEM, e creiamola con la seguente istruzione DDL :

CREATE TABLE  "TAB_PL_PROBLEM" 
  ("TYPE" VARCHAR2(5), 
   "COL_" VARCHAR2(3), 
   "ROW_" VARCHAR2(7), 
   "COEF" FLOAT(126)
  )

Infine, inseriamo nella tabella i seguenti record (per null si intende il valore null non la stringa "null"):


  MAX     null    costo      null   
  GE      null    row1       null    
  LE      null    row2       null   
  EQ      null    row3       null   
  UPPER   null    lim_sup    null   
  LOWER   null    lim_inf    null        
  null      X1    costo      1   
  null      X1    row1       1    
  null      X1    row2       1   
  null      X1    row3      -5   
  null      X1    lim_sup    1   
  null      X1    lim_inf   -1          
  null      X2    costo      3   
  null      X2    row1       1    
  null      X2    row2     1.4   
  null      X2    row3       3   
  null      X2    lim_sup    null   
  null      X2    lim_inf    null         
  null      RHS   row1       1    
  null      RHS   row2       6   
  null      RHS   row3       5

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 [righi 41-48]. Una volta ottenuta una connessione al DB, tramite l'oggetto Connection è possibile, da SSC, accedere al DB come se fosse una libreria, ovvero un contenitore di tabelle. SSC per poter allocare librerie necessita che venga creata una sessione di lavoro SSC. Una sessione SSC rappresenta l'ambiente nel quale SSC viene eseguito. Negli esempi precedenti la creazione di una sessione non era necessaria in quanto l'oggetto LP crea e usa una sua sessione SSC implicita.

L'invocazione di addLibrary() [rigo 21] permette di aggiunge alla sessione SSC corrente una libreria (di nome "DB_ORACLE") che rappresenta una connessione al DB Oracle. Dopo tale invocazione il metodo addLibrary() ritorna un oggetto che rappresenta una interfaccia a tale contenitore. Da questa interfaccia possiamo [rigo 23] ottenere un oggetto di tipo Input che fa riferimento alla tabella "TAB_PL_PROBLEM". Una volta ottenuto tale input possiamo passarlo al costruttore LP [rigo 24] ed eseguire il Simplesso.

E' da notare che nel costruttore della classe LP viene anche passato come argomento [rigo 24] la sessione SSC creata , questo per non far istanziare all'oggetto LP una seconda sessione del tutto inutile.


import it.ssc.context.Context;
import it.ssc.context.Session;
import it.ssc.library.Library;
import it.ssc.log.SscLogger;
import it.ssc.pl.milp.FormatTypeInput.FormatType;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.Input;
import java.sql.Connection;
import oracle.jdbc.pool.OracleDataSource;
 
public class Esempio {
     
    public static void main(String[] args) throws Exception {
         
        Session session = null;
        try {
            session = Context.createNewSession();
            Library lib_ora=session.addLibrary("DB_ORACLE", connOracle());
         
            Input pl_oracle=lib_ora.getInput("TAB_PL_PROBLEM");
            LP lp = new LP(pl_oracle,session,FormatType.SPARSE); 
            SolutionType solution_type=lp.resolve();
             
            if(solution_type==SolutionType.OPTIMUM) { 
                Solution solution=lp.getSolution();
                for(Variable var:solution.getVariables()) {
                    SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
                }
                SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
            }   
        } 
        finally {
            session.close();
        }
    }
     
     
    private static Connection connOracle() throws Exception {
        OracleDataSource ods = new OracleDataSource();
        String URL = "jdbc:oracle:thin:@//192.168.243.134:1521/XE";
        ods.setURL(URL);
        ods.setUser("user_pl");
        ods.setPassword("ora655"); 
        return ods.getConnection();
    }
}

Esempio 1.10

Nell'esempio sottostante si riporta un semplice problema di LP che vuole evidenziare quali sono i valori che il metodo resolve() può restituire a seconda che il problema di LP :

a) restituisca una soluzione ottima
b) non ammetta soluzioni ammissibili
c) abbia ottimo illimitato
d) raggiunga il numero massimo di iterazioni possibili
e) venga restituita una soluzione ammissibile al posto di una soluzione ottima

Se l'esigenza è quella di ottenere una soluzione ammissibile non necessariamente ottima (caso e), basta invocare il metodo setJustTakeFeasibleSolution() passandogli il valore "true" (rigo 28). Questa opzione permette di far eseguire solo la prima fase del simplesso e di ottenere una prima soluzione (basica) ammissibile. In questo caso il valore restituito dal metodo resolve() (nel caso esista una soluzione ammissibile) sarà SolutionType.FEASIBLE.
Infine ricordiamo che il numero massimo di iterazioni possibili può essere modificato dall'analista [rigo 27].

import it.ssc.log.SscLogger;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;

public class Esempio {
	
	public static void main(String[] args) throws Exception {

		String lp_string = 
			                "5  4   1    3   max     .   \n" +  
			                "4  3   1    1   ge      2   \n" +	  
			                "1 -2   1   -1   le      2   \n" +	  		
			                "3  2   1  1.4   le      6   \n" +  
			                "9  8   4  1.7   le      7   \n" +  
			                "5  3  -1  2.4   le      9   \n" +  
			                "3 -2  -5    3   le      5      ";
			

		InputString lp_input = new InputString(lp_string); 
		lp_input.setInputFormat("V1-V4:double, TYPE:varstring(8), RHS:double"); 

		LP lp = new LP(lp_input); 
		SscLogger.log("Numero di iterazioni di default:"+lp.getNumMaxIteration());
		lp.setNumMaxIteration(5);
		lp.setJustTakeFeasibleSolution(true);  //imposto la ricerca di una soluzione ammissibile , 
		SolutionType solution_type=lp.resolve();
		
		if(solution_type==SolutionType.FEASIBLE) { 
			Solution solution=lp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore assunto dalla soluzione ammissibile sulla f.o.:"+solution.getOptimumValue());
		}	
		else if(solution_type==SolutionType.VUOTUM) {
			SscLogger.log("La fase 1 del simplesso non ha trovato soluzioni ammissibili:("+solution_type+")");
		}
		else if(solution_type==SolutionType.ILLIMITATUM) {
			SscLogger.log("Ottimo illimitato:("+solution_type+")");
		}
		else if(solution_type==SolutionType.MAX_ITERATIUM) {
			SscLogger.log("Raggiunto il numero massimo di iterazioni:("+solution_type+")");
		}
		else if(solution_type==SolutionType.OPTIMUM) { 
			//questa sezione non verrà mai raggiunta in quanto avendo impostato 
			//setJustTakeFeasibleSolution(true), il simplesso può solo restituire soluzioni ammissibili
		}
		
	}
}

Esempio 1.11

Nell'esempio sottostante si vuole risolvere il problema già affrontato nell'esercizio 1.6, con la particolarità che la formulazione del problema (utilizzando il formato a disequazioni) è memorizzata in un file. Chiamiamo questo file pl_proble.txt. Il file menzionato conterrà il seguente contenuto:

min:  3Y +2x2   +4Z +7x4 +8X5 
row1:5Y +2x2       +3X4      >= 9
row2:3Y + X2    +Z      +5X5 >= 12
Vin1:6Y +3.0x2 +4Z +5X4      <= 124
vin2: Y +3x2       +3X4 +6X5 <= 854
-1 <= x2 <= 6
 1 <=  z <= .

A differenza della formulazione dell'esempio 1.6 in questo caso ad ogni vincolo abbiamo anche associato una etichetta (nome del vincolo) che si inserisce anteponendo ad ogni vincolo un nome seguito da due punti. E' importante sottolineare che sui limiti di tipo upper e lower bound (ad esempio +3<=x<=+6) l'etichetta non va assolutamente inserita.


import it.ssc.log.SscLogger;
import it.ssc.pl.milp.*;
import java.util.ArrayList;
import java.util.Random;

public class Esempio {
	
 public static void main(String[] args) throws Exception {
 
        LP lp = new LP("C:\\ssc_project\\ssc\\dati_testo\\pl_proble.txt");
        SolutionType solution_type=lp.resolve();
         
        if(solution_type==SolutionType.OPTIMUM) {
            Solution soluzione=lp.getSolution();
            for(Variable var:soluzione.getVariables()) {
                SscLogger.log("Nome variabile :"+var.getName() + " valore :"+var.getValue());
            }
            for(SolutionConstraint sol_constraint: soluzione.getSolutionConstraint()) {
                SscLogger.log("Vincolo "+sol_constraint.getName()+" : valore="+sol_constraint.getValue() + 
                              "[ "+sol_constraint.getRel()+"  "+sol_constraint.getRhs()+" ]" );
            }
            SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
        }
    }
}

Esempio 1.12

Si consideri il seguente problema di LP identico all'esempio 1.9:

	 max  X₁ +   3X₂
	 
	      X₁ +    X₂ ≥ 1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ +   3X₂ = 5
   	    
   	 con -1 ≤ X₁ ≤ +1
   	     -∞ ≤ X₂ ≤ +∞

In questo esempio vogliamo recuperare il problema, formulato nel formato sparso, da un file di testo chiamato sparse_problem.txt contenete il seguente listato:


  MAX     .    costo      .   
  GE      .    row1       .    
  LE      .    row2       .   
  EQ      .    row3       .   
  UPPER   .    lim_sup    .   
  LOWER   .    lim_inf    .        
  .      X1    costo      1   
  .      X1    row1       1    
  .      X1    row2       1   
  .      X1    row3      -5   
  .      X1    lim_sup    1   
  .      X1    lim_inf   -1          
  .      X2    costo      3   
  .      X2    row1       1    
  .      X2    row2     1.4   
  .      X2    row3       3   
  .      X2    lim_sup    .   
  .      X2    lim_inf    .         
  .      RHS   row1       1    
  .      RHS   row2       6   
  .      RHS   row3       5

E' da notare che nel costruttore della classe LP viene passato come argomento un oggetto di tipo InputFile che fa riferimento al file contenente il problema.

import it.ssc.log.SscLogger;
import it.ssc.pl.milp.FormatTypeInput.FormatType;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputFile;

public class Esempio {
     
    public static void main(String[] args) throws Exception {
         
        InputFile input_sparse = new InputFile("C:/ssc_project/sparse_problem.txt");
       	input_sparse.setInputFormat("TYPE:varstring(5), COL_:varstring(3) , ROW_:varstring(7), COEF:double"); 
        LP lp = new LP(input_sparse,FormatType.SPARSE);  
        SolutionType solution_type=lp.resolve();
            
        if(solution_type==SolutionType.OPTIMUM) { 
            Solution solution=lp.getSolution();
            for(Variable var:solution.getVariables()) {
                SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
            }
            SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
        }   
       
    }
}

Esempio 1.13

Nell'esempio sottostante si riporta un problema di LP generato con numeri pseudocausali, con la particolarità che al vettore b vengono fatti assumere valori dell'ordine di decine di milioni. La conseguenza di lavorare con numeri di elevata grandezza potrebbe non far convergere la fase 1 del simplesso. In questo particolare caso se non si modifica la tolleranza ε del valore ottimo z della f.o relativo alla fase 1 la risoluzione del problema potrebbe non dare come risultato soluzioni ammissibili. In altre parole, alla fine della fase 1, se | z | > ε allora il problema non ammette soluzioni. Per ovviare a questo, nell'esempio riportato, la tolleranza viene aumentata da 1E-8 (valore di default) a 1E-5 [rigo 31] per far si che , a causa della manipolazione di numeri di grandezza elevata, possa avvenire che | z | < ε.


import it.ssc.log.SscLogger;
import it.ssc.pl.milp.*;
import java.util.ArrayList;
import java.util.Random;
 
public class Esempio {
    public static void main(String arg[]) throws Exception {
         
        final int M = 445;  // rows
        final int N = 345;  // cols
         
        Random random = new Random();
         
        double[] c = new double[N];
        double[] b = new double[M];
        double[][] A = new double[M][N];
        for (int j = 0; j < N; j++)      c[j] = (double) (random.nextInt(20));
        for (int i = 0; i < M; i++)      b[i] = (double) random.nextInt(100000000);
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++)  A[i][j] = (double) random.nextInt(10);
                 
 
        LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
 
        ArrayList< Constraint > constraints = new ArrayList< Constraint >();
        for(int i=0; i < A.length; i++) {
            constraints.add(new Constraint(A[i], ConsType.LE, b[i])); 
        }
        
        LP lp = new LP(f,constraints);
        lp.setCEpsilon(EPSILON._1E_M5);
        SolutionType solution_type=lp.resolve();
 
        if(solution_type==SolutionType.OPTIMUM) { 
            Solution solution=lp.getSolution();
            for(Variable var:solution.getVariables()) {
                SscLogger.log("Nome variabile :"+var.getName() + " value:"+var.getValue());
            }
            SscLogger.log("Valore f.o. :"+solution.getOptimumValue());  
        }
        else SscLogger.log("Soluzione non ottima. Tipo di soluzione:"+solution_type);
    }
}

Esempio 1.14

Si consideri il seguente problema di LP:

	 max  X₁ +   3X₂
	 
	      X₁ +    X₂ ≥-1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ +   3X₂ = 5
   	    
   	 con X₁, X₂ ≥ 0

Per risolvere questo problema (identico al problema 1.1) con una implementazione del simplesso parallelo, occorre semplicemente aggiungere l'istruzione presente nel rigo 24. Con questa istruzione specifichiamo il numero di thread da utilizare per eseguire una istanza del simplesso parallelo (in questo caso 4). Tra i valori selezionabili vi è anche il valore LPThreadsNumber.AUTO, con il quale si delega al sistema la scelta del numero di thread da utilizzare per l'esecuzione del simplesso parallelo. Occorre ricordare che vantaggi sulla durata del metodo si ottengono con almeno 4 o più core fisici e che ha senso utilizzare questa tecnica solo se il problema presenta un numero di variabili/vincoli dell'ordine dei migliaia.


import it.ssc.log.SscLogger;
import it.ssc.pl.milp.LP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;
import it.ssc.pl.milp.util.LPThreadsNumber;

public class Esempio {
	
	public static void main(String[] args) throws Exception {

		String lp_string = 
			                " 1    3    max      .    \n" +  
			                " 1    1    ge      -1    \n" +	  
			                " 1  1.4    le       6    \n" +  
			                "-5    3    eq       5";
			

		InputString lp_input = new InputString(lp_string); 
		lp_input.setInputFormat("X1:double, X2:double, TYPE:varstring(3), RHS:double"); 

		LP lp = new LP(lp_input); 
		lp.setThreadsNumber(LPThreadsNumber.N_4);
		SolutionType solution_type=lp.resolve();
		
		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=lp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
		else SscLogger.log("Soluzione non ottima:"+solution_type);
	}
}

Example 2.1

Consideriamo il seguente problema di programmazione lineare misto-intera (MILP) :

	
   	 min  3X₁ +  X₂ + 4X₃ + 7X₄ + 8X₅
   	 
   	      5X₁ + 2X₂      + 3X₄       ≤   9
   	      3X₁ +  X₂ +  X₃      + 5X₅  ≥  12
   	      6X₁ + 3X₂ + 4X₃ + 5X₄       ≥ 124
   	      1X₁ + 3X₂      + 3X₄ + 6X₅  ≥ 854
   	      
   	 con X₂, X₃, X₄, X₅ ∈ ℤ 
   	     1 ≤ X₂ ≤ +6
   	     1 ≤ X₃ ≤ +∞     
   	     X₁, X₄, X₅ ≥ 0

Questo problema presenta le variabili X₂, X₃, X₄, X₅ intere, mentre la variabile X₁ non lo è. In SSC per risolvere un problema di MILP occorre semplicemente introdurre nel formato a coefficienti un rigo aggiuntivo [rigo 20] per dichiarare le variabili intere. Ponendo 1 sul rigo degli "integer" si dichiara la relativa variabile come intera.

Altra differenza è che in questo caso va instanziato l'oggetto MILP [rigo 25] e non l'oggetto LP.



import it.ssc.log.SscLogger;
import it.ssc.pl.milp.MILP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;

public class Esempio {
	public static void main(String[] args) throws Exception {

		String milp_string=
				
						"3 1 4 7 8 min      . "  +"\n"+
						"5 2 0 3 0 le       9 "  +"\n"+
						"3 1 1 0 5 ge       12"  +"\n"+
						"6 3 4 5 0 ge       124" +"\n"+
						"1 3 0 3 6 ge       854" +"\n"+
						"0 1 1 0 0 lower    . "  +"\n"+
						". 6 . . . upper    . "  +"\n"+
						"0 1 1 1 1 integer  . "  +"\n" ;  

		InputString milp_input = new InputString(milp_string);
		milp_input.setInputFormat("X1-X5:double, TYPE:varstring(20),  RHS:double");

		MILP milp=new MILP(milp_input);
		SolutionType solution_type= milp.resolve();

		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=milp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
	}
}

Esempio 2.2

Si consideri il seguente problema di MILP dato da:

	 max  X₁ + 3.0X₂
	 
	      X₁ +    X₂ ≥ 1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ + 3.0X₂ ≤ 5
   	    
   	 con  X₁, X₂ ≥ 0
   	      X₁, X₂ ∈ ℤ

Vogliamo risolvere questo problema di programmazione lineare intera utilizzando la notazione matriciale. Per far ciò basta aggiungere alla matrice A dei coefficienti un rigo per esprimere quali sono le variabili intere [rigo 21]. Con il valore 1 si dichiara la variabile intera, con lo 0 la si considera non intera. Occorre anche dichiarare a SSC che l'ulteriore rigo inserito in A non è relativo ai vincoli di tipo GE, LE ,EQ , ma alla dichiarazione delle variabili intere; ciò si realizza aggiungendo al vettore che esprime il tipo di vincolo (array rel[]) il valore ConsType.INT [rigo 26]. Infine occorre aggiungere al vettore b un valore NaN [rigo 23], per adeguare la dimensione di A con quella di b in quanto la dimensione di b deve coincidere con il numero di righi della matrice A.


import it.ssc.log.SscLogger;
import it.ssc.pl.milp.ConsType;
import it.ssc.pl.milp.Constraint;
import it.ssc.pl.milp.GoalType;
import it.ssc.pl.milp.LinearObjectiveFunction;
import it.ssc.pl.milp.MILP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import static it.ssc.pl.milp.LP.NaN;
import java.util.ArrayList;

public class Esempio {
	
	public static void main(String[] args) throws Exception {

		double A[][]={ 
				{ 1.0 , 1.0 },
				{ 1.0 , 1.4 },
				{-5.0 , 3.0 }, 
				{ 1.0 , 1.0 },  //rigo della matrice per la definizione degli integer
				} ;
		double b[]= { 1.0, 6.0 ,5.0, NaN};
		double c[]= { 1.0, 3.0  };	

		ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.LE, ConsType.INT};

		LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);

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

		MILP lp = new MILP(f,constraints); 
		SolutionType solution_type=lp.resolve();

		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=lp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
	}
}

Esempio 2.3

Si consideri il seguente problema di MILP :

	 max  Y₁ + 3.0Y₂
	 
	      Y₁ +    Y₂ ≥ 1
   	      Y₁ + 1.4Y₂ ≤ 6
   	    -5Y₁ + 3.0Y₂ = 5
   	    
   	 con  Y₂ ∈ ℤ
   	     -1 ≤ Y₁ ≤ +1
   	     -∞ ≤ Y₂ ≤ +∞

Vogliamo risolvere questo problema di programmazione lineare misto intera utilizzando la notazione sparsa. Per indicare che la variabile Y₂ è intera basta aggiungere nella colonna dei ROW_ un valore per indicare quale sarà il marcatore che le definisce. Questo marcatore (da noi chiamato "var_int", ma può avere qualsiasi altro nome) deve avere associato un TYPE di tipo INTEGER [rigo 23].

Una volta definito il marcatore che definisce le variabili intere, basta dichiarare [rigo 38] che la variabile Y₂ è di tipo var_int (ovvero INTEGER) ponendo nella colona dei COEF il valore 1. Se al contrario una variabile non è intera si deve valorizzare la colonna COEF con lo 0 o, più brevemente, tralasciare l'intera dichiarazione. Difatti, nella formulazione sottostante, la variabile Y₁ non è intera e quindi non è necessario esprimere la mancata associazione tra la variabile e il marcatore var_int ponendo il valore 0 in COEF.


import it.ssc.log.SscLogger;
import it.ssc.pl.milp.FormatTypeInput.FormatType;
import it.ssc.pl.milp.MILP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;

public class Esempio {
	public static void main(String[] args) throws Exception {

		String lp_sparse = 
		
		
			//    TYPE   COL_   ROW_    COEF 
				 
				" MAX     .    costo      .    \n" +   
                " GE      .    row1       .    \n" +	  
                " LE      .    row2       .    \n" +  
                " EQ      .    row3       .    \n" +
                " UPPER   .    lim_sup    .    \n" +
                " LOWER   .    lim_inf    .    \n" +    
                " INTEGER .    var_int    .    \n" +  
		
				" .      Y1    costo      1    \n" +
				" .      Y1    row1       1    \n" +	  
		        " .      Y1    row2       1    \n" +  
		        " .      Y1    row3      -5    \n" +
		        " .      Y1    lim_sup    1    \n" +
		        " .      Y1    lim_inf   -1    \n" +		       
				 
				" .      Y2    costo      3    \n" +
				" .      Y2    row1       1    \n" +	  
		        " .      Y2    row2     1.4    \n" +  
		        " .      Y2    row3       3    \n" +
		        " .      Y2    lim_sup    .    \n" +
		        " .      Y2    lim_inf    .    \n" +	
		        " .      Y2    var_int    1    \n" +
		         
				" .     RHS    row1       1    \n" +	  
				" .     RHS    row2       6    \n" +  
				" .     RHS    row3       5    \n"   ;
			

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

		MILP lp = new MILP(lp_input,FormatType.SPARSE); 
		SolutionType solution_type=lp.resolve();
		
		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=lp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
	}
}

Esempio 2.4

Si consideri il seguente problema di programmazione lineare misto intera (MILP) con alcune variabili binarie:

	
   	 min  3K₁ +  K₂ + 4K₃ + 7K₄ + 8K₅
   	 
   	      5K₁ + 2K₂      + 3K₄       ≤   9
   	      3K₁ +  K₂ +  K₃      + 5K₅  ≥  12
   	      6K₁ + 3K₂ + 4K₃ + 5K₄       ≥ 124
   	      1K₁ + 3K₂      + 3K₄ + 6K₅  ≥ 854 
   	      
   	 con K₂, K₅ ∈ ℤ 
   	     K₁, K₄ ∈ {0,1}
   	     1 ≤ K₂ ≤ +6
   	     1 ≤ K₃ ≤ +∞     
   	     con K₁, K₄, K₅ ≥ 0

Questo problema presenta variabili intere e binarie, mentre la variabile K₃ non è soggetta a nessun vincolo di interezza. Per dichiarare una variabile binaria basta aggiungere un rigo avente TYPE "binary" [rigo 22]. Se la i-esima variabile è binaria basta porre 1 nel corrispondente rigo dei binary. Si rammenta che una variabile non può essere definita contemporaneamente sia binaria che intera. Nel nostro caso le variabili K₁ e K₄ sono binarie mentre le variabili K₂ e K₅ sono intere.



import it.ssc.log.SscLogger;
import it.ssc.pl.milp.MILP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;

public class Esempio {

	public static void main(String[] args) throws Exception {

		String milp_string=

						"3 1 4 7 8 min      . "  +"\n"+
						"5 2 0 3 0 le       9 "  +"\n"+
						"3 1 1 0 5 ge       12"  +"\n"+
						"6 3 4 5 0 ge       124" +"\n"+
						"1 3 0 3 6 ge       854" +"\n"+
						"0 1 1 0 0 lower    . "  +"\n"+
						". 6 . . . upper    . "  +"\n"+
						"0 1 0 0 1 integer  . "  +"\n"+
						"1 0 0 1 0 binary   . "  +"\n";  

		InputString milp_input = new InputString(milp_string);
		milp_input.setInputFormat("K1-K5:double, TYPE:varstring(20),  RHS:double");

		MILP milp=new MILP(milp_input);
		SolutionType solution_type= milp.resolve();

		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=milp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
	}
}

Esempio 2.5

Si consideri il seguente problema di MILP dato da:

	 max  X₁ + 3.0X₂
	 
	      X₁ +    X₂ ≥ 1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ + 3.0X₂ ≤ 5
   	    
   	 con  X₁, X₂ ≥ 0
   	      X₁ ∈ ℤ 
   	      X₂ ∈ {0,1}

Vogliamo risolvere questo problema di programmazione lineare intera, che presenta anche variabili binarie, utilizzando la notazione matriciale. In questa notazione, per rappresentare le variabili binarie, basta aggiungere alla matrice A dei coefficienti un rigo per dichiararle [rigo 15]. Con il valore 1 si dichiara la variabile binaria, con lo 0 la si considera non binaria. Va anche aggiunto il valore ConsType.BIN [rigo 20] per dichiarare che l'ultimo rigo della matrice A è relativo alla definizione delle variabili binarie.

import static it.ssc.pl.milp.LP.NaN;			
import it.ssc.log.SscLogger;
import it.ssc.pl.milp.*;
import java.util.ArrayList;

public class Esempio {
	
	public static void main(String[] args) throws Exception {

		double A[][]={ 
				{ 1.0 , 1.0 },
				{ 1.0 , 1.4 },
				{-5.0 , 3.0 }, 
				{ 1.0 , 0.0 },  //definizione degli integer
				{ 0.0 , 1.0 },  //definizione dei binary
				} ;
		double b[]= { 1.0, 6.0 ,5.0, NaN, NaN};
		double c[]= { 1.0, 3.0  };	

		ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.LE, ConsType.INT , ConsType.BIN};

		LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);

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

		MILP lp = new MILP(f,constraints); 
		SolutionType solution_type=lp.resolve();

		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=lp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
	}
}

Esempio 2.6

Si consideri il seguente problema di MILP :

	 max  Y₁ + 3.0Y₂
	 
	      Y₁ +    Y₂ ≥ 1
   	      Y₁ + 1.4Y₂ ≤ 6
   	    -5Y₁ + 3.0Y₂ ≤ 5
   	    
   	 con  Y₁ ∈ {0,1}  
   	      Y₂ ∈ ℤ
   	     -1 ≤ Y₁ ≤ +1
   	     -∞ ≤ Y₂ ≤ +∞

Vogliamo risolvere questo problema di programmazione lineare misto intera, che presenta anche variabili binarie, utilizzando la notazione sparsa. Per indicare che la variabile Y₁ è binaria basta aggiungere nella colonna dei ROW_ il marcatore che le definisce. Questo marcatore (da noi chiamato "var_bin" , ma che può avere qualsiasi altro nome) deve avere associato un TYPE di tipo BINARY [rigo 24].

Una volta definito il marcatore delle variabili binarie, basta dichiarare [rigo 32] che la variabile Y₁ è di tipo var_bin (ovvero BINARY) ponendo nella colonna dei COEF il valore 1.


import it.ssc.log.SscLogger;
import it.ssc.pl.milp.FormatTypeInput.FormatType;
import it.ssc.pl.milp.MILP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;

public class Esempio {
	
	public static void main(String[] args) throws Exception {
	
		String lp_sparse = 
		
			//    TYPE   COL_   ROW_    COEF 
				 
				" MAX     .    costo      .    \n" +   
                " GE      .    row1       .    \n" +	  
                " LE      .    row2       .    \n" +  
                " LE      .    row3       .    \n" +
                " UPPER   .    lim_sup    .    \n" +
                " LOWER   .    lim_inf    .    \n" +    
                " INTEGER .    var_int    .    \n" + 
                " BINARY  .    var_bin    .    \n" + 
		
				" .      Y1    costo      1    \n" +
				" .      Y1    row1       1    \n" +	  
		        " .      Y1    row2       1    \n" +  
		        " .      Y1    row3      -5    \n" +
		        " .      Y1    lim_sup    1    \n" +
		        " .      Y1    lim_inf   -1    \n" +	
		        " .      Y1    var_bin    1    \n" +	
				 
				" .      Y2    costo      3    \n" +
				" .      Y2    row1       1    \n" +	  
		        " .      Y2    row2     1.4    \n" +  
		        " .      Y2    row3       3    \n" +
		        " .      Y2    lim_sup    .    \n" +
		        " .      Y2    lim_inf    .    \n" +	
		        " .      Y2    var_int    1    \n" +
		         
				" .     RHS    row1       1    \n" +	  
				" .     RHS    row2       6    \n" +  
				" .     RHS    row3       5    \n"   ;
			

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

		MILP milp = new MILP(lp_input,FormatType.SPARSE);  
		SolutionType solution_type=milp.resolve();
		
		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=milp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
	}
}

Esempio 2.7

Si consideri il seguente problema di LP :

	
   	 min  3X₁ +  X₂ + 4X₃ + 7X₄ + 8X₅
   	 
   	      5X₁ + 2X₂      + 3X₄       ≥    9
   	      3X₁ +  X₂ +  X₃      + 5X₅  ≥ 12.5
   	      6X₁ + 3X₂ + 4X₃ + 5X₄       ≤  124
   	       X₁ + 3X₂      + 3X₄ + 6X₅  ≤  854
   	      
   	 con X₁, X₂, X₃, X₄, X₅ ≥ 0
   	     X₂, X₃ ∈ ℤ

Vogliamo risolvere questo problema di programmazione lineare misto intera usando il formato di rappresentazione a disequazioni. In questo formato per aggiungere il vincolo di interezza sulle variabili X₂ e X₃ basta aggiungere un rigo [rigo 16]. Nel caso in cui si vogliano definire variabili binare o semicontinue, la sintassi è uguale a quella della dichiarazione degli interi, ovvero si antepone la parola chiave "bin" o "sec" e si fa seguire una lista di variabili separate da virgola.


import java.util.ArrayList;
import it.ssc.log.SscLogger;
import it.ssc.pl.milp.*;

public class Esempio {
	
	public static void main(String[] args) throws Exception {
		
		ArrayList< String > constraints = new ArrayList< String >();
		
		constraints.add("min:  3x1 +X2 +4x3 +7x4 +8X5 "); 
        constraints.add("5x1 +2x2 +3X4       >= 9");
        constraints.add("3x1 + X2 +X3 +5X5   >= 12.5");
        constraints.add("6X1+3.0x2 +4X3 +5X4 <= 124");
        constraints.add(" X1 + 3x2 +3X4 +6X5 <= 854");
        constraints.add(" int x2, X3 ");
			
		MILP milp = new MILP(constraints); 
		SolutionType solution_type=milp.resolve();
		
		if(solution_type==SolutionType.OPTIMUM) {
			Solution soluzione=milp.getSolution();
			for(Variable var:soluzione.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore :"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
		}
	}
}

Esempio 2.8

Si consideri il problema di programmazione lineare intera riportato nella sezione sottostante. In questo esempio si confronta la soluzione ottima finale intera con quella ottenuta dal suo rilassamento (i valori del problema rilassato sono riportati tra parentesi quadre [righi 46-49])


import it.ssc.context.exception.InvalidSessionException;
import it.ssc.log.SscLogger;
import it.ssc.pl.milp.*;
import java.util.ArrayList;
import static it.ssc.pl.milp.LP.NaN;

public class Esempio {
	
	public static void main(String arg[]) throws InvalidSessionException, Exception {

		double[]   c =  { 2, 2, 2, 2, 2 ,2, 2, 2, 2, 2,2 ,2 ,2 };
		double[]   b =  {1000, 1234, 1000, 1000, 1000, 1000, 1000, 1000, 1000};
		
		double[][] A ={	{ 2., 9. ,7. ,5. ,9. ,6. ,3., 7., 8. ,7. ,5. ,3. ,1. },
						{ 4. ,1. ,2. ,3. ,6. ,4. ,5. ,2. ,8. ,5. ,3. ,4., 7. },
						{ 3. ,4. ,2. ,5. ,7. ,6. ,3. ,5. ,7. ,4. ,6. ,8. ,6. },
						{ 4. ,6. ,9. ,8. ,7. ,6. ,5. ,4. ,3. ,2. ,3. ,5. ,6. },
						{ 4. ,4. ,7. ,5. ,3. ,8. ,5. ,6. ,3. ,5. ,6. ,4. ,6. },
						{ 2. ,6. ,4. ,5. ,7. ,5. ,6. ,4. ,6. ,7. ,4. ,4. ,6. },
						{ 4. ,6. ,9. ,8. ,3. ,6. ,5. ,5. ,3. ,2. ,9. ,5. ,6. },
						{ 4. ,5. ,7. ,8. ,3. ,8. ,3. ,6. ,3. ,5. ,6. ,1. ,6. },
						{ 2., 2., 4., 3., 7. ,5. ,9. ,4. ,6. ,7. ,8. ,4., 6. }};

		double[] upper ={ 190.5, NaN, NaN, NaN, NaN ,NaN ,NaN ,NaN ,35.0 ,NaN ,NaN ,NaN, NaN };
		double[] integer ={ 1.0, 1.0, 1.0, 1.0, 1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0, 1.0 };

		LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);

		ArrayList< Constraint > constraints = new ArrayList< Constraint >();
		for(int i=0; i< A.length; i++) {
			constraints.add(new Constraint(A[i], ConsType.LE, b[i])); 
		}

		constraints.add(new Constraint(upper,   ConsType.UPPER, NaN)); 
		constraints.add(new Constraint(integer, ConsType.INT , NaN)); 

		MILP milp = new MILP(f,constraints);
		SolutionType solution=milp.resolve();

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

Esempio 2.9

Si consideri il seguente problema di MILP :

	
   	 min  3X₁ +  X₂ + 4X₃ + 7X₄ + 8X₅
   	 
   	      5X₁ + 2X₂      + 3X₄       ≥    9
   	      3X₁ +  X₂ +  X₃      + 5X₅  ≥ 12.5
   	      6X₁ + 3X₂ + 4X₃ + 5X₄       ≤  124
   	       X₁ + 3X₂      + 3X₄ + 6X₅  ≤  854
   	      
   	 con X₁, X₂, X₃, X₄, X₅ ≥ 0
   	     X₂, X₃ ∈ ℤ

Questo problema è identico al problema 2.7. Nel codice per la sua risoluzione sono state aggiunti dei righi per recuperare il valore che la parte LHS di ogni vincolo (la parte alla sinistra della relazione) assume valorizzando le variabili incognite con la soluzione ottima. Il valore LHS viene poi confrontato con il corrispettivo valore RHS. [righi 32-35]. Ai vincoli si può dare un nome, basta anteporre il nome al vincolo, facendolo seguire dai due punti (nome:vincolo). Occorre ricordare che nel caso della definizione degli upper e lower bound le etichette non vanno assolutamente inserite (esempio 1.11).

import java.util.ArrayList;
import it.ssc.log.SscLogger;
import it.ssc.pl.milp.*;


public class Esempio {

	public static void main(String[] args) throws Exception {

		
		ArrayList< String > constraints = new ArrayList< String >();
         
        constraints.add("min:  3x1 +X2 +4x3 +7x4 +8X5 "); 
        constraints.add("5x1 +2x2 +3X4       >= 9");
        constraints.add("3x1 + X2 +X3 +5X5   >= 12.5");
        constraints.add("6X1+3.0x2 +4X3 +5X4 <= 124");
        constraints.add(" X1 + 3x2 +3X4 +6X5 <= 854");
        constraints.add(" int x2, X3 ");
	
		MILP milp = new MILP(constraints); 
		SolutionType solution_type=milp.resolve();

		if(solution_type==SolutionType.OPTIMUM) {
			Solution soluzione=milp.getSolution();
			for(Variable var:soluzione.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore :"+var.getValue());
			}
			for(SolutionConstraint sol_constraint: soluzione.getSolutionConstraint()) {
				SscLogger.log("Vincolo "+sol_constraint.getName()+" : valore="+sol_constraint.getValue() + 
						      "[ "+sol_constraint.getRel()+"  "+sol_constraint.getRhs()+" ]" );
			}
			SscLogger.log("Valore ottimo:"+soluzione.getOptimumValue());
		}
	}
}

Esempio 2.10

Si consideri il seguente problema di programmazione lineare misto intera (MILP) che presenta anche una variabile semicontinua:

	
   	 min  3K₁ +  K₂ + 4K₃ + 7K₄ + 8K₅
   	 
   	      5K₁ + 2K₂      + 3K₄       ≤   9
   	      3K₁ +  K₂ +  K₃      + 5K₅  ≥  12
   	      6K₁ + 3K₂ + 4K₃ + 5K₄       ≥ 124
   	      1K₁ + 3K₂      + 3K₄ + 6K₅  ≥ 854 
   	      
   	 con K₂, K₅ ∈ ℤ 
   	     K₁, K₄ ∈ {0,1}
   	     1 ≤ K₂ ≤ 6 oppure K₂ =0
   	     1 ≤ K₃ ≤ +∞     
   	     con K₁, K₄, K₅ ≥ 0

Questo problema è identico al problema 2.4 con l'aggiunta della condizione che la variabile K₂ è semicontinua, ovvero essa non è strettamente vincolata ad essere compresa tra i valori di upper e lower, ma può anche assumere il valore 0.



import it.ssc.log.SscLogger;
import it.ssc.pl.milp.MILP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;

public class Esempio {

	public static void main(String[] args) throws Exception {

		String milp_string=

						"3 1 4 7 8 min      . "  +"\n"+
						"5 2 0 3 0 le       9 "  +"\n"+
						"3 1 1 0 5 ge       12"  +"\n"+
						"6 3 4 5 0 ge       124" +"\n"+
						"1 3 0 3 6 ge       854" +"\n"+
						"0 1 1 0 0 lower    . "  +"\n"+
						". 6 . . . upper    . "  +"\n"+
						"0 1 0 0 1 integer  . "  +"\n"+
						"1 0 0 1 0 binary   . "  +"\n"+
                        "0 1 0 0 0 semicont . "  +"\n"; 

		InputString milp_input = new InputString(milp_string);
		milp_input.setInputFormat("K1-K5:double, TYPE:varstring(20),  RHS:double");

		MILP milp=new MILP(milp_input);
		SolutionType solution_type= milp.resolve();

		if(solution_type==SolutionType.OPTIMUM) { 
			Solution solution=milp.getSolution();
			for(Variable var:solution.getVariables()) {
				SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
			}
			SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
		}	
	}
}

Esempio 2.11

Si consideri il seguente problema di MILP dato da:

	 max  -X₁ + 3.0X₂
	 
	      X₁ +    X₂ ≥ 1
   	      X₁ + 1.4X₂ ≤ 6
   	    -5X₁ + 3.0X₂ ≤ 5
   	    
   	 con  X₁, X₂ ≥ 0
   	      X₁ ∈ ℤ 
   	      X₂ ∈ {0,1}
   	      1 ≤ X₁ ≤ 3 oppure X₁ =0

Vogliamo risolvere questo problema di programmazione lineare intera, che presenta anche una variabile semicontinua intera, utilizzando la notazione matriciale.

				
import static it.ssc.pl.milp.LP.NaN;
import it.ssc.log.SscLogger;
import it.ssc.pl.milp.*;
import java.util.ArrayList;
 
public class Esempio {
     
    public static void main(String[] args) throws Exception {
 
        double A[][]={ 
                { 1.0 , 1.0 },
                { 1.0 , 1.4 },
                {-5.0 , 3.0 }, 
                { 1.0 , 0.0 },  //definizione degli integer
                { 0.0 , 1.0 },  //definizione dei binary
                { 1.0 , 0.0 },  //definizione dei semicontinuous
                { 3.0 , NaN},   //definizione dei upper
                { 1.0 , 0.0 },  //definizione dei lower
                } ;
        double b[]= { 1.0, 6.0 ,5.0, NaN, NaN, NaN, NaN, NaN};
        double c[]= { -1.0, 3.0  };  
 
        ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.LE, ConsType.INT, ConsType.BIN,
        		         ConsType.SEMICONT, ConsType.UPPER, ConsType.LOWER};
 
        LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
 
        ArrayList< Constraint > constraints = new ArrayList< Constraint >();
        for(int i=0; i < A.length; i++) {
            constraints.add(new Constraint(A[i], rel[i], b[i]));
        }
 
        MILP lp = new MILP(f,constraints); 
        SolutionType solution_type=lp.resolve();
 
        if(solution_type==SolutionType.OPTIMUM) { 
            Solution solution=lp.getSolution();
            for(Variable var:solution.getVariables()) {
                SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
            }
            SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
        }   
    }
}

Esempio 2.12

Si consideri il seguente problema di MILP :

	 max  Y₁ - 3.0Y₂
	 
	      Y₁ +    Y₂ ≥ 1
   	      Y₁ + 1.4Y₂ ≤ 6
   	    -5Y₁ + 3.0Y₂ ≤ 5
   	    
   	 con  Y₁ ∈ {0,1}  
   	      Y₂ ∈ ℤ
   	     -1 ≤ Y₁ ≤ +1
   	      1 ≤ Y₂ ≤ +∞  oppure Y₂ = 0

Vogliamo risolvere questo problema di programmazione lineare misto intera, che presenta anche variabili semicontinue, utilizzando la notazione sparsa.



import it.ssc.log.SscLogger;
import it.ssc.pl.milp.FormatTypeInput.FormatType;
import it.ssc.pl.milp.MILP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;
 
public class Esempio {
     
    public static void main(String[] args) throws Exception {
     
        String lp_sparse = 
         
            //    TYPE   COL_   ROW_    COEF 
                  
                " MAX     .    costo      .    \n" +   
                " GE      .    row1       .    \n" +      
                " LE      .    row2       .    \n" +  
                " LE      .    row3       .    \n" +
                " UPPER   .    lim_sup    .    \n" +
                " LOWER   .    lim_inf    .    \n" +    
                " INTEGER .    var_int    .    \n" + 
                " BINARY  .    var_bin    .    \n" + 
                " SEMICONT .   var_sc     .    \n" + 
         
                " .      Y1    costo      1    \n" +
                " .      Y1    row1       1    \n" +      
                " .      Y1    row2       1    \n" +  
                " .      Y1    row3      -5    \n" +
                " .      Y1    lim_sup    1    \n" +
                " .      Y1    lim_inf   -1    \n" +    
                " .      Y1    var_bin    1    \n" +    
                  
                " .      Y2    costo     -3    \n" +
                " .      Y2    row1       1    \n" +      
                " .      Y2    row2     1.4    \n" +  
                " .      Y2    row3       3    \n" +
                " .      Y2    lim_sup    .    \n" +
                " .      Y2    lim_inf    1    \n" +    
                " .      Y2    var_int    1    \n" +
                " .      Y2    var_sc     1    \n" +
                  
                " .     RHS    row1       1    \n" +      
                " .     RHS    row2       6    \n" +  
                " .     RHS    row3       5    \n"   ;
             
 
        InputString lp_input = new InputString(lp_sparse); 
        lp_input.setInputFormat("TYPE:varstring(8), COL_:varstring(3) , ROW_:varstring(7), COEF:double"); 
 
        MILP milp = new MILP(lp_input,FormatType.SPARSE);  
        SolutionType solution_type=milp.resolve();
         
        if(solution_type==SolutionType.OPTIMUM) { 
            Solution solution=milp.getSolution();
            for(Variable var:solution.getVariables()) {
                SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
            }
            SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
        }   
    }
}

Esempio 2.13

Si consideri il problema di programmazione lineare intera riportato nella sezione sottostante . Vogliamo risolvere questo problema utilizzando un'implementazione del B&B parallelo. Per far questo basta aggiugere l'istruzione al rigo [39], con il quale si dichiara il numero di thread (in questo caso 4) da utilizzare per eseguire un B&B parallelo.



import it.ssc.context.exception.InvalidSessionException;
import it.ssc.log.SscLogger;
import it.ssc.pl.milp.*;
import it.ssc.pl.milp.util.MILPThreadsNumber;
import static it.ssc.pl.milp.LP.NaN; 
import java.util.ArrayList;
 
 
public class Esempio {
     
    public static void main(String arg[]) throws InvalidSessionException, Exception {
 
        double[]   c =  { 2, 2, 2, 2, 2 , 2, 2, 2, 2, 2, 2 ,2 , 2 };
        double[]   b =  {1000, 1234, 1000, 1000, 1000, 1000, 1000, 1000, 1000};
         
        double[][] A ={ { 2., 9. ,7. ,5. ,9. ,6. ,3., 7., 8. ,7. ,5. ,3. ,1. },
                        { 4. ,1. ,2. ,3. ,6. ,4. ,5. ,2. ,8. ,5. ,3. ,4., 7. },
                        { 3. ,4. ,2. ,5. ,7. ,6. ,3. ,5. ,7. ,4. ,6. ,8. ,6. },
                        { 4. ,6. ,9. ,8. ,7. ,6. ,5. ,4. ,3. ,2. ,3. ,5. ,6. },
                        { 4. ,4. ,7. ,5. ,3. ,8. ,5. ,6. ,3. ,5. ,6. ,4. ,6. },
                        { 2. ,6. ,4. ,5. ,7. ,5. ,6. ,4. ,6. ,7. ,4. ,4. ,6. },
                        { 4. ,6. ,9. ,8. ,3. ,6. ,5. ,5. ,3. ,2. ,9. ,5. ,6. },
                        { 4. ,5. ,7. ,8. ,3. ,8. ,3. ,6. ,3. ,5. ,6. ,1. ,6. },
                        { 2., 2., 4., 3., 7. ,5. ,9. ,4. ,6. ,7. ,8. ,4., 6. }};
 
         
        double[] integer ={ 1.0, 1.0, 1.0, 1.0, 1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0, 1.0 };
 
        LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
 
        ArrayList< Constraint > constraints = new ArrayList< Constraint >();
        for(int i=0; i< A.length; i++) {
            constraints.add(new Constraint(A[i], ConsType.LE, b[i])); 
        }
 
        constraints.add(new Constraint(integer, ConsType.INT , NaN)); 
 
        MILP milp = new MILP(f,constraints);
        milp.setThreadNumber(MILPThreadsNumber.N_4);
        SolutionType solutionType=milp.resolve();
 
        if(solutionType==SolutionType.OPTIMUM) { 
            Solution solution=milp.getSolution();
            for(Variable var:solution.getVariables()) {
                SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
            }
            SscLogger.log("Valore ottimo:"+solution.getOptimumValue());
        }  
    }
}

Esempio 2.14

Se l'esigenza è quella di ottenere una soluzione ammissibile non necessariamente ottima , basta invocare il metodo setJustTakeFeasibleSolution() passandogli il valore "true" (rigo 24). Questa opzione permette di far eseguire il B&B im modo di ottenere una soluzione ammissibile . In questo caso il valore restituito da resolve() (se esiste una soluzione ammissibile) sarà SolutionType.FEASIBLE. Nel nostro esempio la soluzione ammissibile intera ottenuta (X₁=2,X₂=2) ha come valore sulla f.o. -6 , mentre la soluzione ottima (X₁=3,X₂=1) ha come valore -7.



import it.ssc.log.SscLogger;
import it.ssc.pl.milp.MILP;
import it.ssc.pl.milp.Solution;
import it.ssc.pl.milp.SolutionType;
import it.ssc.pl.milp.Variable;
import it.ssc.ref.InputString;
 
public class Esempio2_bix {
    public static void main(String[] args) throws Exception {
 
        String milp_string=
                 
                        "-2 -1   min        ."   +"\n"+
                        "-1 -1   ge        -5"   +"\n"+
                        "1  -1   ge         0"   +"\n"+
                        "-6 -2   ge       -21"   +"\n"+
                        "4   3  upper       ."   +"\n"+
                        "1   1  integer     ."   +"\n" ;  
 
        InputString milp_input = new InputString(milp_string);
        milp_input.setInputFormat("X1-X2:double, TYPE:varstring(20),  RHS:double");
 
        MILP milp=new MILP(milp_input);
        milp.setJustTakeFeasibleSolution(true);
        SolutionType solution_type= milp.resolve();
 
        if(solution_type==SolutionType.FEASIBLE) { 
            Solution solution=milp.getSolution();
            for(Variable var:solution.getVariables()) {
                SscLogger.log("Nome variabile :"+var.getName() + " valore:"+var.getValue());
            }
            SscLogger.log("Valore soluzione sulla f.o.:"+solution.getOptimumValue());
        }   
    }
}