Inizia a utilizzare OR-Tools per Java

Nelle sezioni seguenti inizierai a utilizzare OR-Strumenti per Java:

Che cos'è un problema di ottimizzazione?

L'obiettivo dell'ottimizzazione è trovare la migliore soluzione a un problema tra un ampio insieme di soluzioni possibili. (Talvolta la soluzione potrebbe essere soddisfacente; OR-Strumenti può fare lo stesso.)

Di seguito è riportato un problema di ottimizzazione tipico. Supponiamo che una società di spedizioni consegni i pacchi ai propri clienti con un parco autocarri. Ogni giorno l'azienda deve assegnare i pacchi ai camion, quindi scegliere un percorso per ciascun camion in cui consegnare i pacchi. Ogni possibile assegnazione di pacchi e percorsi ha un costo basato sulla distanza totale da percorrere per i camion ed eventualmente anche su altri fattori. Il problema è scegliere le assegnazioni di pacchetti e route che hanno il costo minimo.

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 impostare un problema di ottimizzazione, devi definire una funzione che calcoli il valore dell'obiettivo per qualsiasi soluzione possibile. Questa è 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: limitazioni sull'insieme di possibili soluzioni, basate sui requisiti specifici del problema. Ad esempio, se la società di spedizione non può assegnare pacchi al di sopra di un determinato peso ai camion, le soluzioni verranno applicate a un vincolo.

    Una soluzione disponibile è una soluzione che soddisfa tutti i vincoli dati per il problema, senza essere necessariamente ottimale.

Il primo passo per risolvere un problema di ottimizzazione è identificare l'obiettivo e i vincoli.

Risoluzione di un problema di ottimizzazione in Java

Quindi, 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 più usate è 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.

Massimizza 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. Definire 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 imposta e risolve il problema.

Procedi nel seguente modo:

  • Importa le librerie richieste. 
    import com.google.ortools.Loader;
import com.google.ortools.init.OrToolsVersion;
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");
if (solver == null) {
  System.out.println("Could not create solver GLOP");
  return;
}
    MPSolver è un wrapper per risolvere qualsiasi problema di programmazione lineare o 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 &leq; x ≤ 1 e 0 &leq; y ≤ 2, sono già impostati dalle definizioni delle variabili. Il seguente codice definisce il vincolo x + y &leq; 2: 
    double infinity = Double.POSITIVE_INFINITY;
// Create a linear constraint, x + y <= 2.
MPConstraint ct = solver.makeConstraint(-infinity, 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 obiettivo. 
    // 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 questo è un problema di massimizzazione.
  • Richiama il risolutore e visualizza i risultati. 
    System.out.println("Solving with " + solver.solverVersion());
final MPSolver.ResultStatus resultStatus = solver.solve();
System.out.println("Status: " + resultStatus);
if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
  System.out.println("The problem does not have an optimal solution!");
  if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
    System.out.println("A potentially suboptimal solution was found");
  } else {
    System.out.println("The solver could not solve the problem.");
    return;
  }
}

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

Di seguito è riportato il programma completo.

package com.google.ortools.linearsolver.samples;

import com.google.ortools.Loader;
import com.google.ortools.init.OrToolsVersion;
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();

    System.out.println("Google OR-Tools version: " + OrToolsVersion.getVersionString());

    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");
    if (solver == null) {
      System.out.println("Could not create solver GLOP");
      return;
    }

    // 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());

    double infinity = Double.POSITIVE_INFINITY;
    // Create a linear constraint, x + y <= 2.
    MPConstraint ct = solver.makeConstraint(-infinity, 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();

    System.out.println("Solving with " + solver.solverVersion());
    final MPSolver.ResultStatus resultStatus = solver.solve();

    System.out.println("Status: " + resultStatus);
    if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
      System.out.println("The problem does not have an optimal solution!");
      if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
        System.out.println("A potentially suboptimal solution was found");
      } else {
        System.out.println("The solver could not solve the problem.");
        return;
      }
    }

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

    System.out.println("Advanced usage:");
    System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
    System.out.println("Problem solved in " + solver.iterations() + " iterations");
  }

  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, quindi salvalo come my_program.java.
  2. Apri una finestra di comando nel livello superiore della directory in cui hai installato OR-Strumenti 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 di Java

Consulta la sezione Esempi per consultare altri esempi Java che illustrano come risolvere vari tipi di problemi di ottimizzazione.

Identificare il tipo di problema da risolvere

Esistono diversi tipi di problemi di ottimizzazione. Per ogni tipo di problema esistono approcci e algoritmi diversi 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 risolvere e quindi scegliere un risolvo appropriato, ovvero un algoritmo che consenta di trovare la soluzione ottimale.

Di seguito troverai una breve panoramica dei tipi di problemi risolti da OR-Strumenti e 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 dell'ottimizzazione lineare, che in realtà è un wrapper per diverse librerie lineari e di valori interi misti, incluse le librerie di terze parti.

Scopri di più sull'ottimizzazione lineare

Ottimizzazione con numeri interi misti

Un problema di ottimizzazione di numeri interi misti si verifica in cui alcune o tutte le variabili devono essere numeri interi. Un esempio è il problema dei compiti, 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à specifica e 0 negli altri casi. In questo caso, le variabili possono assumere solo i valori 0 o 1.

Scopri di più sull'ottimizzazione di numeri interi misti

Ottimizzazione del vincolo

L'ottimizzazione del vincolo, o programmazione dei vincoli (CP), identifica soluzioni realizzabili tra un insieme molto ampio di candidati, in cui il problema può essere modellato in termini di vincoli arbitrari. La CP si basa sulla fattibilità (trova una soluzione fattibile) piuttosto che sull'ottimizzazione (trova una soluzione ottimale) e si concentra sui vincoli e sulle variabili piuttosto che sulla funzione obiettivo. Tuttavia, CP può essere utilizzato per risolvere problemi di ottimizzazione semplicemente confrontando i valori della funzione obiettivo per tutte le soluzioni realizzabili.

Scopri di più sull'ottimizzazione dei vincoli

Assignment

I problemi di assegnazione comportano l'assegnazione di un gruppo di agenti (ad esempio, lavoratori o macchine) a un insieme di attività, in cui è previsto un costo fisso per l'assegnazione di ogni agente a un'attività specifica. Il problema consiste nel 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ù sui compiti

Confezionamento

Il bin packing è il problema di pacchettizzare un insieme di oggetti di dimensioni diverse in container di capacità differenti. L'obiettivo è comprimere il maggior numero 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

Programmazione

La pianificazione dei problemi comporta l'assegnazione di risorse per eseguire una serie di attività in momenti specifici. Un esempio importante è dato 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 è l'assegnazione di 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 una flotta di veicoli per attraversare una rete, definiti da un grafico diretto. Il problema di assegnazione dei pacchi ai furgoni, descritto in Che cos'è un problema di ottimizzazione?, è un esempio di problema di routing. Un altro è il problema del venditore durante i viaggi.

Scopri di più sul routing

Flussi di rete

Molti problemi di ottimizzazione possono essere rappresentati da un grafico diretto composto da nodi e archi diretti tra di essi. Ad esempio, i problemi relativi ai trasporti, in cui le merci vengono spedite su 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. Il problema è assegnare la quantità di merci da spedire attraverso ogni arco, in modo che la quantità totale da trasportare sia la più grande possibile.

Scopri di più sui flussi di rete