Inizia a utilizzare OR-Tools per Java

Le sezioni seguenti ti aiuteranno a iniziare a utilizzare OR-Tools per Java:

Che cos'è un problema di ottimizzazione?

L'obiettivo dell'ottimizzazione è trovare la soluzione migliore a un problema tra un ampio insieme di possibili soluzioni. A volte sarai soddisfatto di trovare una soluzione attuabile; anche OR-Tools ti consente di farlo.

Di seguito è riportato un problema di ottimizzazione tipico. Supponiamo che una compagnia di spedizioni consegni i pacchi ai suoi clienti utilizzando un parco veicoli. Ogni giorno l'azienda deve assegnare i pacchi ai furgoni, quindi scegliere un percorso per ciascun furgone in cui consegnare i pacchi. Ogni possibile assegnazione di pacchi e percorsi ha un costo basato sulla distanza totale da percorrere dei camion ed eventualmente anche su altri fattori. Il problema è scegliere le assegnazioni di pacchetti e route a minor costo.

Come tutti i problemi di ottimizzazione, questo problema presenta i seguenti elementi:

  • L'obiettivo: la quantità da ottimizzare. Nell'esempio precedente, l'obiettivo è ridurre al minimo i costi. Per configurare un problema di ottimizzazione, devi definire una funzione che calcoli il valore dell'obiettivo per una possibile soluzione. Questa funzione è chiamata funzione con obiettivo. Nell'esempio precedente, la funzione obiettivo calcola il costo totale di qualsiasi assegnazione di pacchetti e route.

    Una soluzione ottimale è quella per cui il valore della funzione obiettivo è il migliore. ("Migliore" può essere un valore massimo o minimo).

  • I vincoli: restrizioni sull'insieme di possibili soluzioni, basate sui requisiti specifici del problema. Ad esempio, se la società di spedizione non può assegnare ai camion pacchi con un peso superiore a un determinato peso, viene imposto un vincolo alle soluzioni.

    Una soluzione attuabile è una soluzione che soddisfi tutti i vincoli specificati per il problema, senza necessariamente essere ottimale.

Il primo passo per risolvere un problema di ottimizzazione consiste nell'individuare l'obiettivo e i vincoli.

Risoluzione di un problema di ottimizzazione in Java

Successivamente, forniremo un esempio di problema di ottimizzazione e mostreremo come impostarlo e risolverlo in Java.

Esempio di ottimizzazione lineare

Una delle aree di ottimizzazione più antiche e utilizzate è l'ottimizzazione lineare (o programmazione lineare), in cui la funzione obiettivo e i vincoli possono essere scritti come espressioni lineari. Ecco un semplice esempio di questo tipo di problema.

Ingrandisci 3x + y in base ai seguenti vincoli:

  1. 0 ≤ x ≤ 1
  2. 0 ≤ y ≤ 2
  3. x + y ≤ 2

La funzione obiettivo in questo esempio è 3x + y. Sia la funzione obiettivo che i vincoli sono dati da espressioni lineari, il che rende questo un problema lineare.

Passaggi principali per la risoluzione del problema

Per ogni lingua, i passaggi di base per impostare e risolvere un problema sono gli stessi:

  1. Importa le librerie richieste,
  2. Dichiara il risolutore,
  3. Crea le variabili,
  4. Definisci i vincoli,
  5. Definire la funzione obiettivo,
  6. Richiama il risolutore e
  7. Visualizza i risultati.

Programma Java

Questa sezione illustra un programma Java che configura e risolve il problema.

La procedura è la seguente:

  • Importa le librerie richieste. 
    import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
  • Dichiara il risolutore. 
    // Create the linear solver with the GLOP backend.
MPSolver solver = MPSolver.createSolver("GLOP");
    MPSolver è un wrapper per la risoluzione di qualsiasi problema relativo alla programmazione lineare o alla programmazione con numeri interi misti.
  • Crea le variabili. 
    // Create the variables x and y.
MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

System.out.println("Number of variables = " + solver.numVariables());
  • Definisci i vincoli. I primi due vincoli, 0 ≤ x ≤ 1 e 0 ≤ y ≤ 2, sono già impostati dalle definizioni delle variabili. Il seguente codice definisce il vincolo x + y ≤ 2: 
    // Create a linear constraint, 0 <= x + y <= 2.
MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
ct.setCoefficient(x, 1);
ct.setCoefficient(y, 1);

System.out.println("Number of constraints = " + solver.numConstraints());
    Il metodo setCoefficient imposta i coefficienti di x e y nell'espressione del vincolo.
  • Definisci la funzione dello scopo. 
    // Create the objective function, 3 * x + y.
MPObjective objective = solver.objective();
objective.setCoefficient(x, 3);
objective.setCoefficient(y, 1);
objective.setMaximization();
    Il metodo setMaximization dichiara che si tratta di un problema di massimizzazione.
  • Richiama il risolutore e visualizza i risultati. 
    solver.solve();
System.out.println("Solution:");
System.out.println("Objective value = " + objective.value());
System.out.println("x = " + x.solutionValue());
System.out.println("y = " + y.solutionValue());

Completa il programma

Il programma completo è mostrato di seguito.

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");

    // Create the variables x and y.
    MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
    MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

    System.out.println("Number of variables = " + solver.numVariables());

    // Create a linear constraint, 0 <= x + y <= 2.
    MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
    ct.setCoefficient(x, 1);
    ct.setCoefficient(y, 1);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Create the objective function, 3 * x + y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 1);
    objective.setMaximization();

    solver.solve();

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());
  }

  private BasicExample() {}
}

Esecuzione del programma Java

Puoi eseguire il programma indicato sopra nel seguente modo:

  1. Copia e incolla il codice riportato sopra in un nuovo file e salvalo con il nome my_program.java.
  2. Apri una finestra di comando nel livello superiore della directory in cui hai installato OR-Tools e inserisci: 
    make run SOURCE=relative/path/to/my_program.java
    dove relative/path/to/ è il percorso della directory in cui hai salvato il programma.

Il programma restituisce i valori di x e y che massimizzano la funzione obiettivo:

Solution:
x =  1.0
y =  1.0

Per compilare il programma senza eseguirlo, inserisci:

make build SOURCE=relative/path/to/my_program.java

Altri esempi Java

Per altri esempi Java che illustrano come risolvere vari tipi di problemi di ottimizzazione, consulta gli esempi.

Identificare il tipo di problema da risolvere

Esistono molti tipi diversi di problemi di ottimizzazione nel mondo. Per ogni tipo di problema esistono diversi approcci e algoritmi per trovare la soluzione ottimale.

Prima di poter iniziare a scrivere un programma per risolvere un problema di ottimizzazione, devi identificare il tipo di problema da affrontare, quindi scegliere un risoltore appropriato, ovvero un algoritmo per trovare la soluzione ottimale.

Di seguito troverai una breve panoramica dei tipi di problemi risolti con OR-Tools e i link alle sezioni di questa guida che spiegano come risolvere ciascun tipo di problema.

Ottimizzazione lineare

Come hai appreso nella sezione precedente, un problema di ottimizzazione lineare è un problema in cui la funzione obiettivo e i vincoli sono espressioni lineari nelle variabili.

Il risolutore principale in OR-Tools per questo tipo di problema è il risolutore di ottimizzazione lineare, che in realtà è un wrapper per diverse librerie per l'ottimizzazione lineare e per l'ottimizzazione di numeri interi misti, comprese le librerie di terze parti.

Scopri di più sull'ottimizzazione lineare

Ottimizzazione con numeri interi misti

Un problema di ottimizzazione di numeri interi misti è un problema in cui alcune o tutte le variabili devono essere numeri interi. Un esempio è il problema di assegnazione, in cui un gruppo di lavoratori deve essere assegnato a un insieme di attività. Per ogni worker e attività, definisci una variabile il cui valore è 1 se il worker specificato è assegnato all'attività specificata e 0 negli altri casi. In questo caso, le variabili possono assumere solo i valori 0 o 1.

Scopri di più sull'ottimizzazione con numeri interi misti

Ottimizzazione dei vincoli

L'ottimizzazione dei vincoli, o programmazione di vincoli (CP), identifica soluzioni attuabili su un gran numero di candidati, dove il problema può essere modellato in termini di vincoli arbitrari. La CP si basa sulla fattibilità (trovare una soluzione fattibile) piuttosto che sull'ottimizzazione (trovare una soluzione ottimale) e si concentra sui vincoli e sulle variabili piuttosto che sulla funzione obiettivo. Tuttavia, il CP può essere utilizzato per risolvere problemi di ottimizzazione semplicemente confrontando i valori della funzione obiettivo per tutte le soluzioni fattibili.

Scopri di più sull'ottimizzazione dei vincoli

Assignment

I problemi di assegnazione prevedono l'assegnazione di un gruppo di agenti (ad esempio, lavoratori o macchine) a un insieme di attività, che prevede un costo fisso per l'assegnazione di ciascun agente a un'attività specifica. Il problema è trovare l'assegnazione con il costo totale minimo. I problemi di assegnazione sono in realtà un caso speciale di problemi di flusso di rete.

Scopri di più sull'assegnazione

Confezionamento

Il bin packing è il problema di inserire un insieme di oggetti di dimensioni diverse in container di capacità diverse. L'obiettivo è pacchettizzare il maggior possibile di oggetti, in base alle capacità dei container. Un caso speciale di questo è il problema dello zaino, in cui c'è un solo container.

Scopri di più sul bin packing

Pianificazione in corso

I problemi di pianificazione prevedono l'assegnazione di risorse per l'esecuzione di una serie di attività in momenti specifici. Un esempio importante è rappresentato dal problema dell'officina, in cui più job vengono elaborati su più macchine. Ogni job consiste in una sequenza di attività, che devono essere eseguite in un determinato ordine e ogni attività deve essere elaborata su una macchina specifica. Il problema è assegnare una pianificazione in modo che tutti i job vengano completati nel più breve intervallo di tempo possibile.

Scopri di più sulla pianificazione

Routing

I problemi di percorso riguardano l'individuazione dei percorsi ottimali per un parco veicoli di attraversamento di una rete, definiti da un grafico diretto. Il problema di assegnazione dei pacchi ai furgoni, descritto nella sezione Che cos'è un problema di ottimizzazione?, è un esempio di problema di routing. Un altro è il problema del venditore se viaggi.

Scopri di più sul routing

Flussi di rete

Molti problemi di ottimizzazione possono essere rappresentati da un grafico diretto costituito da nodi e archi diretti tra di loro. Ad esempio, i problemi di trasporto, in cui le merci vengono spedite attraverso una rete ferroviaria, possono essere rappresentati da un grafico in cui gli archi sono linee ferroviarie e i nodi sono centri di distribuzione.

Nel problema di flusso massimo, ogni arco ha una capacità massima che può essere trasportata attraverso di esso. Il problema è assegnare la quantità di beni da spedire attraverso ogni arco in modo che la quantità totale da trasportare sia il più grande possibile.

Scopri di più sui flussi di rete