Inizia a utilizzare OR-Tools per Python

Le seguenti sezioni ti insegneranno a utilizzare OR-Strumenti per Python:

• Che cos'è un problema di ottimizzazione?
• Risolvere un problema di ottimizzazione in Python
• Altri esempi di Python
• Identificare il tipo di problema da risolvere

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.

Risolvere un problema di ottimizzazione in Python

Quindi, forniremo un esempio di problema di ottimizzazione e mostreremo come impostarlo e risolverlo in Python.

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 Python

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

Nota: alla fine della sezione vengono mostrati il programma Python completo e i passaggi per eseguirlo.

Procedi nel seguente modo:

• Importa le librerie richieste.

  from ortools.init.python import init
  from ortools.linear_solver import pywraplp

• Dichiara il risolutore.

  # Create the linear solver with the GLOP backend.
  solver = pywraplp.Solver.CreateSolver("GLOP")
  if not solver:
      print("Could not create solver GLOP")
      return

  pywraplp è un wrapper Python per il risolutore C++ sottostante. L'argomento "GLOP" specifica GLOP, il risolutore lineare OR-Strumenti.
• Crea le variabili.

  # Create the variables x and y.
  x_var = solver.NumVar(0, 1, "x")
  y_var = solver.NumVar(0, 2, "y")
  
  print("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:

  infinity = solver.infinity()
  # Create a linear constraint, x + y <= 2.
  constraint = solver.Constraint(-infinity, 2, "ct")
  constraint.SetCoefficient(x_var, 1)
  constraint.SetCoefficient(y_var, 1)
  
  print("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.
  objective = solver.Objective()
  objective.SetCoefficient(x_var, 3)
  objective.SetCoefficient(y_var, 1)
  objective.SetMaximization()

  Il metodo SetMaximization dichiara che questo è un problema di massimizzazione.
• Richiama il risolutore e visualizza i risultati.

  print(f"Solving with {solver.SolverVersion()}")
  result_status = solver.Solve()
  print(f"Status: {result_status}")
  if result_status != pywraplp.Solver.OPTIMAL:
      print("The problem does not have an optimal solution!")
      if result_status == pywraplp.Solver.FEASIBLE:
          print("A potentially suboptimal solution was found")
      else:
          print("The solver could not solve the problem.")
          return
  
  print("Solution:")
  print("Objective value =", objective.Value())
  print("x =", x_var.solution_value())
  print("y =", y_var.solution_value())

Completa il programma

Di seguito è riportato il programma completo.

from ortools.init.python import init
from ortools.linear_solver import pywraplp


def main():
    print("Google OR-Tools version:", init.OrToolsVersion.version_string())

    # Create the linear solver with the GLOP backend.
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if not solver:
        print("Could not create solver GLOP")
        return

    # Create the variables x and y.
    x_var = solver.NumVar(0, 1, "x")
    y_var = solver.NumVar(0, 2, "y")

    print("Number of variables =", solver.NumVariables())

    infinity = solver.infinity()
    # Create a linear constraint, x + y <= 2.
    constraint = solver.Constraint(-infinity, 2, "ct")
    constraint.SetCoefficient(x_var, 1)
    constraint.SetCoefficient(y_var, 1)

    print("Number of constraints =", solver.NumConstraints())

    # Create the objective function, 3 * x + y.
    objective = solver.Objective()
    objective.SetCoefficient(x_var, 3)
    objective.SetCoefficient(y_var, 1)
    objective.SetMaximization()

    print(f"Solving with {solver.SolverVersion()}")
    result_status = solver.Solve()

    print(f"Status: {result_status}")
    if result_status != pywraplp.Solver.OPTIMAL:
        print("The problem does not have an optimal solution!")
        if result_status == pywraplp.Solver.FEASIBLE:
            print("A potentially suboptimal solution was found")
        else:
            print("The solver could not solve the problem.")
            return

    print("Solution:")
    print("Objective value =", objective.Value())
    print("x =", x_var.solution_value())
    print("y =", y_var.solution_value())

    print("Advanced usage:")
    print(f"Problem solved in {solver.wall_time():d} milliseconds")
    print(f"Problem solved in {solver.iterations():d} iterations")


if __name__ == "__main__":
    init.CppBridge.init_logging("basic_example.py")
    cpp_flags = init.CppFlags()
    cpp_flags.stderrthreshold = True
    cpp_flags.log_prefix = False
    init.CppBridge.set_flags(cpp_flags)
    main()

Gestione del programma

Puoi eseguire il programma indicato sopra nel seguente modo:

1. Copia e incolla il codice riportato sopra in un nuovo file e salvalo come program.py.
2. Apri una finestra di comando e passa alla directory in cui hai salvato program.py. Al prompt dei comandi, inserisci:

   python relative/path/to/program.py

   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

Altri esempi di Python

Consulta la pagina Esempi per altri esempi Python 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
• Ottimizzazione dei vincoli
• Ottimizzazione con numeri interi misti
• Compito
• Programmazione
• Imballaggio
• Routing
• Flussi di rete

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