Note di rilascio di OR-Tools

Questa pagina elenca le modifiche apportate a OR-Tools, tra cui nuove funzionalità, correzioni di bug e miglioramenti al codice e alle procedure di installazione.

Se riscontri problemi durante l'installazione di OR-Tools, consulta la sezione Risoluzione dei problemi nelle istruzioni di installazione di OR-Tools. Se il tuo problema non è presente nell'elenco, controlla i problemi su GitHub oppure non esitare ad aprirne uno nuovo e saremo lieti di fornirti assistenza.

Di seguito sono riportate le note di rilascio di OR-Tools, a partire dalla release più recente.

Maggio 2024

Annuncio del rilascio della versione 9.10 di OR-Strumenti

Abbiamo rilasciato OR-Strumenti v9.10. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Puoi trovare la nota di rilascio su github

March 2024

Annuncio del rilascio della versione 9.9 di OR-Strumenti

Abbiamo rilasciato OR-Strumenti v9.9. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Puoi trovare la nota di rilascio su github

Novembre 2023

Lancio della versione 9.8 di OR-Tools

Abbiamo rilasciato OR-Strumenti v9.8. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alla piattaforma

  • Aggiungi Python 3.12.
  • Aggiungi il supporto per Ubuntu 23.10

Linear Solver

  • Porta ModelBuilder a .Net.
  • Rinomina LogCallback in MbLogCallback per evitare conflitti con SAT LogCallback.
  • API Extend ModelBuilder:
    • Aggiungi vincoli di indicatori.
    • Aggiungi il supporto del suggerimento.
    • Aggiungi la clonazione dei modelli.

Opzione matematica

  • Una rielaborazione profonda.

Routing

  • Aggiungi lo stato ROUTING_OPTIMAL.
  • Imposta RoutingModel come non copiabile né spostabile.
  • Correggi il loop infinito negli operatori di ricerca locale.
  • Aggiungi uno struct interno PickupDeliveryPosition.
  • Aggiungi i metodi IsPickup() e IsDelivery().

SAT

  • Riduci l'ingombro di memoria per i modelli di grandi dimensioni.
  • Ricerca della pianificazione migliorata.
  • add packing_precedences_lns.
  • ottimizzare e correggere il salto di fattibilità.
  • ottimizzare il logging di presolvenza lineare e migliorare il logging di presolvenza.
  • Migliora la presolvenza per int_abs, int_mod, int_prod e lin_max.
  • Migliora il supporto Panda
  • Poche correzioni di bug.

Log delle modifiche di GitHub

Agosto 2023

Annuncio del rilascio della versione 9.7 di OR-Strumenti

Abbiamo rilasciato OR-Strumenti v9.7. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alla piattaforma

  • Rilascia Centos-8 (EOL).
  • Rilascia Debian 10.
  • Rilascia Fedora [33, 36] (EOL).
  • Rilascia Ubuntu 18.04 LTS (EOL).
  • Elimina Python 3.7 (EOL).
  • Disattiva il supporto di netcore3.1 in CMake (EOL).

Python generatore di modelli

  • Consenti l'utilizzo di serie e frame di dati Pandas per creare variabili.
  • Completa le informazioni di digitazione

PDLP

  • vari aggiornamenti.

CP-SAT

  • Miglioramenti delle prestazioni. (fasibility_jump, lin_max)
  • Migliora la gestione dei tagli
  • Nuovo worker di goal_shaving_search dedicato a migliorare il limite inferiore dell'obiettivo (durante la riduzione al minimo)
  • Digitazione di annotazioni per cp_model.py python
  • Supporto parziale sperimentale per i panda in cp_model.py
  • Worker sperimentali basati sulla violazione della ricerca locale:
    • attivato con i parametri: num_violation_ls:xxx
    • ottimizzato per il modello lineare (linear, bool_or, bool_and, at_most_one, exactly_one)
    • funziona correttamente con lin_max, prodotto, divisione
    • supporta no_overlap, cumulative, circuito, route
    • disattivata con no_overlap_2d
    • numero consigliato di worker ls: num_workers -> num_violation_ls: (8, 1), (16, 2) (24, 3), (32, 4)

Log delle modifiche di GitHub

Marzo 2023

Annuncio del rilascio della versione 9.6 di OR-Strumenti

Abbiamo rilasciato OR-Strumenti v9.6. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alla piattaforma

  • Aggiungi il supporto Fedora 37 e 38.
  • Elimina Python 3.6 (non supportato da protobuf).
  • Rilascia Python 3.7 su macOS (non supportato da scipy).
  • Aggiungi il supporto net7.0 in CMake (utilizza -DUSE_DOTNET_7=ON)
  • Elimina netcore3.1 nei pacchetti nuget .org

Dipendenze

  • SCIP v801 -> v803 (nota: ora SCIP usa una licenza compatibile con OSI)
  • calata in corda doppia 20220623.1 -> 20230105.0
  • Protobuf v21.5 -> v21.12
  • SWIG 4.1.1
  • JNA Java 5.11.0 -> 5.12.1

Bazel

  • Aggiungi il supporto di pybind11.
  • Aggiungi il supporto per wrapper Java.

Risolutori

  • PDLP: dd wrapper Python.
  • CP-SAT: Miglioramenti delle prestazioni.
  • GLOP: Modifica la presolvenza.
  • ModelBuilder: Python: Better Numpy support.
  • Routing: miglioramenti delle prestazioni (ricerca locale)

Problemi noti:

  • CP-SAT: se il subsolver pseudo_costs viene ignorato, viene restituito un parametro non valido (vedi #3706).

Novembre 2022

Lancio di OR-Strumenti v9.5

Abbiamo rilasciato OR-Strumenti v9.5. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alla piattaforma

  • Aggiungere il supporto SID Debian.
  • Aggiungi il supporto Fedora 35 e 36.
  • Aggiungi il supporto per Ubuntu 22.10.
  • Rilascia Python 3.6 su macOS.
  • Aggiungi il supporto per Python 3.11.

Aggiornamento delle dipendenze

  • Protobuf v19.4 -> v21.5.
  • Risolutore SCIP v800 -> v801.

CP-SAT

  • Miglioramenti alla soluzione: max(array), vincoli booleani, vincoli lineari.
  • La ricerca con interleaving dovrebbe essere deterministica in parallelo.
  • Tagli lineari: pulisci tagli quadrati e int_prod; riscrivi la pipeline di taglio.
  • Modello e soluzione di input dell'impronta (visibili nel log).
  • Pianificazione dei miglioramenti.
  • La solita serie di correzioni di bug (arresti anomali durante la fase di presolvenza, arresti anomali nei tagli, soluzioni irrealizzabili, modello impossibile in LNS).

GLOP

  • Velocizza la riscrittura dell'algebra lineare e della regola di selezione pivot.

Linear Solver

  • Aggiungi knapsack_interface.cc.
  • Sposta l'API model_builder nella directory linear_solver (intestazioni ed esempi).
  • Aggiungi il supporto per Gurobi 10.

Routing

  • Libera pochi parser per vari tipi di problemi di routing.

Agosto 2022

Lancio della versione 9.4 di OR-Strumenti

Abbiamo rilasciato OR-Strumenti v9.4. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Piattaforme

  • Aggiungi il supporto Debian-10 (vedi #3029).
  • Aggiungi il supporto di Ubuntu 22.04 LTS (vedi #3276). Nota: non avrà il supporto .Net 3.1 (vedi dotnet/core#7038).
  • Rimozione del supporto di Ubuntu 21.10.

Varie

  • Suddividi l'archivio per lingue e aggiungi la configurazione CMake a quella C++ (#3200).

Grafico

Suddividi ortools.graph.pywrapgraph in:

  • ortools.graph.python.linear_sum_assignment.
  • ortools.graph.python.max_flow.
  • ortools.graph.python.min_cost_flow.

Ciò consente di utilizzare numpy per velocizzare la configurazione dei problemi.

CP-SAT

Alcuni miglioramenti su:

  • pianificazione (propagazione, tagli, limiti inferiori).
  • MaxSAT (presolve, euristica basata su core).
  • Prestazioni MIP (presolvenza, interruzioni).

Marzo 2022

Lancio di OR-Tools v9.3

Abbiamo rilasciato OR-Strumenti v9.3. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alla piattaforma

  • Interrompi l'assistenza Debian-10.
  • Elimina l'assistenza per Ubuntu-16.04.
  • Elimina .NET Framework 4.5.2.

Aggiornamento delle dipendenze

  • Aggiungi l'oggetto 3.4.0.
  • Aggiungi Google R2 2021-11-01.
  • Protobuf 3.19.1 -> 3.19.4.
  • SCIP 7.0.1 -> v800.

Python

  • Aggiungi pybind11.

Caratteristiche

  • Aggiungi PDLP come sperimentale.
  • Aggiungi MathOpt come sperimentale.

CP-SAT

  • Alcune API sono state rinominate per coerenza, ad esempio LinearExpr.ScalProd. -> LinearExpr.WeightedSum..
  • Aggiungi AddAtLeastOne/AddAtMostOne/AddExactlyOne metodi.
  • Aggiungi AddMultiplicationConstraint(z, x, y) in tutte le lingue.
  • Aggiungi AddMultipleCircuit() in tutte le lingue.

C++

  • Testo esplicito: IntVar(BoolVar).
  • LinearExpr::Add* rimosso e sostituito dall'operatore, ad esempio LinearExpr +=.
  • Aggiungere operatori aritmetici all'espressione lineare.
  • LinearExpr::BooleanSum/BooleanScalProd rimosso, utilizza Sum/WeightedSum.
  • Aggiungi CpModelBuilder::FixVariable() che sovrascrivono il dominio della variabile in un singolo valore.

Java

  • Riscrivi LinearExpr, aggiungi una classe del builder incrementale: LinearExpr.newBuilder().add(x).addSum(<array of variables>).build().
  • Segui l'API C++: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment e ForbiddenAssignment ora restituiscono una classe specializzata con un'API incrementale per aggiungere nuove variabili, termini, richieste...

C

  • Documenta tutti i metodi.
  • Segui l'API C++: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment e ForbiddenAssignment ora restituiscono una classe specializzata con un'API incrementale per aggiungere nuove variabili, termini, richieste...
  • Aggiungi la classe LinearExprBuilder per creare espressioni in modo incrementale.

Sistema di compilazione

CMake

  • Richiedi almeno CMake >= 3,18.

Marca

  • Ora utilizzare internamente la build basata su CMake.

Dicembre 2021

Annuncio del rilascio della versione 9.2 di OR-Strumenti

Abbiamo rilasciato OR-Strumenti v9.2. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alla piattaforma

  • Aggiunta del supporto per Ubuntu 21:10 (ultima release in sequenza).

Aggiornamento delle dipendenze

  • Aggiornamento di .Net TFM net5.0 -> net6.0 (è necessario .Net SDK 6.0 LTS e .Net SDK 3.1 LTS).
  • dbeil-cpp 20210324.2 -> 20211102.0.
  • Protobuf 3.18.0 -> 3.19.1.
  • Googletest 1.10.0 -> 1.11.0.
  • Python: add numpy >= 1.13.3.
  • Su MacOS compila Coin-OR in -O1 per evitare arresti anomali nei runner.

Routing

  • Miglioramento dei filtri.
  • Migliorare l'euristica della prima soluzione.
  • Migliora i posizionamenti delle interruzioni temporali.

CP-SAT

Modifiche che provocano un errore

  • Il buffer di protocollo sottostante non è compatibile con le versioni precedenti. Qualsiasi buffer di protocollo memorizzato dovrà essere rigenerato con le API del builder aggiornate (in C++, Python, Java e .NET)
  • In particolare, il protobuf dell'intervallo è stato pulito poiché abbiamo rimosso i vecchi campi (inizio, dimensione e fine) e rinominato quelli nuovi (utilizzando _view) per utilizzare il nome dei campi rimossi.

Nuove funzionalità

  • I vincoli all_different, reservoir, modulo, multiplication e division accettano espressioni affine (a * var + b) ovunque siano richieste variabili intere.
  • L'obiettivo accetta i coefficienti in virgola mobile (consulta la classe DoubleLinearExpr in C++/Java/.NET. Vedi l'esempio knapsack_2d_sat.py in Python).
  • Il vincolo no_overlap_2d supporta intervalli facoltativi.
  • L'API C++ implementa gli operatori + e * per creare espressioni.

Miglioramenti

  • Codice di prerisoluzione migliorato.
  • Controllo dei modelli più preciso.
  • Rielabora il vincolo del serbatoio.
  • Aggiungi tagli energici per il vincolo no_overlap_2d.
  • Miglioramento dell'allentamento lineare dei vincoli di codifica (literal implies var == value).

Metodi deprecati e rimossi

  • C++ BooleanSum e BooleanScalProd deprecati. Basta usare Sum e ScalProd.
  • C++ AddLinMinEquality e AddLinMaxEquality rimossi. Basta usare AddMinEquality e AddMaxEquality.

Incompatibilità future

  • In futuro, riscriveremo il livello di definizione dei modelli Java in modo che sia più vicino al livello C++.
  • Nel livello di definizione del modello C++, renderemo esplicito il ruolo IntVar(BoolVar var).
  • Stiamo contemplando di rendere l'API Python conforme allo standard PEP 8 (utilizzando i nomi snake_case). In questo caso, forniremo un file sed per la portabilità del codice.

Sistema di compilazione

Bazel

  • Correggi la build di Windows.

CMake

  • Aggiungi l'opzione FETCH_PYTHON_DEPS (valore predefinito: ON).
  • Aggiungi il supporto facoltativo per il risolutore GPLK (valore predefinito: -DUSE_GLPK=OFF).

Python

  • Supporta i numeri interi numpy nella maggior parte dell'API CP-SAT.
  • Correggi l'errore __version__ mancante.

Settembre 2021

Annuncio del rilascio della versione 9.1 di OR-Strumenti

Abbiamo rilasciato OR-Strumenti v9.1. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alla piattaforma

  • Python: usa l'immagine manylinux2014 (vedi PEP 599).
  • Python: aggiungi il supporto per aarch64 Linux usando l'immagine manylinux2014_aarch64.
  • .Net: aggiungi il supporto di .Net 5.0.

Aggiornamento delle dipendenze

  • dbeil-cpp 20210324.1 -> 20210324.2.
  • Protobuf 3.15.8 -> 3.18.0.
  • SCIP 7.0.1 -> master.
  • Googletest 1.8.0 -> 1.10.0.
  • python: uso di warning in cp_model.py (vedi #2530).
  • python: BSL-py 0.11 -> 0.13.

CMake

  • Versione minima di Bump richiesta 3.14-3.15 (vedi #2528).
  • Python: picco minimo richiesto versione 3.14 -> 3.18 (vedi #2774).

Marca

La build basata sulla creazione è deprecata. Esegui la migrazione a CMake o Bazel per creare la build dall'origine.

Java

  • Migliora la robustezza del caricatore di librerie nativo (vedi #2742).
  • Correggi l'arresto anomalo di JVM Garbage Collector durante lo smaltimento del modello di routing o del risolutore di vincoli (vedi #2091) (vedi #2466).
  • Correggi l'arresto anomalo del callback di logging CP-SAT quando utilizzi più worker (vedi #2775).

CP-SAT

  • Migliora la solidità del codice LNS (vedi #2525).
  • Migliora il codice di programmazione: nuovi metodi predefiniti per creare intervalli a dimensione fissa, nuove euristiche di ricerca, presolvenza migliorata e nuovi tagli lineari.
  • Migliora il codice di routing: nuovo LNS dedicato.
  • Migliora il controllo dei modelli. Ora è più pignola, in particolare a causa dei potenziali overflow.
  • Miglioramento del codice MIP: migliore prerisoluzione e molteplici miglioramenti al rilassamento lineare dei modelli MIP e CP.
  • Migliorare la diversità nella ricerca. Se utilizzi più di 12 worker, aggiungi worker dedicati a migliorare il limite inferiore dell'obiettivo.
  • Modifica al codice di parallelismo: per impostazione predefinita, il risolutore utilizzerà tutti i core disponibili. Utilizza num_search_parameters per specificare il livello di parallelismo.
  • Depreca SearchAllSolutions e SolveWithSolutionCallback.
  • API Python: controlli più pedanti quando si utilizza var == ... o var != ... al di fuori di una chiamata model.Add().

Aprile 2021

Lancio di OR-Strumenti v9.0

Abbiamo rilasciato OR-Strumenti v9.0. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Aggiornamenti delle dipendenze

Java

Correzioni di bug

  • Migliora il multi-threading quando utilizzi il risolutore CP-SAT (vedi #1588).
  • Correggi il supporto del wrapper Python per std::vector&ltstd::string&gt (vedi #2453).
  • Supporto per la rielaborazione di CPLEX (vedi #2470).

Modifica che provoca un errore nota

  • Aggiungi l'accesso al logger in Python, Java e .Net (vedi #2245).
  • Sostituzione di tutti i tipi Google personalizzati con quelli forniti in cstdint.

CP-SAT

  • I metodi SearchForAllSolutions(), SearchAllSolutions() e SolveWithSolutionCallback() sono deprecati. Usa invece Solve().
  • Migliora il supporto degli operatori standard Python. Questo può danneggiare il codice esistente errato.

Marzo 2021

Lancio di OR-Strumenti v8.2

Abbiamo rilasciato OR-Strumenti v8.2. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Aggiornamenti delle dipendenze

  • Abseil-cpp 20200923.2 aggiornato a 20200923.3 LTS.
  • Protobuf 3.14.0 aggiornato alla 3.15.3.

Routing

  • RoutingModel.RegisterTransitMatrix() e RoutingModel.RegisterUnaryTransitVector() aggiunti.
  • Modifica il ritorno di RoutingModel.AddVectorDimension() e RoutingModel.AddMatrixDimension() in std::pair&ltint, bool&gt il cui int è l'ID valutatore del trasporto pubblico.

Dicembre 2020

Lancio di OR-Strumenti v8.1

Abbiamo rilasciato OR-Strumenti v8.1. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Aggiornamenti delle dipendenze

  • Abseil-cpp 20200923 aggiornato a 20200923.2 LTS.
  • Protobuf 3.13.0 aggiornato alla 3.14.
  • Aggiungi il supporto per Gurobi 9.1.0
  • Elimina la dipendenza GLog (sostituita da un'implementazione personalizzata in base ai flag ABeil-cpp)
  • Elimina la dipendenza GFlag (sostituita dal componente flag ABeil-cpp)

Correzioni di bug

  • Correggi il doppio conteggio della licenza fluttuante Gurobi (vedi #2227).
  • Correggi la build di Windows (vedi #2200).

Ottobre 2020

Lancio di OR-Strumenti v8.0

Abbiamo rilasciato OR-Strumenti v8.0. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alla piattaforma

  • Aggiunto il supporto per Python 3.9 (#2187)
  • Interruzione del supporto per Python 3.5 (#2186) <!-- In attesa del supporto di Microsoft dotnet-sdk potrebbe essere generato dopo l'uscita della release...
    • Aggiunto il supporto per Ubuntu 20.10 (#2188) -->
  • Interruzione del supporto per Ubuntu 16.04 LTS (#2188)
  • Interruzione del supporto per Ubuntu 19.10 (#2188)

Aggiornamenti delle dipendenze

  • Abseil-cpp 20200225.2 aggiornato a 20200923 LTS.
  • Protobuf 3.12.2 aggiornato alla versione 3.13.0.

Modifica che provoca un errore nota

  • Ora il codice sorgente Routing e CP-SAT utilizza alcune funzionalità di C++17. Avviso: se fornisci la tua versione di abseil-cpp, verifica che sia creata anche per C++17.
  • La firma di MPSolver::CreateSolver è stata modificata. L'argomento del nome del modello è stato eliminato.

CMake

  • Correggi la disattivazione del supporto SCIP quando utilizzi -DUSE_SCIP=OFF (vedi #2129).
  • Integra esempi ed esempi al sistema di compilazione CMake. Nota: può essere disattivato utilizzando -DBUILD_SAMPLES=OFF e -DBUILD_EXAMPLES=OFF. Nota: può essere disattivata per una lingua specifica utilizzando -DBUILD_<LANG>_SAMPLES=OFF o -DBUILD_<LANG>_EXAMPLES=OFF.
    • Con <LANG> tra:
    • CXX,
    • PYTHON,
    • JAVA e
    • DOTNET.

Marca

  • Richiedi Make >= 4.3 (uso della funzione di valutazione Marc).
  • Richiede CMake >= 3.14 (utilizzo dell'opzione CMake --verbose).
  • Aggiungi l'opzione per disabilitare il supporto SCIP utilizzando -DUSE_SCIP=OFF (vedi #2134).
  • Aggiungi l'opzione per disattivare il supporto di CLP e CBC utilizzando -DUSE_COINOR=OFF.

Java

  • OR-Tools ora genera pacchetti di esperti (vedi #202).

Correzioni di bug

  • Correggi la build C++ e Python su FreeBSD (vedi #2126).
  • Correggi il debug della build in Windows (vedi #2077).
  • Risolvi l'arresto anomalo di lunga data in parallelo su CP-SAT su Windows (vedi #2001, #2019).

Luglio 2020

Lancio di OR-Tools v7.8

Abbiamo rilasciato OR-Strumenti v7.8. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Aggiornamenti delle dipendenze

  • Gurobi 9.0.2 è ora preintegrato in programmi binari predefiniti. Cerca la libreria condivisa gurobi 90 nel percorso di installazione predefinito dei programmi di installazione di Gurobi su MAC OS X e Windows oppure nella directory GUROBI_HOME.
  • SCIP 7.0.1 è ora integrato in programmi binari predefiniti. Assicurati di rispettare la licenza SCIP prima di utilizzarla.
  • Aggiunto il supporto per la versione opzionale di Xpress Solver 8.9.0.

Linear Solver

  • È stato aggiunto un metodo LinearSolver::CreateSolver() statico per semplificare il controllo del supporto per i backend integrati con risolutori lineari. Funziona in tutte le lingue.

Correzioni di bug

  • È stata corretta la build basata su CMake su FreeBSD.
  • Correzione dell'ordinamento CP-SAT nella generazione di tagli cumulativi.
  • Risolto il problema di perdita di memoria del risolutore lineare nel wrapper .Net.

Giugno 2020

Lancio di OR-Tools v7.7

Abbiamo rilasciato OR-Strumenti v7.7. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Aggiornamenti delle dipendenze

  • Abseil-cpp b832dce aggiornato a c51510d (LTS 20200225.2).
  • Protobuf 3.11.4 aggiornato alla 3.12.2.

Nuove funzionalità e miglioramenti

  • Il risolutore CP-SAT ora restituisce Optimal anziché Feasible in un modello di soddisfazione (ovvero senza obiettivo).
  • È stata aggiunta l'euristica della pompa di fattibilità dalla community MIP.

Correzioni di bug

Risolto l'arresto anomalo multi-threading CP-SAT (vedi #2005).

Aprile 2020

Lancio di OR-Strumenti v7.6

Abbiamo rilasciato OR-Strumenti v7.6. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Nuove funzionalità di CP-SAT

Abbiamo aggiunto le seguenti nuove funzionalità al risolutore CP-SAT:

  • Gestione dei piani di taglio per gli LP migliorata.
  • Strumenti di debug.

Aggiornamenti delle dipendenze

Abseil-cpp 8ba96a8 aggiornato a b832dce (LTS 20200225).

Correzioni di bug

  • Risolto il bug CP-SAT UNSAT nella presolvenza (vedi #1908).
  • L'URL di swigwin.exe è stato corretto.
  • Correzione della gestione delle mappe dei tipi di SWIG per Java e .Net.

Gennaio 2020

Lancio di OR-Tools v7.5

Abbiamo rilasciato OR-Strumenti v7.5. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alla piattaforma

  • Aggiunto il supporto per Python 3.8 (#1719)
  • Eliminazione della compilazione del supporto dalle origini in Visual Studio 2017 (#1852).
  • Supporto aggiornato da Centos 7 a Centos 8 (#1827).

Aggiornamento delle dipendenze

Correzioni di bug

I seguenti problemi sono stati risolti in OR-Tools v7.5 (per un elenco completo, consulta Milestone v7.5).

In particolare:

  • Caricamento dell'assemblaggio corretto. Vedi #1421.
  • Sono stati esposti i metodi GetStartIndex() e GetEndIndex() di RouteIndexManager (#1843).
  • È stato corretto lo SWIG per rimuovere i metodi non funzionanti (#1838, #1276).

Ottobre 2019

Lancio di OR-Tools v7.4

Abbiamo rilasciato OR-Strumenti v7.4. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Nuove funzionalità e miglioramenti

  • Il risolutore CP-SAT ora verifica la presenza di vincoli che non supportano i valori letterali di applicazione. Il controllo del modello restituirà un errore prima di risolvere se un vincolo di questo tipo ha un valore letterale di applicazione.
  • Ricerca locale migliore e più veloce per la libreria di routing.
  • Il risolutore lineare ora supporta il software di terze parti Xpress-MP. Per utilizzarlo, dovrai ricreare OR-Tools dall'origine.
  • L'architettura del pacchetto NuGet è stata completamente riscritta. In particolare, ora supporta .NET framework >= 4.5.2 sulle piattaforme Windows.

Piattaforma deprecata

Come annunciato nelle note di rilascio di luglio 2019, OR-Tools non supporta più Python 2.7.

Aggiornamento delle dipendenze

Protobuf 3.9.0 è stato aggiornato alla versione 3.10.0.

Agosto 2019

Lancio di OR-Strumenti v7.3

Abbiamo rilasciato OR-Strumenti v7.3. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Piattaforma deprecata

Stiamo ritirando il supporto per Python 2.7 per allinearci al passaggio di Google a Python 3. Questa sarà l'ultima release di OR-Strumenti che supportano Python 2.7.

Aggiornamento delle dipendenze

Protobuf 3.8.0 è stato aggiornato alla versione 3.9.0.

Correzioni di bug

I seguenti problemi sono stati risolti in OR-Tools v7.3. Per un elenco completo, vedi Kanban 7.3.

In particolare:

  • Risolto il problema di trasmissione di init/int64 su Java (#1448),
  • Controllo di presolvenza corretto durante l'elaborazione di vincoli cumulativi vuoti.

Luglio 2019

Lancio di OR-Strumenti v7.2

Abbiamo rilasciato OR-Strumenti v7.2. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alla piattaforma

  • Stiamo ritirando il supporto per Python 2.7 per allinearci al passaggio di Google a Python 3. Ci sarà al massimo un'altra release di OR-Strumenti che supportano Python 2.7.
  • Ubuntu 18.10 aggiornato a Ubuntu 19.04.
  • Aggiunto il supporto per la compilazione da fonti in Visual Studio 2019.
  • Python 3.5 non è più supportato su Windows; utilizza Python 3.6 o una versione successiva.

Aggiornamenti alle dipendenze

  • Ora scegliamo come target CBC 2.10.3.
  • Ora puntiamo a Protobuf 3.8.0.

CP-SAT

  • Abbiamo apportato diversi miglioramenti alla ricerca, al parallelismo e al rilassamento lineare.
  • Sono state aggiunte le API LinearExpr.Sum() e LinearExpr.ScalProd() in Python.
  • API IntVar[].Sum() e IntVar[].ScalProd() deprecate in C#.
  • C++: SolveWithModel() rimosso perché era un duplicato di SolveCpModel().
  • Sono stati aggiunti i metodi CpModel.addGreaterThan() e CpModel.addLessThan() all'API Java.

Risolutore lineare

  • È stato aggiunto MPSolver.SetHint() per Python, Java e C# (supportato da SCIP e Gurobi).
  • È stato aggiunto MPSolver.SetNumThreads() per Python, Java e C# (supportato da CBC, Gurobi e SCIP).
  • Supporto riscritto per SCIP 6.0.1.

Documentazione di riferimento

  • Abbiamo aggiunto manuali di riferimento basati su doxygen e pdoc3 per tutte le lingue e per tutti gli strumenti (algoritmi, routing, grafico, linear_solver e CP-SAT). Consulta i manuali di riferimento degli strumenti OR.
  • La documentazione di riferimento è completa per C++ (tutti i prodotti) e CP-SAT (C++, Python, Java).
  • Stiamo esportando tutta la documentazione C++ in Python e Java.
  • La documentazione .NET è carente e non abbiamo soluzioni in futuro per migliorarla. L'abbiamo conservata così come mostra ancora l'API disponibile.

Maggio 2019

Lancio di OR-Tools v7.1

Abbiamo rilasciato OR-Strumenti v7.1. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alle dipendenze richieste

OR-Tools v7.1 presenta le seguenti dipendenze nuove e aggiornate:

  • glog versione 0.3.5 aggiornata alla versione 0.4.0
  • protobuf versione 3.6.1 aggiornata alla versione 3.7.1
  • Cbc 2.9.9 aggiornato alla versione 2.10.1
  • Cgl 0.59.10 aggiornato alla versione 0.60.1
  • Clp 1.16.11 aggiornato alla versione 1.77.1
  • Osi 0.107.9 aggiornato a 0.108.1
  • CoinUtils 2.10.14 aggiornato alla versione 2.11.1

Modifiche all'API CP-SAT

Le seguenti sezioni descrivono le modifiche all'API CP-SAT in OR-Strumenti 7.1.

Utilizzo del dominio per creare variabili

Gli esempi riportati di seguito mostrano come creare una variabile intera con domini non contigui. Questo sostituisce il metodo rimosso NewEnumeratedIntVar(). In questo caso, la variabile x può essere qualsiasi tra 1, 3, 4 o 6:

Python

model.NewIntVarFromDomain(cp_model.Domain.FromValues([1, 3, 4, 6]), 'x')

C++

model.NewIntVar(Domain::FromValues({1, 3, 4, 6}));

Java

model.newIntVarFromDomain(Domain.fromValues(new long[] {1, 3, 4, 6}), "x");

C#

model.NewIntVarFromDomain(Domain.FromValues(new long[] {1, 3, 4, 6}), "x");

Puoi creare variabili anche utilizzando un elenco di intervalli. Di seguito, la variabile x è vincolata a 1, 2, 4, 5 o 6:

Python

model.NewIntVarFromDomain(cp_model.Domain.FromIntervals([[1, 2], [4, 6]]), 'x')

C++

model.NewIntVar(Domain::FromIntervals({ {1, 2}, {4, 6} }));

Java

model.newIntVarFromDomain(Domain.fromIntervals(new long[][] { {1, 2}, {4, 6} }), "x");

C#

model.NewIntVarFromDomain(Domain.FromIntervals(new long[][] { new long[] {1, 2}, new long[] {4, 6} }), "x");

Utilizzo di Domain in un'espressione lineare

I seguenti esempi mostrano come limitare un'espressione lineare in un dominio non contiguo. Qui l'espressione lineare linear_expr è definita su 5, 6, 8, 9 e 10:

Python

model.AddLinearExpressionInDomain(linear_expr, cp_model.Domain.FromIntervals([(5, 6), (8, 10)]))

C++

model.AddLinearConstraint(linear_expr, Domain::FromIntervals({ {5, 6}, {8, 10} }))

Java

model.addLinearExpressionInDomain(linear_expr, Domain.fromIntervals(new long[][] { {5, 6}, {8, 10} }))

.Net

model.AddLinearExpressionInDomain(linear_expr, Domain.FromIntervals(new long[][] {new long[] {5, 6}, new long[] {8, 10} }));

Utilizzo di aiutanti delle espressioni lineari

I seguenti esempi mostrano come utilizzare metodi helper per creare somme e prodotti scalari. Ecco alcuni esempi in cui vogliamo x + y == 20 e 4 * x + 2 * y = 56:\

Python

model.Add(x + y == 20)
model.Add(4 * x + 2 * y == 56)

C++

cp_model.AddEquality(LinearExpr::Sum({x, y}), 20);
cp_model.AddEquality(LinearExpr::ScalProd({x, y}, {4, 2}), 56);

Java

model.addEquality(LinearExpr.sum(new IntVar[] {x, y}), 20);
model.addEquality(LinearExpr.scalProd(new IntVar[] {x, y}, new long[] {4, 2}), 56);

.Net

model.Add(x + y == 20);
model.Add(4 * x + 2 * y == 56);

Marzo 2019

Lancio di OR-Strumenti v7.0

Abbiamo rilasciato OR-Strumenti v7.0. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Modifiche alle piattaforme supportate

OR-Tools v7.0 non supporta più le seguenti piattaforme:

  • Visual C++ 2015
  • Ubuntu 14.04
  • Python 3.4 su Linux

Se usi una di queste piattaforme, puoi comunque installare OR-Tools v6.10.

Modifiche alle dipendenze richieste

OR-Tools v7.0 presenta le seguenti dipendenze nuove e aggiornate:

Le seguenti sezioni descrivono le nuove funzionalità e i miglioramenti di OR-Strumenti 7.0.

Nuovo sistema di gestione degli indici per i programmi di routing

In OR-Tools v7.0, i programmi di routing dei veicoli devono utilizzare il nuovo RoutingIndexManager. Ciò garantisce che gli indici standard per le località siano coerenti con gli indici interni utilizzati dal risolutore e contribuisce a evitare errori nel codice.

Il nuovo RoutingIndexManager richiede alcune modifiche di minore entità ai programmi di routing, descritti nelle seguenti sezioni:

Includi/importa RoutingIndexManager

In OR-Tools 7.0, i programmi di routing in C++ e Java devono includere o importare RoutingIndexManager come mostrato negli esempi seguenti:

C++

#include "ortools/constraint_solver/routing_index_manager.h"

Java

import com.google.ortools.constraintsolver.RoutingIndexManager;

Le importazioni Python e C# non sono state modificate.

Dichiara RoutingIndexManager

In OR-Tools v7.0, i programmi di routing devono dichiarare RoutingIndexManager e creare il modello di routing, come mostrato negli esempi seguenti:

Python

manager = pywrapcp.RoutingIndexManager(num_locations, num_vehicles, depot)
routing = pywrapcp.RoutingModel(manager)

C++

RoutingIndexManager manager(num_locations, num_vehicles, depot);
RoutingModel routing(manager);

Java

RoutingIndexManager manager = new RoutingIndexManager(numLocations, numVehicles, depot);
RoutingModel routing = new RoutingModel(manager);

.Net

RoutingIndexManager manager = new RoutingIndexManager(numLocations, numVehicles, depot);
RoutingModel routing = new RoutingModel(manager);

Gli argomenti per RoutingIndexManager sono:

  • Il numero di sedi
  • Il numero di veicoli
  • L'indice del deposito (località di partenza e di arrivo per tutti i veicoli)

Callback

In OR-Tools v7.0, devi utilizzare RoutingIndexManager per creare callback, ad esempio il callback di distanza, che poi passi al risolutore. I seguenti esempi mostrano come creare un callback di distanza.

Python

    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

C++

  const int transit_callback_index = routing.RegisterTransitCallback(
      [&data, &manager](const int64_t from_index,
                        const int64_t to_index) -> int64_t {
        // Convert from routing variable Index to distance matrix NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        const int to_node = manager.IndexToNode(to_index).value();
        return data.distance_matrix[from_node][to_node];
      });
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

Java

    final int transitCallbackIndex =
        routing.registerTransitCallback((long fromIndex, long toIndex) -> {
          // Convert from routing variable Index to user NodeIndex.
          int fromNode = manager.indexToNode(fromIndex);
          int toNode = manager.indexToNode(toIndex);
          return data.distanceMatrix[fromNode][toNode];
        });
    routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

.Net

        int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
                                                                   {
                                                                       // Convert from routing variable Index to
                                                                       // distance matrix NodeIndex.
                                                                       var fromNode = manager.IndexToNode(fromIndex);
                                                                       var toNode = manager.IndexToNode(toIndex);
                                                                       return data.DistanceMatrix[fromNode, toNode];
                                                                   });
        routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

Il metodo IndexToNode converte gli indici di posizione interni utilizzati dal risolutore negli indici standard per la matrice di distanza.

Anziché passare il callback direttamente al risolutore, come nelle versioni precedenti, nella v7.0 devi prima creare transit&nbsp;callback&nbsp;index, un riferimento al callback, e passarlo al risolutore (in questo caso tramite SetArcCostEvaluatorOfAllVehicles).

Dimensioni

I seguenti esempi mostrano come creare una dimensione per le richieste e le capacità, che viene utilizzata per risolvere il problema di routing dei veicoli abilitati.

Python

    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data["demands"][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data["vehicle_capacities"],  # vehicle maximum capacities
        True,  # start cumul to zero
        "Capacity",
    )

C++

  const int demand_callback_index = routing.RegisterUnaryTransitCallback(
      [&data, &manager](const int64_t from_index) -> int64_t {
        // Convert from routing variable Index to demand NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        return data.demands[from_node];
      });
  routing.AddDimensionWithVehicleCapacity(
      demand_callback_index,    // transit callback index
      int64_t{0},               // null capacity slack
      data.vehicle_capacities,  // vehicle maximum capacities
      true,                     // start cumul to zero
      "Capacity");

Java

    final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
      // Convert from routing variable Index to user NodeIndex.
      int fromNode = manager.indexToNode(fromIndex);
      return data.demands[fromNode];
    });
    routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
        data.vehicleCapacities, // vehicle maximum capacities
        true, // start cumul to zero
        "Capacity");

.Net

        int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
                                                                       {
                                                                           // Convert from routing variable Index to
                                                                           // demand NodeIndex.
                                                                           var fromNode =
                                                                               manager.IndexToNode(fromIndex);
                                                                           return data.Demands[fromNode];
                                                                       });
        routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
                                                data.VehicleCapacities, // vehicle maximum capacities
                                                true,                   // start cumul to zero
                                                "Capacity");

Soluzioni di stampa

In OR-Tools v7.0, devi utilizzare RoutingIndexManager per visualizzare i percorsi del veicolo in una soluzione. Gli esempi riportati di seguito mostrano come stampare soluzioni in tutte le lingue supportate.

Python

def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    index = routing.Start(0)
    plan_output = "Route for vehicle 0:\n"
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += f" {manager.IndexToNode(index)} ->"
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += f" {manager.IndexToNode(index)}\n"
    plan_output += f"Distance of the route: {route_distance}m\n"
    print(plan_output)

C++

//! @brief Print the solution
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const RoutingIndexManager& manager,
                   const RoutingModel& routing, const Assignment& solution) {
  LOG(INFO) << "Objective: " << solution.ObjectiveValue();
  // Inspect solution.
  int64_t index = routing.Start(0);
  LOG(INFO) << "Route for Vehicle 0:";
  int64_t distance{0};
  std::stringstream route;
  while (!routing.IsEnd(index)) {
    route << manager.IndexToNode(index).value() << " -> ";
    const int64_t previous_index = index;
    index = solution.Value(routing.NextVar(index));
    distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
  }
  LOG(INFO) << route.str() << manager.IndexToNode(index).value();
  LOG(INFO) << "Distance of the route: " << distance << "m";
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

Java

  /// @brief Print the solution.
  static void printSolution(
      DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
    // Solution cost.
    logger.info("Objective : " + solution.objectiveValue());
    // Inspect solution.
    logger.info("Route for Vehicle 0:");
    long routeDistance = 0;
    String route = "";
    long index = routing.start(0);
    while (!routing.isEnd(index)) {
      route += manager.indexToNode(index) + " -> ";
      long previousIndex = index;
      index = solution.value(routing.nextVar(index));
      routeDistance += routing.getArcCostForVehicle(previousIndex, index, 0);
    }
    route += manager.indexToNode(routing.end(0));
    logger.info(route);
    logger.info("Distance of the route: " + routeDistance + "m");
  }

.Net

    /// <summary>
    ///   Print the solution.
    /// </summary>
    static void PrintSolution(in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution)
    {
        Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
        // Inspect solution.
        Console.WriteLine("Route for Vehicle 0:");
        long routeDistance = 0;
        var index = routing.Start(0);
        while (routing.IsEnd(index) == false)
        {
            Console.Write("{0} -> ", manager.IndexToNode((int)index));
            var previousIndex = index;
            index = solution.Value(routing.NextVar(index));
            routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
        }
        Console.WriteLine("{0}", manager.IndexToNode((int)index));
        Console.WriteLine("Distance of the route: {0}m", routeDistance);
    }

Supporto per i VRP con ritiri e consegne

OR-Tools v7.0 fornisce supporto per la risoluzione dei problemi relativi al routing dei veicoli (VRP) con ritiro e consegne, in cui l'obiettivo è trovare i percorsi più brevi per un parco di veicoli che ritira e consegna gli articoli in varie località. Imposta il problema in modo simile a un VRP standard, ma oltre a specificare una coppia di località (i, j) per ogni articolo, dove i è il luogo di ritiro e j è il luogo di consegna. Il risolutore di percorso restituisce i percorsi dei veicoli in modo che, per ogni coppia (i, j), i e j, si trovino sullo stesso percorso e il veicolo visiti il percorso i prima del giorno j.

Per un esempio che risolve questo tipo di problema, consulta Routing dei veicoli con pick-up e consegne.

Supporto per le funzioni lambda

OR-Tools v7.0 include ora il supporto per le funzioni lambda in C# e Java (oltre a C++ e Python, già supportati). Le funzioni lambda offrono un modo conveniente per definire i callback nei programmi di routing. Tuttavia, puoi definire i callback utilizzando le funzioni standard se ritieni che il codice renda più leggibile.

Gli esempi di callback C# e Java riportati sopra mostrano come definire i callback utilizzando le funzioni lambda.

Novembre 2018

Annuncio del rilascio della versione v6.10

Abbiamo rilasciato OR-Tools versione 6.10. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Le seguenti sezioni descrivono le nuove funzionalità e i miglioramenti apportati alla versione 6.10.

Comandi semplificati per creare ed eseguire programmi

Nella versione 6.10 puoi creare ed eseguire programmi inserendo comandi come segue: 

make run SOURCE=relative/path/to/program.cc
dove <var>relative/path/to</var> è il percorso della directory contenente il programma.

Per creare un programma senza eseguirlo, inserisci: 

make build SOURCE=relative/path/to/program.cc
Consulta Inizia a utilizzare OR-Strumenti per istruzioni specifiche sull'esecuzione di programmi in base alla lingua.

Supporto per SCIP 6.0.0

OR-Tools ora fornisce supporto per SCIP 6.0.0.

Programmi binari

Le distribuzioni binarie sono state create usando Java JDK 8 (JDK 7 per Ubuntu 14.04).

Risolutore CP-SAT

Aggiorna l'API

  • Aggiungi l'API CpModelBuilder CP-SAT C++.

Esempi

Alcuni esempi sono stati spostati.

  • Sposta gli esempi di community in examples/contrib.
  • Sposta alcuni esempi in ortools/<var>component</var>/samples (ad es. ortools/linear_solver/samples/simple_program.java)

Settembre 2018

Annuncio del rilascio della versione v6.9

Abbiamo rilasciato OR-Tools versione 6.9. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Dipendenze aggiornate

  • Protobuf 3.5.1 -> 3.6.1.
  • SCIP 4.0 -> 6.0.

Risolutore CP-SAT

  • Modifiche che provocano un errore all'API: i dettagli completi sono disponibili qui:
  • Rinomina SolveWithSolutionObserver in SolveWithSolutionCallback in Python.

  • Rinomina NewSolution in OnSolutionCallback nella classe CpSolverSolutionCallback in Python. L'esempio seguente mostra il nuovo modo per creare un callback della soluzione in Python. 

    class MySolutionCallback(cp_model.CpSolverSolutionCallback):
def init(self):
cpmodel.CpSolverSolutionCallback.init(self)
self._solution_count = 0
    


    def OnSolutionCallback(self):
print('Solution {}, time = {}s, objective = {}, makespan = {}'.format(
  self.solution_count,
  self.WallTime(),
  self.ObjectiveValue(),
  self.Value(makespan)))
self.solution_count += 1

  • Esponi StopSearch sul callback della soluzione in Python, Java e C#. La documentazione è disponibile qui.

  • Esponi ModelStats e CpSolverResponseStats in Python, Java e C#.

  • Migliora la documentazione relativa alla docstring Python. La documentazione è disponibile qui.

  • Aggiornamenti all'implementazione Java dell'interfaccia del risolutore e del libro di ricette.

  • Implementa il modulo.

  • Modifica l'implementazione del serbatoio: aggiungi un'API con valore booleano per specificare eventi di svuotamento/riempimento facoltativi.

Linear Solver

  • Esponi InterruptSolve in Java e C#.

Risolutore CP

  • Esponi SolutionCollector regista in C#.

Python

  • Aggiungi il supporto per Python 3.7.
  • Durante la compilazione dal codice sorgente: preferisci python3 rispetto a python2 durante il rilevamento di Python.

.NET

  • Riscrittura completa del livello .NET.
  • Fornisci un pacchetto Nuget Google.OrTools NetStandard 2.0 compatibile con l'identificatore runtime win-x64, linux-x64 e osx-x64.
  • Fornisci un pacchetto Nuget Google.OrTools.FSharp.
  • Aggiungi un file di progetto per tutti gli esempi .NET.
  • Aggiorna tutti gli esempi di script F# (.fsx) in un progetto F# normale (.fs).
  • Aggiungi la documentazione sulla generazione delle build dei pacchetti .NET qui.

Flazinco

  • Aggiungi il supporto per i set in flatzinc (utilizzando nosets.mzn).

Contributi

  • Aggiungi il supporto per Binder. Grazie a Kevin Mader.
  • Imposta DecisionVisitor come tipo di Director nelle associazioni Java. Grazie a Jeremy Apthorp.

Luglio 2018

Annuncio del rilascio della versione v6.8

Abbiamo rilasciato OR-Tools versione 6.8. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Presentazione del risolutore CP-SAT

Il risolutore CP-SAT è un nuovo risolutore per la programmazione di vincoli. Il risolutore CP-SAT è più veloce del risolutore CP originale e dovrebbe essere preferibile per i problemi CP.

Per gli esempi che utilizzano il risolutore CP-SAT, nella directory examples di GitHub cerca i file che contengono _sat nel nome.

Il risolutore CP originale continuerà a essere mantenuto per un certo periodo di tempo per supportare il codice esistente, ma sarà deprecato.

Nuove opzioni per il risolutore CP-SAT

Le seguenti opzioni per il risolutore CP-SAT sono nuove in questa release:

  • Ricerca nel quartiere locale (LNS): usa l'opzione SatParameters.use_lns per attivare LNS.
  • Ricerca parallela: utilizza l'opzione SatParameters.num_search_workers per abilitare più thread durante una ricerca. Ogni thread può avere parametri diversi e seed casuali diversi. Questo massimizza la diversità e la probabilità che almeno un thread trovi soluzioni.

Miglioramenti delle prestazioni per i risolutori

Abbiamo migliorato le prestazioni dei risolutori CP-SAT e Glop.

Marzo 2018

Annuncio del rilascio della versione v6.7

Abbiamo rilasciato OR-Tools versione 6.7. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR.

Aggiorna alle dipendenze richieste

  • Protobuf 3.5.0 -> 3.5.1.

Varie

  • Esegui il refactoring della base per preparare l'integrazione abseil-cpp.
  • Utilizzo dei servizi di integrazione continua (CI) di Travis CI e di Appveyor.

SAT

  • Miglioramento del rendimento.
  • Migliora l'API Python.
  • Aggiungi l'API C# nota anche come CpSolver.cs (SPERIMENTALE).

Glop

  • Refactoring del codice.
  • Miglioramento del rendimento.

Assistenza CMake (SPERIMENTALE)

  • Aggiungi l'assistenza di CMake su C++ OR-Tools.
  • Essere in grado di creare OR-Tools come progetto CMake autonomo.
  • Essere in grado di incorporare OR-Tools in un progetto CMake esistente.
  • Aggiungi la build basata su CMake Python OR-Tools.
  • Genera un pacchetto Python (wheel) utilizzando CMake.

Contributi

  • Correggi la ridefinizione di WHOIS.h sulle finestre. Grazie a Florent Tollin de Rivarol.
  • Aggiungi supporto F# (SPERIMENTALE). Grazie a Matthew Moore. Nota: disponibile solo con il builder di Makefile.
  • Aggiungi il supporto standard .NET (SPERIMENTALE). Grazie a Ziad El Malki. Nota: disponibile solo con il builder di Makefile.

Novembre 2017

Annuncio del rilascio della versione v6.6

Abbiamo rilasciato OR-Tools versione 6.6. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Aggiornamenti alle dipendenze richieste

  • Protobuf a 3.3.0 -> 3.5.0.
  • gflags in 2.2.0 -> 2.2.1.
  • CBC 2.9.8 -> 2.9.9.
  • Aggiungi il modulo Python sei (1.10) come dipendenza richiesta per Python.

Correzioni di bug

  • Richiesta di pull n. 494 Refactoring dei nomi. L'aggiunta di commenti per IntelliSense in alcuni editor. Grazie a Matthew Moore.
  • Istruzione di pull #516 per il programma binario autonomo F#. Grazie a Matthew Moore.
  • Migliora la precisione in Glop.

Risolutore SAT

  • Migliorare il risolutore SAT interno, correggere vari bug.
  • Aggiungi un vincolo VRP al risolutore SAT, collegato al risolutore LP.
  • Cambia l'osservatore della soluzione nel risolutore SAT per utilizzare CpSolverResponse come parametro.
  • Migliora l'utilizzo di Glop nel Risolutore SAT.
  • Velocizza la connessione SAT-LP.
  • Aggiungi il vincolo Reservoir al formato SAT cp_model protobuf.

SAT/Python

Esempi

  • Riscrivi rcpsp_parser per utilizzare il formato ProtoBuf per archiviare il problema.
  • Migliora il parser RCPSP.

Ottobre 2017

Annuncio del rilascio della versione v6.5

Abbiamo rilasciato OR-Tools versione 6.5. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Variazione nelle piattaforme

  • Il modulo pypi py3-ortools è stato unito nel modulo ortools. Ora esiste un solo modulo: "ortools".
  • Il formato principale di questi moduli Python ora sono i file wheel. Per installare OR-Tools per Python da pypi, esegui pip install ortools. È necessaria una versione recente di pip installata (>= 9.0.1). Ciò dovrebbe generare il pull della release più recente (v6.5).

Bug fixed

Il file jar protobuf ora viene creato correttamente con le classi compilate.

Nuovi esempi

  • Sono stati aggiunti altri esempi F# alla directory example/fsharp (grazie ancora a Matthew Moore).
  • Sono stati aggiunti anche esempi di MIP in Java (Grazie Darian).

Settembre 2017

Annuncio del rilascio della versione v6.4

Abbiamo rilasciato OR-Tools versione 6.4. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Variazione nelle piattaforme

  • I moduli Pypi sulle piattaforme Linux vengono ora pubblicati come file wheel utilizzando il tag Manylinux1. Grazie a Federico Ficarelli. In seguito a questa modifica, abbiamo eseguito il backtracciamento dei moduli per Linux introdotti nella release di luglio 2017.

Nuove funzionalità

  • Metodo di scalabilità migliorato utilizzato in GLOP.
  • Correggi il wrapping dei valutatori nella libreria di routing C#. Grazie a DevNamedZed.
  • Migliora le prestazioni della presolvenza flatzinc per i modelli di grandi dimensioni.
  • Per impostazione predefinita, utilizza il supporto SAT per flatzinc.
  • Migliorare le prestazioni dell'approccio basato su core per il risolutore sat.
  • Correggere un bug nell'algoritmo di assegnazione lineare che non funzionava correttamente.
  • Sono stati aggiunti gli esempi F# in ortools/examples/fsharp.
  • Rimuovi il segno di spunta per penalità positive nella libreria di routing.

Agosto 2017

Annuncio del rilascio della versione v6.3

Abbiamo rilasciato OR-Tools versione 6.3. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Nuovi file scaricati

I file wheel Python per Linux sono ora disponibili per il download nella pagina di rilascio di OR-Tools, insieme alle versioni più recenti di tutti i download.

Risolutore di zinco

Questa versione contiene il codice sat e flatzinc finale inviato per la sfida Minizinc 2017.

Luglio 2017

Annuncio del rilascio della versione v6.2

Abbiamo rilasciato OR-Tools versione 6.2. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Variazione nelle piattaforme

  • Ora supportiamo più distribuzioni binarie Linux (Ubuntu 14.04, 16.04, 17.04, CentOS 7, Debian 9).
  • I moduli Pypi sulle piattaforme Linux ora includono un tag che descrive la distribuzione (ubuntu-14.04, ubuntu-16.04, ubuntu-17.04, centos-7, debian-9).

Nuove funzionalità

Abbiamo aggiunto il supporto per Docker per la creazione di artefatti di Linux. Vai a or-tools/tools/docker e guarda Makefile per vedere i possibili target (make archive, make pypi e make pypi3).

Questi comandi creano una sottodirectory export e aggiungono artefatti binari al suo interno.

Giugno 2017

Annuncio del rilascio della versione v6.1

Abbiamo rilasciato OR-Tools versione 6.1. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Variazione nelle piattaforme

  • Visual Studio 2017 è supportato; Visual Studio 2013 non è più supportato.
  • macOS 10.9 e versioni successive sono supportate.

Nuove funzionalità

Abbiamo aggiunto un nuovo formato protobuf per il risolutore CP-SAT. Leggi ortools/sat/cp_model.proto per definire il modello e ortools/sat/cp_model_solver.h per risolvere il problema.

Correzioni di bug

Questione n. 420: abbiamo corretto l'attributo __version__ mancante sui moduli pypi Python su tutte le piattaforme.

Maggio 2017

Annuncio del rilascio della versione v6.0

Abbiamo rilasciato OR-Tools versione 6.0. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Nuova struttura di directory in C++

Abbiamo modificato la struttura di origine/inclusione degli strumenti OR quando si utilizza C++. L'obiettivo è fornire un incapsulamento migliore dei file di inclusione di C++. Ha anche il vantaggio di allineare le strutture delle directory C++ e Python.

  • src/ è stato rinominato in ortools/.
  • A tutti i comandi #include nei file C++ viene aggiunto il prefisso ortools. #include "constraint/constraint_solver.h" ora è #include "ortools/constraint/constraint_solver.h".

Nuove funzionalità

  • Assistenza Bazel. Ora puoi creare OR-Strumenti con bazel, lo strumento di creazione di Google. Funziona su Linux e Mac OS X. Dopo aver scaricato Bazel versione 0.4.5 o successive, cambia la directory in or-tools e crea gli esempi: bazel build examples/cpp/....

Routing

Nella libreria dei percorsi, abbiamo implementato il supporto per le pause (ad es. tempi di inattività del veicolo dovuti al pranzo con i conducenti). Questa funzionalità è mostrata nell'esempio di cvrptw_with_breaks.cc.

Supporto SCIP

Il wrapper del risolutore lineare ora supporta SCIP 4.0. Ora devi prima creare SCIP e poi indicare agli strumenti che lo utilizzerai. Le istruzioni sono disponibili qui.

Supporto di GLPK

Abbiamo anche cambiato il modo di usare le build con GLPK. Leggi qui.

Pulizia

  • Abbiamo rimosso qualsiasi utilizzo di hash_map e hash_set dal codebase C++ poiché sono deprecati. Sono stati sostituiti da unordered_map e unordered_set da STL.
  • Pulizia dei makefile di C#, gentilmente concessa da Michael Powell.

Gennaio 2017

Annuncio del rilascio della versione v5.1

Abbiamo rilasciato OR-Tools versione 5.1. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Nuove funzionalità

Installazione in corso…

Routing

È stato implementato un algoritmo per calcolare il limite inferiore di Held-Karp per i problemi simmetrici dei venditori in viaggio. Ciò consente di calcolare un limite superiore per il divario tra il costo di una soluzione potenzialmente non ottimale e il costo della soluzione ottimale.

  • È stato aggiunto un nuovo metodo alla libreria di percorsi dei veicoli, RoutingModel::SetBreakIntervalsOfVehicle, che ti consente di aggiungere intervalli di break, ovvero periodi di tempo in cui un veicolo non può svolgere alcuna attività (come viaggiare o visitare un nodo). Per un esempio in cui viene utilizzata questa opzione, vedi cvrptw_with_breaks.cc

Programmazione

Risolutore di Sat

Miglioramenti del rendimento

  • Risolutore SAT: prestazioni del risolutore Sat migliorate, in particolare per quanto riguarda il vincolo cumulativo.
  • Risolutore glop: robustezza numerica del risolutore glop migliorata, che ora restituisce soluzioni ancora più precise a problemi numerici difficili.
  • Risolutore di flazinco
  • Prestazioni del backend Sat notevolmente migliorate per l'interprete flatzinc.
  • È stata semplificata l'interfaccia di C# flatzinc. Per un esempio della nuova interfaccia, consulta la pagina https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs.

Correzioni di bug

  • L'utilizzo dell'euristica PathCheapestArc sui modelli di routing con un solo veicolo e vincoli laterali, a volte causa un tempo di esecuzione del risolutore troppo lungo. Questo problema è stato risolto prendendo correttamente in considerazione i vincoli secondari.
  • In Java, a volte il risolutore di percorso si arrestava in modo anomalo durante la risoluzione dei problemi di routing dei veicoli. Questo problema è stato risolto nell'ultima release.

Novembre 2016

Annuncio del rilascio della versione v5.0

Abbiamo rilasciato OR-Tools versione 5.0. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Esempi in esecuzione

  • Sono stati introdotti target specifici per lingua che semplificano la compilazione e l'esecuzione dei programmi, oltre agli esempi forniti con OR-Tools.

Sab

FlatZinc

Risolutore dei vincoli

Routing

  • È stato implementato AddAtSolutionCallback, ovvero un callback che viene chiamato ogni volta che viene trovata una soluzione durante la ricerca.
  • Rimossi i costruttori senza deposito RoutingModel. Ora è obbligatorio specificare almeno un deposito nel modello di routing.

Settembre 2016

Annuncio del rilascio della versione v4.4

Abbiamo rilasciato OR-Tools versione 4.4. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Sab

  • API di pianificazione estesa ed esempi modificati (weight_tardiness_sat e jobshop_sat) per utilizzarla.

Grafico

  • Sono stati aggiunti trait iteratori alle classi Graph.

Distribuzione OR-Strumenti

  • Il pacchetto Nuget è di nuovo supportato.

Agosto 2016

Annuncio del rilascio della versione v4.3

Abbiamo rilasciato OR-Tools versione 4.3. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Risolutore dei vincoli

  • Il metodo NotBetween è stato implementato per vincolare una variabile al di fuori di un determinato intervallo.

calcolo itinerario

  • È stata aggiunta un'analisi del modello per controllare i vincoli NotMember esistenti come mostrato in questo esempio e utilizzarli nei filtri di ricerca locale.
  • È stata aggiunta la profilazione della ricerca locale.
  • Correzione per gli spostamenti locali.

Risolutore lineare

  • Report sullo stato SCIP corretti.

Sab

Glop

  • Sono state migliorate le prestazioni sfruttando la sparsità in più fasi di calcolo.

Flazinco

  • Sono stati corretti bug rilevati dalla sfida Minizinc.

Lp_data

  • Semplificazione continua dei modelli negli iteratori.

Distribuzione OR-Strumenti

  • Gli assiemi C# ora hanno un nome sicuro per impostazione predefinita.
  • Aggiornato a Protobuf3.0.0.
  • È stato aggiunto uno script Python per controllare le dipendenze di archiviazione di OR-Tools.

Luglio 2016

Annuncio del rilascio della versione v4.2

Abbiamo rilasciato OR-Tools versione 4.2. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Risolutore dei vincoli (routing)

  • Una disgiunzione ora può essere definita con una cardinalità, che è il numero massimo di nodi che possono essere attivi all'interno di questa disgiunzione. Ad esempio, se aggiungi una disgiunzione con n nodi e una cardinalità k, possono essere attivi i nodi k tra gli n nodi. A questo scopo, puoi utilizzare la nuova definizione di AddDisjunction.
  • Aggiunto il supporto per più disgiunzioni per nodo. Ad esempio, ora puoi aggiungere un nodo N1 a molte disgiunzioni (D1..Dm). Ciò aumenta le possibilità di essere attivo all'interno di uno qualsiasi di essi. È stato introdotto un algoritmo di ricerca dei percorsi più veloce per i problemi relativi alle finestre temporali di disgiunzione.
  • Sono stati aggiunti parametri del risolutore di vincoli ai parametri del modello di routing e log_search ai parametri di ricerca di routing.
  • L'algoritmo di ricerca locale è più veloce nella risoluzione dei problemi con finestre temporali disconnesse. Consulta l'esempio cvrp_disjoint_tw.cc per ulteriori dettagli.

Glop (ottimizzazione lineare)

  • È stato introdotto un algoritmo Simplex più veloce.

Distribuzione OR-Strumenti

  • Un archivio per piattaforma, invece che singoli archivi per ognuno degli archivi C++, Java e .Net. Gli archivi Python sono ancora ospitati su pypi.
  • Su Pypi, siamo passati ai moduli wheel (.whl) su Mac OS X e Windows. È stato introdotto uno schema di numerazione MAJOR.MINOR. Questi numeri vengono utilizzati i nomi degli archivi, la versione archiviata nelle librerie condivise di Mac OS X, i moduli Python e gli assiemi .NET. La prima versione che stiamo rilasciando è con questo schema la v4.2

Giugno 2016

Annuncio del rilascio della versione v2016-06

Abbiamo rilasciato la versione v2016-06 di OR-Tools. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Risolutore dei vincoli

  • Rimossa la maggior parte delle istanze dei callback (src/base/callback.h) dalla libreria CP.
  • Aggiunto NotMemberCt (la variabile non può appartenere a un insieme di intervalli).

Libreria di routing

  • MODIFICA INCOMPATIBILE: per specificare la capacità dei veicoli in AddDimensionWithVehicleCapacity, ora devi passare un array (un vettore in c++) anziché un callback.

GLOP

  • Cambia la rappresentazione interna della matrice sparsa.
  • Miglioramenti delle prestazioni.

Grafico

  • Riscrivi gli algoritmi di Dijkstra e Bellman-Ford per sostituire i callback di std::function (C++).
  • Cambia l'API dell'implementazione dei grafici diversi durante l'iterazione su archi e nodi.

Sab

  • Rimuovi il metodo principale inutilizzato (nodi di risoluzione).
  • Aggiunta di drat writer per controllare le prove dell'insoddisfabilità.
  • Aggiungi preprocessore.

Pupù

  • Aggiungi nuovi quartieri.

Esempi

  • c++: eliminare il filelinereader negli esempi.
  • data: aggiungi problemi di pianificazione su una singola macchina.

Documentazione

Aprile 2016

Annuncio del rilascio della versione v2016-04

Abbiamo rilasciato la versione v2016-04 di OR-Tools. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Dipendenze aggiornate

Dicembre 2015

Annuncio del rilascio della versione v2015-12

Abbiamo rilasciato la versione v2015-12 di OR-Tools. Per aggiornare la tua versione, consulta la sezione appropriata di Installazione di OR-Strumenti.

Risolutore dei vincoli

  • Compatibilità interrotta con la ricerca di grandi quartieri nel risolutore CP (vedi examples/cpp/ls_api.cc, examples/python/pyls_api.py, examples/csharp/csls_api.cs e examples/com/google/ortools/sample/LsApi.java per vedere la nuova API).
  • È stato pulito il wrapping Python. Supporta la decisione personalizzata nel risolutore CP (vedi examples/test/test_cp_api.py per vedere l'API in azione).
  • Miglioramenti vari e correzione di diversi bug.

Settembre 2015

Annuncio della prima release su GitHub.

D'ora in poi i file verranno archiviati lì.

Flazinco

  • Aggiunti archivi binari per l'interprete di flatzinc (visita il sito www.minizinc.org).
  • Contiene alcune correzioni alla versione utilizzata nella sfida.