Notas da versão das ferramentas OR

Nesta página, listamos as mudanças nas ferramentas OU, incluindo novos recursos, correções de bugs e melhorias no código e nos procedimentos de instalação.

Se você tiver problemas ao instalar as ferramentas OR, consulte a seção Solução de problemas nas instruções de instalação das ferramentas OR. Se o seu problema não estiver listado, verifique os problemas no GitHub ou abra um novo e ficaremos felizes em ajudar.

Veja a seguir as notas da versão do OR-Tools, começando pela versão mais recente.

Maio de 2024

Anúncio do lançamento do OR-Tools v9.10

Lançamos o OR-Tools v9.10. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Encontre a nota da versão no github (link em inglês).

março de 2024

Anúncio do lançamento do OR-Tools v9.9

Lançamos o OR-Tools v9.9. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Encontre a nota da versão no github (link em inglês).

Novembro de 2023

Anúncio do lançamento do OR-Tools v9.8

Lançamos o OR-Tools v9.8. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças na plataforma

  • Adicione o Python 3.12.
  • Adicionar suporte para o Ubuntu 23.10

Solucionador linear

  • Porta ModelBuilder para .Net.
  • LogCallback foi renomeado como MbLogCallback para evitar colisões com o LogCallback da SAT
  • Estender a API ModelBuilder:
    • Adicionar restrições de indicador
    • Foi adicionado suporte a dicas.
    • Adicionar clonagem de modelo.

Opção matemática

  • Retrabalho profundo.

Roteamento

  • Adiciona o status ROUTING_OPTIMAL.
  • Torne RoutingModel não copiável nem móvel.
  • Correção de algum loop infinito nos operadores de pesquisa local.
  • Adição de um struct interno PickupDeliveryPosition.
  • Adição dos métodos IsPickup() e IsDelivery().

SÁB

  • Reduz o consumo de memória para modelos grandes.
  • Pesquisa de programação aprimorada.
  • adicione packing_precedences_lns.
  • otimizar e corrigir o salto de viabilidade.
  • Otimização linear da solução e melhor geração de registros.
  • Melhoria na resolução de int_abs, int_mod, int_prod e lin_max
  • Melhorar o suporte ao Panda
  • Poucas correções de bugs.

Registro de alterações do GitHub

Agosto de 2023

Anúncio do lançamento do OR-Tools v9.7

Lançamos o OR-Tools v9.7. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças na plataforma

  • Drop Centos-8 (EOL).
  • Abandone o Debian 10.
  • Remova o Fedora [33, 36] (EOL).
  • Descarte o Ubuntu 18.04 LTS (EOL).
  • Lançamento do Python 3.7 (EOL).
  • Desative o suporte a netcore3.1 no CMake (EOL).

Criador de modelos Python

  • Permitir o uso de conjuntos de dados e séries do Pandas para criar variáveis.
  • Preencha as informações de digitação

PDLP

  • diversas atualizações.

CP-SAT

  • Melhorias de desempenho. (viabilidade_salto, lin_max)
  • Melhore o gerenciamento de cortes
  • Novo worker Object_shave_search dedicado a melhorar o limite inferior do objetivo (ao minimizar)
  • Anotações de digitação para o cp_model.py do Python
  • Suporte parcial experimental para pandas em cp_model.py
  • Funcionários experimentais com base em violação da pesquisa local:
    • ativado com parâmetros: num_violation_ls:xxx
    • otimizado para modelo linear (linear, bool_or, bool_and, at_most_one, exactly_one)
    • funciona corretamente com lin_max, product, division
    • suporta no_overlap, cumulativo, circuito, rotas
    • desativado com no_overlap_2d
    • número recomendado de workers ls: num_workers -> num_violation_ls: (8, 1), (16, 2) (24, 3), (32, 4)

Registro de alterações do GitHub

Março de 2023

Anúncio do lançamento do OR-Tools v9.6

Lançamos o OR-Tools v9.6. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças na plataforma

  • Foi adicionado suporte ao Fedora 37, 38.
  • Solte o Python 3.6 (incompatível com protobuf).
  • Solte o Python 3.7 no macOS (incompatível com scipy).
  • Foi adicionado suporte a net7.0 no CMake (use -DUSE_DOTNET_7=ON).
  • Inclua netcore3.1 em pacotes nuget .org

Dependências

  • SCIP v801 -> v803 (observação: agora o SCIP usa uma licença compatível com OSI)
  • racha 20220623.1 -> 20230105.0
  • Protobuf v21.5 -> v21.12
  • ALTERNAR 4.1.1
  • JNA Java 5.11.0 -> 5.12.1

Bazel

  • Foi adicionado suporte a pybind11.
  • Adicionado suporte a wrapper Java.

Solucionadores

  • PDLP: "dd python wrapper".
  • CP-SAT: Melhorias no desempenho.
  • GLOP: Ajuste o presolve.
  • ModelBuilder: Python: melhoria do suporte a numpy
  • Roteamento: melhorias no desempenho (pesquisa local)

Problemas conhecidos:

  • CP-SAT: ignorar o subsolidador pseudo_costs retorna parâmetros inválidos (consulte 3706, link em inglês).

Novembro de 2022

Anúncio do lançamento do OR-Tools v9.5

Lançamos o OR-Tools v9.5. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças na plataforma

  • Inclusão do suporte ao Debian Sid.
  • Adicionado suporte ao Fedora 35, 36.
  • Adicionar suporte para Ubuntu 22.10.
  • Solte o Python 3.6 no macOS.
  • Adicionar suporte ao Python 3.11.

Atualização de dependências

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

CP-SAT

  • Melhorias na solução: max(array), as restrições booleanas e as restrições lineares.
  • A pesquisa intercalada deve ser determinista em paralelo.
  • Cortes lineares: cortes quadrados de limpeza e int_prod; pipeline de corte de regravação.
  • Modelo e solução de entrada de impressão digital (visíveis no registro).
  • Melhorias na programação.
  • O grupo normal de correções de bugs (falha durante a solução, falhas em cortes, soluções inviáveis, modelo inviável no LNS).

GLOP

  • Acelere ao reescrever a álgebra linear, bem como a regra de seleção dinâmica.

Solucionador linear

  • Adição do knapsack_interface.cc.
  • Mova a API model_builder para o diretório linear_solver (cabeçalhos e amostras).
  • Foi adicionado suporte ao Gurobi 10.

Roteamento

  • Liberação de poucos analisadores para vários desafios de roteamento.

Agosto de 2022

Anúncio do lançamento do OR-Tools v9.4

Lançamos o OR-Tools v9.4. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Plataformas

  • Adicione o suporte ao Debian-10 (consulte #3029).
  • Adicione suporte ao Ubuntu 22.04 LTS (consulte #3276). Observação: não haverá suporte ao .Net 3.1 (consulte dotnet/core#7038).
  • Remoção do suporte ao Ubuntu 21.10.

Diversos

  • O arquivo foi dividido por idiomas e a configuração do CMake foi adicionada à do C++ (#3200).

Gráfico

Dividir ortools.graph.pywrapgraph em:

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

Isso permite usar o numpy para acelerar a configuração dos problemas.

CP-SAT

Melhorias em:

  • Programação (propagação, cortes, limites inferiores).
  • MaxSAT (presolve, heurística baseada no núcleo).
  • Desempenho do MIP (presolve, cortes).

Março de 2022

Anúncio do lançamento do OR-Tools v9.3

Lançamos o OR-Tools v9.3. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças na plataforma

  • Remoção do suporte a Debian-10.
  • Remoção do suporte ao Ubuntu-16.04.
  • Solte o .NET Framework 4.5.2.

Atualização de dependências

  • O Eigen 3.4.0 foi adicionado.
  • Adição do 2021-11-01 do Google re2.
  • Protobuf 3.19.1 -> 3.19.4.
  • SCIP 7.0.1 -> v800.

Python

  • Adição de pybind11.

Recursos

  • O PDLP foi adicionado como experimental.
  • Adição de MathOpt como experimental

CP-SAT

  • Algumas APIs foram renomeadas para fins de consistência, por exemplo, LinearExpr.ScalProd. -> LinearExpr.WeightedSum.
  • Adição de métodos AddAtLeastOne/AddAtMostOne/AddExactlyOne.
  • Adicionar AddMultiplicationConstraint(z, x, y) em todos os idiomas.
  • Adicionar AddMultipleCircuit() em todos os idiomas.

C++

  • Usuário explícito IntVar(BoolVar).
  • LinearExpr::Add* foi removido e substituído pelo operador, por exemplo, LinearExpr +=.
  • Adicionar operadores aritméticos em uma expressão linear.
  • LinearExpr::BooleanSum/BooleanScalProd foi removido. Use Sum/WeightedSum
  • Adicione CpModelBuilder::FixVariable(), que substitui o domínio da variável por um único valor.

Java

  • Reescreva LinearExpr e adicione uma classe builder incremental: LinearExpr.newBuilder().add(x).addSum(<array of variables>).build().
  • Siga a API C++: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment e ForbiddenAssignment agora retornam uma classe especializada com API incremental para adicionar novas variáveis, termos, demandas...

C

  • Documentar todos os métodos.
  • Siga a API C++: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment e ForbiddenAssignment agora retornam uma classe especializada com API incremental para adicionar novas variáveis, termos, demandas...
  • A classe LinearExprBuilder foi adicionada para criar expressões de maneira incremental.

Sistema de compilação

CMake

  • Exige pelo menos o CMake >= 3.18.

Fabricante

  • Agora use o build baseado no CMake internamente.

Dezembro de 2021

Anúncio do lançamento do OR-Tools v9.2

Lançamos o OR-Tools v9.2. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças na plataforma

  • Adicione suporte para o Ubuntu 21:10 (última versão contínua).

Atualização de dependências

  • Atualização do .Net TFM para net5.0 -> net6.0 (necessita do .Net SDK 6.0 LTS e do .Net SDK 3.1 LTS).
  • abseil-cpp 20210324.2 -> 20211102.0.
  • Protobuf 3.18.0 -> 3.19.1.
  • Googletest 1.10.0 -> 1.11.0
  • Python: adicione numpy >= 1.13.3.
  • No MacOS, compile o Coin-OR em -O1 para evitar falhas nos executores.

Roteamento

  • Melhoria nos filtros.
  • Melhorar a heurística da primeira solução.
  • Melhore as posições de intervalo de tempo.

CP-SAT

Alterações importantes

  • O buffer de protocolo subjacente é incompatível com versões anteriores. Qualquer buffer de protocolo armazenado precisará ser gerado novamente com as APIs do builder atualizadas (em C++, Python, Java e .NET).
  • Em particular, o protobuf de intervalo foi limpo à medida que removemos os campos antigos ( start, size e end) e renomeamos os novos (usando _view) para usar o nome dos campos removidos.

Novos recursos

  • As restrições all_different, reservoir, modulo, multiplication e division aceitam expressões afins (a * var + b) em todos os lugares em que exigem variáveis inteiras.
  • O objetivo aceita coeficientes de ponto flutuante. Consulte a classe DoubleLinearExpr em C++/Java/.NET. Veja o exemplo knapsack_2d_sat.py em Python.
  • A restrição no_overlap_2d é compatível com intervalos opcionais.
  • A API C++ implementa os operadores + e * para criar expressões.

Melhorias

  • Melhoria no código presolve.
  • Verificador de modelos mais estrito.
  • Restrição de reservatório.
  • Adicione cortes intensos para a restrição no_overlap_2d.
  • Melhoria no relaxamento linear das restrições de codificação (literal implies var == value).

Métodos descontinuados e removidos

  • O uso de BooleanSum e BooleanScalProd do C++ foi descontinuado. Basta usar Sum e ScalProd.
  • Remoção de AddLinMinEquality e AddLinMaxEquality do C++. Basta usar AddMinEquality e AddMaxEquality.

Futuras incompatibilidades

  • No futuro, reescreveremos a camada de modelagem do Java para ficar mais próxima da camada C++.
  • Na camada de modelagem do C++, tornaremos o filtro IntVar(BoolVar var) explícito.
  • Estamos pensando em tornar a API Python compatível com PEP 8 (usando nomes do Snake_case). Se isso acontecer, forneceremos um arquivo sed para transferir o código.

Sistema de compilação

Bazel

  • O build do Windows foi corrigido.

CMake

  • Adicione a opção FETCH_PYTHON_DEPS (o padrão é ON).
  • Foi adicionado suporte opcional para o solucionador GPLK (padrão -DUSE_GLPK=OFF).

Python

  • Compatibilidade com números inteiros numpy na maior parte da API CP-SAT.
  • Correção do __version__ ausente

Setembro de 2021

Anúncio do lançamento do OR-Tools v9.1

Lançamos o OR-Tools v9.1. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças na plataforma

  • Python: use a imagem manylinux2014 (consulte PEP 599).
  • Python: adicione suporte para o Linux aarch64 usando a imagem manylinux2014_aarch64.
  • .Net: adicione suporte para .Net 5.0.

Atualização de dependências

  • abseil-cpp 20210324.1 -> 20210324.2.
  • Protobuf 3.15.8 -> 3.18.0.
  • SCIP 7.0.1 -> mestre.
  • Googletest 1.8.0 -> 1.10.0
  • python: uso de warning em cp_model.py (consulte 2530, link em inglês).
  • python: absl-py 0,11 -> 0,13

CMake

  • A versão mínima do aumento é necessária 3.14 -> 3.15 (consulte #2528).
  • Python: promoção da versão mínima necessária 3.14 -> 3.18 (consulte #2774).

Fabricante

O build baseado em Make foi descontinuado. Migre para o CMake ou o Bazel para criar usando a origem.

Java

  • Melhoria na robustez do carregador de biblioteca nativa (consulte 2742, link em inglês).
  • Foi corrigida a falha do Coletor de lixo da JVM ao descartar o modelo de roteamento ou o solucionador de restrições (consulte 2091, link em inglês) (consulte 2466, link em inglês).
  • Foi corrigida a falha de callback de geração de registros do CP-SAT ao usar vários workers (consulte 2775, link em inglês).

CP-SAT

  • Melhore a robustez do código LNS (consulte #2525).
  • Melhoria no código de programação: novos métodos de fábrica para criar intervalos de tamanho fixos, novas heurísticas de pesquisa, solução aprimorada e novos cortes lineares
  • Melhoria no código de roteamento: novo LNS dedicado.
  • Melhoria no verificador de modelos. Agora ele é mais pedantístico, especialmente sobre possíveis overflows.
  • Melhoria do código MIP: melhor resolução e várias melhorias no relaxamento linear dos modelos de MIP e CP.
  • Melhorar a diversidade de pesquisa. Ao usar mais de 12 workers, adicione workers dedicados a melhorar o limite inferior do objetivo.
  • Mude para o código de paralelismo: por padrão, o solucionador usará todos os núcleos disponíveis. Use num_search_parameters para especificar o nível de paralelismo.
  • O uso de SearchAllSolutions e SolveWithSolutionCallback foi descontinuado.
  • API Python: verificações mais pedantísticas ao usar var == ... ou var != ... fora de uma chamada model.Add().

Abril de 2021

Anúncio do lançamento do OR-Tools v9.0

Lançamos o OR-Tools v9.0. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Atualizações de dependência

Java

Correções de bugs

  • Melhoria no uso de várias linhas de execução ao usar o solucionador CP-SAT (consulte #1588).
  • O suporte ao wrapper Python de std::vector&ltstd::string&gt foi corrigido (consulte #2453).
  • O suporte ao CPLEX foi reformulado (consulte #2470).

Alteração interruptiva conhecida

  • Adicione o acesso de logger em Python, Java e .Net (consulte #2245).
  • Substituição de todos os tipos personalizados do Google pelos fornecidos em cstdint.

CP-SAT

  • Os métodos SearchForAllSolutions(), SearchAllSolutions() e SolveWithSolutionCallback() foram descontinuados. Use Solve().
  • Melhoria no suporte aos operadores padrão do Python. Isso pode corromper códigos incorretos.

Março de 2021

Anúncio do lançamento do OR-Tools v8.2

Lançamos o OR-Tools v8.2. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Atualizações de dependência

  • Abseil-cpp 20200923.2 atualizado para 20200923.3 LTS.
  • Protobuf 3.14.0 atualizado para 3.15.3.

Roteamento

  • Os elementos RoutingModel.RegisterTransitMatrix() e a RoutingModel.RegisterUnaryTransitVector() foram adicionados.
  • Mude o retorno de RoutingModel.AddVectorDimension() e RoutingModel.AddMatrixDimension() para std::pair&ltint, bool&gt, em que int é o ID do avaliador do transporte público.

Dezembro de 2020

Anúncio do lançamento do OR-Tools v8.1

Lançamos o OR-Tools v8.1. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Atualizações de dependência

  • Abseil-cpp 20200923 atualizado para 20200923.2 LTS.
  • Protobuf 3.13.0 atualizado para 3.14.
  • Adicionar suporte ao Gurobi 9.1.0
  • Remover dependência GLog (substituída por uma implementação personalizada dependendo das sinalizações abseil-cpp)
  • Remover dependência GFlag (substituída pelo componente de sinalizações abseil-cpp)

Correções de bugs

  • A contagem dupla da licença flutuante Gurobi foi corrigida (consulte #2227).
  • O build do Windows foi corrigido (consulte #2200).

Outubro de 2020

Anúncio do lançamento do OR-Tools v8.0

Lançamos o OR-Tools v8.0. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças na plataforma

  • Foi adicionado suporte ao Python 3.9 (#2187).
  • Compatibilidade com Python 3.5 removida (#2186). <!-- Aguardando suporte para o Microsoft dotnet-sdk. Pode ser gerado após o lançamento...
    • Foi adicionado suporte para o Ubuntu 20.10 (#2188) -->
  • A compatibilidade com o Ubuntu 16.04 LTS foi removida (#2188).
  • Suporte reduzido para o Ubuntu 19.10 (2188, link em inglês)

Atualizações de dependência

  • Abseil-cpp 20200225.2 atualizado para 20200923 LTS.
  • Protobuf 3.12.2 atualizada para 3.13.0.

Alteração interruptiva conhecida

  • Agora, o roteamento e o código-fonte CP-SAT usam alguns recursos C++17. Aviso: se você fornecer sua própria versão do abseil-cpp, verifique se ela foi criada em C++17.
  • A assinatura MPSolver::CreateSolver foi alterada. O argumento de nome do modelo foi descartado.

CMake

  • Correção da desativação do suporte a SCIP ao usar -DUSE_SCIP=OFF (consulte 2129, link em inglês).
  • Integre exemplos e exemplos ao sistema de build do CMake. Observação: é possível desativar usando -DBUILD_SAMPLES=OFF e -DBUILD_EXAMPLES=OFF. Observação: é possível desativar para um idioma específico usando -DBUILD_<LANG>_SAMPLES=OFF ou -DBUILD_<LANG>_EXAMPLES=OFF.
    • Com <LANG> entre:
    • CXX,
    • PYTHON,
    • JAVA e
    • DOTNET.

Fabricante

  • Requer Make >= 4.3 (uso da função de avaliação do Make).
  • Exige CMake >= 3.14 (uso da opção -- Details do CMake).
  • Foi adicionada uma opção para desativar o suporte a SCIP usando -DUSE_SCIP=OFF (consulte 2134, link em inglês).
  • Foi adicionada uma opção para desativar o suporte a CLP e CBC usando -DUSE_COINOR=OFF.

Java

  • Agora, as ferramentas OR geram pacotes do Maven (consulte a seção 202).

Correções de bugs

  • O build C++ e Python foi corrigido no FreeBSD (consulte #2126).
  • O build na depuração do Windows foi corrigido (consulte 2077, link em inglês).
  • Foi corrigida uma falha antiga em paralelo no CP-SAT no Windows (consulte 2001, 2019, links em inglês).

Julho de 2020

Anúncio do lançamento do OR-Tools v7.8

Lançamos o OR-Tools v7.8. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Atualizações de dependência

  • O Gurobi 9.0.2 agora é pré-integrado em binários pré-criados. Ele pesquisará a biblioteca compartilhada gurobi 90 no caminho de instalação padrão dos instaladores do Gurobi no MAC OS X e no Windows ou no diretório GUROBI_HOME.
  • O SCIP 7.0.1 agora está integrado em binários pré-criados. Verifique a conformidade com a licença SCIP antes de usá-la.
  • Foi adicionado suporte ao Xpress Solver 8.9.0 opcional.

Solucionador linear

  • Foi adicionado um método LinearSolver::CreateSolver() estático para simplificar a verificação de suporte a back-ends de solucionadores lineares integrados. Funciona em todos os idiomas.

Correções de bugs

  • O build baseado no CMake foi corrigido no FreeBSD.
  • A classificação CP-SAT foi corrigida na geração de cortes cumulativos.
  • Foi corrigido um vazamento de memória do solucionador linear no wrapper .Net.

Junho de 2020

Anúncio do lançamento do OR-Tools v7.7

Lançamos o OR-Tools v7.7. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Atualizações de dependência

  • Abseil-cpp b832dce atualizado para c51510d (LTS 20200225.2).
  • Protobuf 3.11.4 atualizado para 3.12.2.

Novos recursos e melhorias

  • O solucionador CP-SAT agora retorna Optimal em vez de Feasible em um modelo de satisfação (ou seja, sem objetivo).
  • Adição da heurística da bomba de viabilidade da comunidade MIP.

Correções de bugs

Foi corrigida uma falha de várias linhas de execução do CP-SAT (consulte 2005, link em inglês).

Abril de 2020

Anúncio do lançamento do OR-Tools v7.6

Lançamos o OR-Tools v7.6. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Novos recursos do CP-SAT

Adicionamos os seguintes novos recursos ao solucionador CP-SAT:

  • Gerenciamento aprimorado de planos de corte para LPs.
  • Ferramentas de depuração.

Atualizações de dependência

Abseil-cpp 8ba96a8 foi atualizado para b832dce (LTS 20200225).

Correções de bugs

  • Correção do bug de CP-SAT UNSAT em presolve (consulte #1908).
  • O URL swigwin.exe foi corrigido.
  • O gerenciamento de typemap SWIG foi corrigido para Java e .Net.

Janeiro de 2020

Anúncio do lançamento do OR-Tools v7.5

Lançamos o OR-Tools v7.5. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças na plataforma

  • Foi adicionado suporte ao Python 3.8 (#1719).
  • A compilação de suporte a partir de fontes foi removida do Visual Studio 2017 (#1852).
  • Atualização do suporte do Centos 7 para o Centos 8 (#1827).

Atualização de dependência

Correções de bugs

Os problemas a seguir foram corrigidos nas ferramentas OU v7.5. Para uma lista completa, consulte Marco v7.5.

Especificamente, faça o seguinte:

  • Carregamento de assembly fixo. Consulte #1421.
  • Os métodos GetStartIndex() e GetEndIndex() do RouteIndexManager foram expostos (#1843).
  • O SWIG foi corrigido para remover métodos corrompidos (#1838, #1276).

Outubro de 2019

Anúncio do lançamento do OR-Tools v7.4

Lançamos o OR-Tools v7.4. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Novos recursos e melhorias

  • O solucionador de problemas CP-SAT agora verifica se há restrições que não oferecem suporte a literais de aplicação. O verificador de modelos retornará um erro antes de resolver se essa restrição tiver um literal de aplicação.
  • Pesquisa local melhor e mais rápida para a biblioteca de trajetos.
  • O solucionador linear agora oferece suporte ao software de terceiros Xpress-MP. Você precisará recriar as ferramentas OR a partir da origem para usá-las.
  • A arquitetura do pacote NuGet foi completamente reescrita. Mais especificamente, agora ela é compatível com o .NET Framework >= 4.5.2 em plataformas Windows.

Plataforma descontinuada

Conforme anunciado nas notas da versão de julho de 2019, o OR-Tools não é mais compatível com o Python 2.7.

Atualização de dependência

O Protobuf 3.9.0 foi atualizado para 3.10.0.

Agosto de 2019

Anúncio do lançamento do OR-Tools v7.3

Lançamos o OR-Tools v7.3. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Plataforma descontinuada

Estamos descontinuando o suporte ao Python 2.7 para nos alinharmos à migração do Google para o Python 3. Esta será a última versão das ferramentas OR compatíveis com Python 2.7.

Atualização de dependência

O Protobuf 3.8.0 foi atualizado para 3.9.0.

Correções de bugs

Os problemas a seguir foram corrigidos na ferramenta OR v7.3. Para uma lista completa, consulte Kanban v7.3.

Especificamente, faça o seguinte:

  • Correção do problema de transmissão init/int64 no Java (#1448).
  • Correção da verificação de presolve ao processar restrições cumulativas vazias.

Julho de 2019

Anúncio do lançamento do OR-Tools v7.2

Lançamos o OR-Tools v7.2. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças na plataforma

  • Estamos descontinuando o suporte ao Python 2.7 para nos alinharmos à migração do Google para o Python 3. Haverá no máximo mais uma versão do OR-Tools com suporte ao Python 2.7.
  • Ubuntu 18.10 atualizado para o Ubuntu 19.04.
  • Foi adicionado suporte à compilação de fontes no Visual Studio 2019.
  • O Python 3.5 não é mais compatível com o Windows. Use o Python 3.6 ou superior.

Atualizações para dependências

  • Agora, segmentamos CBC 2.10.3.
  • Agora, direcionamos o Protobuf 3.8.0.

CP-SAT

  • Fizemos várias melhorias na pesquisa, no paralelismo e no relaxamento linear.
  • Adição das APIs LinearExpr.Sum() e LinearExpr.ScalProd() no Python
  • As APIs IntVar[].Sum() e IntVar[].ScalProd() foram descontinuadas no C#.
  • C++: o método SolveWithModel() foi removido porque era uma cópia de SolveCpModel().
  • Os métodos CpModel.addGreaterThan() e CpModel.addLessThan() foram adicionados à API Java.

Solucionador linear

  • Adição de MPSolver.SetHint() para Python, Java e C# (compatível com SCIP e Gurobi).
  • MPSolver.SetNumThreads() foi adicionado para Python, Java e C# (compatível com CBC, Gurobi e SCIP).
  • O suporte para SCIP 6.0.1 foi reescrito.

Documentação de referência

  • Adicionamos manuais de referência baseados em doxygen e pdoc3 para todas as linguagens e ferramentas (algoritmos, roteamento, gráfico, linear_solver e CP-SAT). Consulte Manuais de referência das Ferramentas OR.
  • A documentação de referência está completa para C++ (todos os produtos) e CP-SAT (C++, Python, Java).
  • Estamos exportando toda a documentação do C++ para Python e Java.
  • Não há documentação do .NET, e não temos uma solução para melhorar isso no futuro. Mantemos o arquivo porque ele ainda mostra a API disponível.

Maio de 2019

Anúncio do lançamento do OR-Tools v7.1

Lançamos o OR-Tools v7.1. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças nas dependências necessárias

O OR-Tools v7.1 tem as seguintes dependências novas e atualizadas:

  • glog v0.3.5 atualizado para v0.4.0
  • protobuf v3.6.1 atualizado para v3.7.1
  • Cbc 2.9.9 atualizado para 2.10.1
  • Cgl 0.59.10 atualizado para 0.60.1
  • Clp 1.16.11 atualizado para 1.77.1
  • Osi 0.107.9 atualizado para 0.108.1
  • CoinUtils 2.10.14 atualizado para 2.11.1.

Mudanças na API CP-SAT

As seções a seguir descrevem as mudanças na API CP-SAT no OR-Tools 7.1.

Como usar o domínio para criar variáveis

Os exemplos a seguir mostram como criar uma variável de número inteiro com domínios não contíguos. Isso substitui o método NewEnumeratedIntVar() removido. Aqui, a variável x pode ser 1, 3, 4 ou 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");

As variáveis também podem ser criadas usando uma lista de intervalos. Abaixo, a variável x é restrita a 1, 2, 4, 5 ou 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");

Como usar o domínio em uma expressão linear

Os exemplos a seguir mostram como limitar uma expressão linear em um domínio não contíguo. Aqui, a expressão linear linear_expr é definida em 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} }));

Como usar auxiliares de expressão linear

Os exemplos a seguir mostram como usar métodos auxiliares para criar somas e produtos escalares. Confira um exemplo em que queremos usar 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);

Março de 2019

Anúncio do lançamento do OR-Tools v7.0

Lançamos o OR-Tools v7.0. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Mudanças nas plataformas com suporte

O OR-Tools v7.0 não é mais compatível com as seguintes plataformas:

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

Se você estiver usando uma dessas plataformas, ainda poderá instalar o OR-Tools v6.10.

Mudanças nas dependências necessárias

O OR-Tools v7.0 tem as seguintes dependências novas e atualizadas:

As seções a seguir descrevem os novos recursos e melhorias do OR-Tools 7.0.

Novo gerenciador de índices para programas de roteamento

Nas Ferramentas do OR v7.0, os programas de roteamento de veículos precisam usar o novo RoutingIndexManager. Isso garante que os índices padrão para locais sejam consistentes com os índices internos usados pelo solucionador e ajuda a evitar erros no código.

O novo RoutingIndexManager requer algumas pequenas mudanças nos programas de roteamento, que são descritas nas seções a seguir:

Incluir/importar RoutingIndexManager

No OR-Tools 7.0, os programas de roteamento em C++ e Java precisam incluir ou importar o RoutingIndexManager, conforme mostrado nos exemplos abaixo:

C++

#include "ortools/constraint_solver/routing_index_manager.h"

Java

import com.google.ortools.constraintsolver.RoutingIndexManager;

As importações para Python e C# não são alteradas.

Declarar RoutingIndexManager

Nas ferramentas OR v7.0, os programas de roteamento precisam declarar RoutingIndexManager e criar o modelo de roteamento, conforme mostrado nos exemplos a seguir:

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

Os argumentos de RoutingIndexManager são:

  • O número de locais
  • O número de veículos
  • O índice do depósito (locais de partida e chegada para todos os veículos)

Callbacks

No OR-Tools v7.0, você precisa usar RoutingIndexManager para criar callbacks, como o callback de distância, que você transmite para o solucionador. Os exemplos abaixo mostram como criar um callback de distância.

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

O método IndexToNode converte os índices de localização internos usados pelo solucionador nos índices padrão da matriz de distância.

Em vez de transmitir o callback diretamente para o solucionador, como nas versões anteriores, na v7.0, primeiro você cria transit&nbsp;callback&nbsp;index, uma referência ao callback, e a transmite para o solucionador (neste caso, por SetArcCostEvaluatorOfAllVehicles).

Dimensões

Nos exemplos a seguir, mostramos como criar uma dimensão para demandas e capacidades, que é usada para resolver o problema de roteamento de veículos capacitados.

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");

Soluções de impressão

No OR-Tools v7.0, use RoutingIndexManager para mostrar as rotas do veículo em uma solução. Os exemplos a seguir mostram como imprimir soluções em todas as linguagens compatíveis.

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);
    }

Suporte a VRPs com retiradas e entregas

A OR-Tools v7.0 oferece suporte para resolver problemas de roteamento de veículos (VRPs, na sigla em inglês) com retiradas e entregas, em que o objetivo é encontrar os trajetos mais curtos para uma frota de veículos retirando e entregando itens em vários locais. Você configura o problema de maneira semelhante a um VRP padrão, mas, além disso, especifica um par (i, j) de locais para cada item, em que i é o local de retirada e j é o local de desembarque. O solucionador de trajetos retorna trajetos do veículo que, para cada par, (i, j), i e j estejam no mesmo trajeto, e o veículo visita i antes de j.

Para conferir um exemplo que resolve esse tipo de problema, consulte Roteamento de veículos com embarques e entregas.

Suporte a funções lambda

O OR-Tools v7.0 agora inclui suporte para funções lambda em C# e Java, além de C++ e Python, que já tinham suporte. As funções Lambda fornecem uma maneira conveniente de definir callbacks em programas de roteamento. No entanto, você pode definir callbacks usando funções padrão se achar que isso torna seu código mais legível.

Os exemplos de callback em C# e Java acima ilustram como definir callbacks usando funções lambda.

Novembro de 2018

Anúncio do lançamento da versão v6.10

Lançamos a versão 6.10 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

As seções a seguir descrevem os novos recursos e melhorias da versão 6.10.

Comandos simplificados para criar e executar programas.

Na versão 6.10, é possível criar e executar programas inserindo comandos como estes: 

make run SOURCE=relative/path/to/program.cc
, em que <var>relative/path/to</var> é o caminho para o diretório que contém o programa.

Para criar um programa sem executá-lo, digite: 

make build SOURCE=relative/path/to/program.cc
. Consulte Começar a usar ferramentas OR para conferir instruções específicas sobre como executar programas por linguagem.

Suporte para SCIP 6.0.0

O OR-Tools é compatível com o SCIP 6.0.0.

Binários

As distribuições binárias foram criadas usando Java JDK 8 (JDK 7 para Ubuntu 14.04).

Solucionador CP-SAT

Atualizar a API

  • Foi adicionada a API CpModelBuilder para C++ CP-SAT.

Exemplos

Alguns exemplos foram movidos.

  • Mover exemplos da comunidade para examples/contrib.
  • Mova alguns exemplos para ortools/<var>component</var>/samples (por exemplo, ortools/linear_solver/samples/simple_program.java)

Setembro de 2018

Anúncio do lançamento da versão v6.9

Lançamos a versão 6.9 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Dependências atualizadas

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

Solucionador CP-SAT

  • Mudanças interruptivas na API. Todos os detalhes neste link:
  • Renomeie SolveWithSolutionObserver como SolveWithSolutionCallback em Python.

  • Renomeie NewSolution como OnSolutionCallback na classe CpSolverSolutionCallback em Python. O exemplo a seguir mostra a nova maneira de criar um callback de solução em 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

  • Exposição de StopSearch no callback da solução em Python, Java e C#. Acesse a documentação aqui.

  • ModelStats e CpSolverResponseStats foram expostos em Python, Java e C#.

  • Melhoria na documentação do docstring do Python. Acesse a documentação aqui.

  • Atualizações na implementação Java da interface do solucionador e do manual.

  • Implemente módulo.

  • Mude a implementação de reservoir: adicione a API com booleano para especificar eventos opcionais de drenagem/preenchimento

Solucionador linear

  • Exposição de InterruptSolve em Java e C#.

Solucionador

  • Exposição do diretor SolutionCollector em C#.

Python

  • Foi adicionado suporte a Python 3.7.
  • Ao compilar usando a origem: dê preferência a python3 em vez de python2 ao detectar o Python.

.NET

  • Reescrever completamente a camada .NET.
  • Forneça um pacote Nuget Google.OrTools NetStandard 2.0 compatível com o IDentificador de ambiente de execução win-x64, linux-x64 e osx-x64.
  • Forneça um pacote Nuget Google.OrTools.FSharp.
  • Adicione um arquivo de projeto para todos os exemplos em .NET.
  • Atualize todos os exemplos de script F# (.fsx) para o projeto F# normal (.fs).
  • Adicione a documentação sobre a geração de build de pacotes .NET aqui.

Zinco

  • Foi adicionado suporte a conjuntos em flatzinc (usando nosets.mzn).

Contribuições

  • Foi adicionado suporte à vinculação. Agradecemos a Kevin Mader
  • Transforme DecisionVisitor em um tipo de diretor nas vinculações Java. Agradecemos a Jeremy Apthorp.

Julho de 2018

Anúncio do lançamento da versão v6.8

Lançamos a versão 6.8 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Conheça o solucionador CP-SAT

O solucionador CP-SAT é um novo solucionador para programação de restrições. O solucionador CP-SAT é mais rápido do que o solucionador CP e deve ser preferível para problemas de CP.

Para ver exemplos que usam o solucionador CP-SAT, procure no diretório examples no GitHub para arquivos que tenham _sat no nome.

O solucionador CP original vai continuar sendo mantido por um período para oferecer suporte ao código atual, mas foi descontinuado.

Novas opções para o solucionador CP-SAT

As seguintes opções para o solucionador CP-SAT são novas nesta versão:

  • Pesquisa de bairro local (LNS, na sigla em inglês): use a opção SatParameters.use_lns para ativar o LNS.
  • Pesquisa paralela: use a opção SatParameters.num_search_workers para ativar várias linhas de execução durante uma pesquisa. Cada linha de execução pode ter parâmetros diferentes e diferentes sementes aleatórias. Isso maximiza a diversidade e a probabilidade de que pelo menos uma linha de execução encontre soluções.

Melhorias de desempenho para solucionadores de problemas

Fizemos melhorias de desempenho nos solucionadores CP-SAT e Glop.

Março de 2018

Anúncio do lançamento da versão v6.7

Lançamos a versão 6.7 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada em Instalação de ferramentas OU.

Atualizar para as dependências necessárias

  • Protobuf 3.5.0 -> 3.5.1.

Diversos

  • Refatorar a base para preparar a integração abseil-cpp.
  • Uso dos serviços de integração contínua (CI) do Travis CI e do Appveyor.

SÁB

  • Melhoria no desempenho.
  • Melhora a API Python.
  • Adição da API C#, também conhecida como CpSolver.cs (EXPERIMENTAL).

Glop

  • Refatoração de código
  • Melhoria no desempenho.

Suporte ao CMake (EXPERIMENTAL)

  • Foi adicionado suporte ao CMake C++ OR-Tools.
  • Saber compilar OR-Tools como um projeto CMake independente.
  • Conseguir incorporar ferramentas OR a um projeto CMake existente.
  • Adicione o build baseado em CMake das ferramentas OR Python.
  • Gerar o pacote Python (wheel) usando o CMake.

Contribuições

  • Correção da redefinição winsock2.h no Windows. Agradecemos a Florent Tollin de Rivarol.
  • Adicione suporte a F# (EXPERIMENTAL). Agradecemos a Matthew Moore. Observação: disponível apenas com o builder do Makefile.
  • Adicionar suporte padrão ao .NET (EXPERIMENTAL). Agradecemos a Ziad El Malki. Observação: disponível apenas com o builder do Makefile.

Novembro de 2017

Anúncio do lançamento da versão v6.6

Lançamos a versão 6.6 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Atualizações para as dependências necessárias

  • Protobuf para 3.3.0 -> 3.5.0.
  • do gflags para 2.2.0 -> 2.2.1.
  • CBC 2.9.8 -> 2.9.9.
  • Adicione o módulo seis (1.10) do Python como a dependência necessária para o Python.

Correções de bugs

  • Solicitação de envio no 494 Refatoração de nome. Adição de comentários para o IntelliSense em alguns editores Agradecemos a Matthew Moore.
  • Solicitação de envio no 516 Instrução para binário autônomo F#. Agradecemos a Matthew Moore.
  • Melhorar a precisão no Glop.

Solucionador SAT

  • Melhoria no solucionador interno do SAT, correção de vários bugs.
  • Adiciona uma restrição de VRP ao solucionador SAT, vinculado ao solucionador LP.
  • Mude o observador de solução no solucionador SAT para usar um CpSolverResponse como parâmetro.
  • Melhorar o uso de Glop no Solucionador SAT.
  • Aceleração da conexão SAT-LP.
  • A restrição de reservatório foi adicionada ao formato protobuf cp_model do SAT.

SAT/Python

Exemplos

  • Reescreva rcpsp_parser para usar o formato ProtoBuf e armazenar o problema.
  • Melhoria no analisador RCPSP.

Outubro de 2017

Anúncio do lançamento da versão v6.5

Lançamos a versão 6.5 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Mudança nas plataformas

  • O módulo pypi py3-ortools foi mesclado com o módulo ortools. Agora há apenas um módulo: "ortools".
  • O formato principal desses módulos Python agora são arquivos wheel. Para instalar OR-Tools para Python usando pypi, basta executar pip install ortools. Você precisa de uma versão recente do pip instalada (>= 9.0.1). Isso extrairá a versão mais recente (v6.5).

Bug fixed

O arquivo jar protobuf agora é criado corretamente com classes compiladas.

Novos exemplos

  • Mais exemplos de F# foram contribuídos para o diretório examples/fsharp (graças novamente a Matthew Moore).
  • Exemplos de MIP do Java também foram disponibilizados (obrigado Darian).

Setembro de 2017

Anúncio do lançamento da versão v6.4

Lançamos a versão 6.4 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Mudança nas plataformas

  • Agora, os módulos Pypi nas plataformas Linux são entregues como arquivos wheel usando a tag Manylinux1. Agradecemos a Federico Fácerelli. Com essa mudança, revertemos os módulos por Linux introduzidos na versão de julho de 2017.

Novos recursos

  • Método de escalonamento aprimorado usado dentro do GLOP.
  • Correção do encapsulamento de avaliadores na biblioteca de roteamento C#. Agradecemos a DevNamedZed.
  • Melhorar o desempenho do plano de zinco para modelos grandes.
  • Use o SAT com suporte para flatzinc por padrão.
  • Melhorar o desempenho da abordagem baseada em Core para o solucionador SAT.
  • Correção do bug no algoritmo de atribuição linear que estava falhando incorretamente.
  • Adição de exemplos de F# em ortools/examples/fsharp.
  • Remova a verificação de penalidades positivas na biblioteca de roteamento.

Agosto de 2017

Anúncio do lançamento da versão v6.3

Lançamos a versão 6.3 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Novos arquivos de download

Os arquivos Python wheel para Linux agora estão disponíveis para download na página de versões OR-Tools, junto com as versões mais recentes de todos os downloads.

Solucionador minizinco

Esta versão contém o código final de satélite e de flatzinc enviado para o desafio Minizinc 2017.

Julho de 2017

Anúncio do lançamento da versão v6.2

Lançamos a versão 6.2 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Mudança nas plataformas

  • Agora oferecemos suporte a várias distribuições binárias do Linux (Ubuntu 14.04, 16.04, 17.04, CentOS 7, Debian 9).
  • Agora, os módulos Pypi nas plataformas Linux incluem uma tag que descreve a distribuição (ubuntu-14.04, ubuntu-16.04, ubuntu-17.04, centos-7, debian-9).

Novos recursos

Adicionamos suporte ao Docker para criar artefatos do Linux. Acesse or-tools/tools/docker e confira o Makefile para conferir possíveis destinos (make archive, make pypi e make pypi3).

Esses comandos vão criar um subdiretório export e adicionar artefatos binários a ele.

Junho de 2017

Anúncio do lançamento da versão v6.1

Lançamos a versão 6.1 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Mudança nas plataformas

  • O Visual Studio 2017 é compatível, mas o Visual Studio 2013 não é mais compatível.
  • As versões 10.9 e mais recentes do macOS são compatíveis.

Novos recursos

Adicionamos um novo formato protobuf para nosso solucionador CP-SAT. Consulte ortools/sat/cp_model.proto para definir o modelo e ortools/sat/cp_model_solver.h para resolver o problema.

Correções de bugs

Problema 420: corrigimos o atributo __version__ ausente nos módulos pypi do Python em todas as plataformas.

Maio de 2017

Anúncio do lançamento da versão v6.0

Lançamos a versão 6.0 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Nova estrutura de diretórios em C++

Mudamos a estrutura de origem/inclusão das ferramentas OR ao usar C++. O objetivo é melhorar o encapsulamento dos arquivos de inclusão do C++. Ele também tem a vantagem de alinhar as estruturas de diretórios C++ e Python.

  • src/ foi renomeado como ortools/.
  • Todos os comandos #include em arquivos C++ agora têm o prefixo ortools adicionado. #include "constraint/constraint_solver.h" agora é #include "ortools/constraint/constraint_solver.h".

Novos recursos

  • Suporte ao Bazel. Agora é possível criar ferramentas OR com o bazel, a ferramenta de compilação do Google. Ele funciona no Linux e no Mac OS X. Depois de fazer o download do Bazel versão 0.4.5 ou mais recente, mude o diretório para or-tools e crie os exemplos: bazel build examples/cpp/....

Roteamento

Implementamos suporte a intervalos (por exemplo, tempo de inatividade do veículo devido a motoristas almoçando) na biblioteca de trajetos. Esse recurso é mostrado no exemplo cvrptw_with_breaks.cc.

Suporte ao SCIP

O wrapper de solucionador linear agora é compatível com SCIP 4.0. Agora você precisa criar o SCIP primeiro e depois dizer às ferramentas que ele será usado. As instruções estão disponíveis aqui.

Suporte a GLPK

Também mudamos o caminho com o build com GLPK. Acesse este link.

Limpeza

  • Removemos todo o uso de hash_map e hash_set na base de código C++, já que eles foram descontinuados Eles foram substituídos por unordered_map e unordered_set do STL.
  • Limpeza dos makefiles de C#, cortesia de Michael Powell.

Janeiro de 2017

Anúncio do lançamento da versão v5.1

Lançamos a versão 5.1 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Novos recursos

Instalação

Roteamento

Foi implementado um algoritmo para calcular o limite inferior Held-Karp para problemas simétricos de vendedores em viagem. Isso permite calcular um limite superior para a lacuna entre o custo de uma solução potencialmente não ideal e o custo da solução ideal.

  • Foi adicionado um novo método à biblioteca de trajetos de veículos, RoutingModel::SetBreakIntervalsOfVehicle, que permite adicionar intervalos de break, que são períodos em que o veículo não pode realizar nenhuma tarefa, como viajar ou visitar um nó. Para ver um exemplo que usa essa opção, consulte cvrptw_with_breaks.cc

Agendamento

Solucionador de sat

Melhorias no desempenho

  • Solucionador de SAT: melhoria no desempenho do solucionador, especialmente para a restrição cumulativa.
  • Solucionador de Glop: robustez numérica aprimorada do solucionador, que agora retorna soluções ainda mais precisas para problemas numéricos difíceis.
  • Solucionador Flatzinc
  • Melhoria significativa no desempenho do back-end Sat para o intérprete de flatzinc.
  • Simplificação da interface flatzinc de C#. Para ver um exemplo da nova interface, consulte https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs.

Correções de bugs

  • O uso da heurística PathCheapestArc em modelos de roteamento com um único veículo e restrições laterais às vezes fazia com que o solucionador fosse executado por muito tempo. Isso foi corrigido considerando corretamente as restrições laterais.
  • Em Java, o solucionador de problemas de roteamento às vezes travava ao resolver problemas de definição de trajeto de veículos. Isso foi corrigido na última versão.

Novembro de 2016

Anúncio do lançamento da versão v5.0

Lançamos a versão 5.0 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Exemplos em execução

  • Foram introduzidos destinos específicos de linguagem que facilitam a compilação e execução dos seus programas, bem como os exemplos que acompanham as ferramentas OR.

Sáb

FlatZinc

Solucionador de restrições

Roteamento

  • Foi implementado o AddAtSolutionCallback, que é um callback chamado sempre que uma solução é encontrada durante a pesquisa.
  • Os construtores sem depósito do RoutingModel foram removidos Agora é obrigatório especificar pelo menos um depósito no modelo de roteamento.

Setembro de 2016

Anúncio do lançamento da versão v4.4

Lançamos a versão 4.4 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Sáb

  • API de agendamento estendida e exemplos modificados (weighted_tardiness_sat e jobshop_sat) para usá-la.

Gráfico

  • Características do iterador foram adicionadas às classes Graph

Distribuição de ferramentas OU

  • O pacote Nuget é compatível novamente.

Agosto de 2016

Anúncio do lançamento da versão v4.3

Lançamos a versão 4.3 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Solucionador de restrições

  • O método NotBetween foi implementado para restringir uma variável a um determinado intervalo.

roteamento

  • Foi adicionada uma análise do modelo para verificar as restrições de NotMember existentes, conforme mostrado neste exemplo, e usá-las em filtros de pesquisa local.
  • A criação de perfil da pesquisa local foi adicionada.
  • Correção para mudanças locais.

Solucionador linear

  • Relatórios de status do SCIP corrigidos.

Sáb

  • O método SolveWithPresolve foi implementado para simplificar o uso do presolver de SAT.
  • Utilitários de pesquisa reagrupados em src/sat/util.h|cc.
  • Implementação de restrições de programação da SMT (geração lenta de cláusulas): consulte jobshop_sat.cc e weighted_tardiness_sat.cc.

Glop

  • O desempenho melhorou explorando a esparsidade em mais estágios de computação.

Zinco

  • Correção de bugs encontrados pelo desafio minizinc.

Lp_data

  • Simplificação contínua de modelos em iteradores.

Distribuição de ferramentas OU

  • Os assemblies C# agora são nomeados fortemente por padrão.
  • Atualização para Protobuf3.0.0.
  • Foi adicionado um script do Python para verificar as dependências de arquivo das ferramentas OR.

Julho de 2016

Anúncio do lançamento da versão v4.2

Lançamos a versão 4.2 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Solucionador de restrições (roteamento)

  • Agora, uma disjunção pode ser definida com uma cardinalidade, que é o número máximo de nós que podem estar ativos dentro dessa disjunção. Por exemplo, se você adicionar uma disjunção com n nós e uma cardinalidade de k, os k nós entre os n nós poderão ficar ativos. Você pode usar a nova definição de AddDisjunction para fazer isso.
  • Inclusão de suporte a várias disjunções por nó. Por exemplo, agora você pode adicionar um nó, N1, a muitas disjunções (D1..Dm). Isso aumenta sua chance de ser ativa em qualquer um deles. Introduzido um algoritmo de pesquisa de roteamento mais rápido para problemas relacionados a janelas de tempo disjuntas.
  • Foram adicionados parâmetros do solucionador de restrições aos parâmetros de modelo de roteamento e log_search aos parâmetros de pesquisa de roteamento.
  • O algoritmo de pesquisa local é mais rápido na resolução de problemas com janelas de tempo separadas. Confira o exemplo em cvrp_disjoint_tw.cc para mais detalhes.

Glop (otimização linear)

  • Introduzido um algoritmo Simplex mais rápido.

Distribuição de ferramentas OU

  • Um arquivo por plataforma, em vez de arquivos individuais para cada um dos arquivos C++, Java e .Net. Os arquivos Python continuam hospedados em pypi.
  • Em pypi, mudamos para módulos wheel (.whl) no Mac OS X e Windows. Foi introduzido um esquema de numeração MAJOR.MINOR. Esses números são usados para os nomes de arquivos, a versão armazenada nas bibliotecas compartilhadas do Mac OS X, nos módulos do Python e em conjuntos do .NET. A primeira versão que estamos lançando é a v4.2, com esse esquema

Junho de 2016

Anúncio do lançamento da versão v2016-06

Lançamos a versão v2016-06 do OR-Tools. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Solucionador de restrições

  • A maioria das instâncias dos callbacks (src/base/callback.h) foram removidas da biblioteca CP.
  • NotMemberCt adicionado. A variável não pode pertencer a um conjunto de intervalos.

Biblioteca de roteamento

  • ALTERAÇÃO INCOMPATÍVEL: para especificar a capacidade de veículos em AddDimensionWithVehicleCapacity, agora você precisa transmitir uma matriz (um vetor em c++) em vez de um callback.

GLOP

  • Mudar a representação interna da matriz esparsa.
  • Melhorias de desempenho.

Gráfico

  • Os algoritmos de Dijkstra e Bellman-Ford foram reescritos para substituir callbacks por std::function (C++).
  • Mude a API de implementação de gráfico diferente ao iterar em arcos e nós.

Sáb

  • Remoção do método principal não utilizado (nós de resolução).
  • O redator foi adicionado para verificar as provas de insatisfação.
  • Adicionar pré-processador.

Bop

  • Adicionar novos bairros.

Exemplos

  • c++: se livrar de filelinereader em exemplos.
  • dados: adicionar problemas de programação em uma única máquina.

Documentação

Abril de 2016

Anúncio do lançamento da versão v2016-04

Lançamos a versão OR-Tools v2016-04. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Dependências atualizadas

Dezembro de 2015

Anúncio do lançamento da versão v2015-12

Lançamos a versão OR-Tools v2015-12. Para atualizar sua versão, consulte a seção apropriada de Instalação de ferramentas OU.

Solucionador de restrições

  • A compatibilidade com a Pesquisa de bairros grandes no solucionador CP foi interrompida. Consulte examples/cpp/ls_api.cc, examples/python/pyls_api.py, examples/csharp/csls_api.cs e examples/com/google/ortools/sample/LsApi.java para conferir a nova API.
  • Limpeza do encapsulamento do Python. Suporte à decisão personalizada no solucionador de problemas de CPU. Consulte examples/test/test_cp_api.py para conferir a API em ação.
  • Diversas melhorias e correções de bugs.

Setembro de 2015

Anúncio da primeira versão no GitHub.

Os arquivos serão armazenados lá a partir de agora.

Zinco

  • Foram adicionados arquivos binários para o intérprete flatzinc (consulte www.minizinc.org).
  • Contém algumas correções para a versão usada no desafio.