Примечания к выпуску OR-Tools

На этой странице перечислены изменения в OR-Tools, включая новые функции, исправления ошибок, а также улучшения кода и процедур установки.

Если у вас возникли проблемы при установке OR-Tools, обратитесь к разделу «Устранение неполадок» в инструкциях по установке OR-Tools. Если вашей проблемы там нет, проверьте ее на GitHub или не стесняйтесь открывать новую, и мы будем рады предоставить вам помощь.

Ниже приведены примечания к выпуску OR-Tools, начиная с последней версии.

март 2024 г.

Анонсируем выпуск OR-Tools v9.9

Мы выпустили OR-Tools v9.9. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Вы можете найти примечание к выпуску на github.

ноябрь 2023 г.

Анонсируем выпуск OR-Tools v9.8

Мы выпустили OR-Tools v9.8. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения платформы

  • Добавьте Python 3.12.
  • Добавить поддержку Ubuntu 23.10.

Линейный решатель

  • Перенесите ModelBuilder в .Net.
  • Переименуйте LogCallback в MbLogCallback , чтобы избежать конфликта с SAT LogCallback.
  • Расширьте API ModelBuilder:
    • Добавьте ограничения индикатора.
    • Добавьте поддержку хинтинга.
    • Добавьте клонирование модели.

Математический вариант

  • Глубокая переработка.

Маршрутизация

  • Добавьте статус ROUTING_OPTIMAL .
  • Сделайте RoutingModel не подлежащим копированию и перемещению.
  • Исправлен бесконечный цикл в операторах локального поиска.
  • Добавьте внутреннюю структуру PickupDeliveryPosition .
  • Добавьте методы IsPickup() и IsDelivery() .

СИДЕЛ

  • Уменьшите объем памяти для большой модели.
  • Улучшен поиск по расписанию.
  • добавьте package_precedences_lns.
  • оптимизировать и исправить скачок осуществимости.
  • оптимизировать линейное предварительное решение и улучшить ведение журнала предварительного решения.
  • Улучшите предварительное решение для int_abs , int_mod , int_prod и lin_max .
  • Улучшение поддержки Panda
  • Немного исправлений ошибок.

Журнал изменений GitHub

август 2023 г.

Анонсируем выпуск OR-Tools v9.7

Мы выпустили OR-Tools v9.7. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения платформы

  • Удалите Centos-8 (EOL).
  • Удалить Дебиан 10.
  • Удалите Fedora [33, 36] (EOL).
  • Удалите Ubuntu 18.04 LTS (EOL).
  • Удалите Python 3.7 (EOL).
  • Отключите поддержку netcore3.1 в CMake (EOL).

Конструктор моделей Python

  • Разрешить использование фреймов данных и серий Pandas для создания переменных.
  • Полная информация о вводе

ПДЛП

  • различные обновления.

CP-САТ

  • Улучшения производительности. (feasibility_jump, lin_max)
  • Улучшите управление обрезкой
  • Новый рабочий объект Object_shaving_search, предназначенный для улучшения нижней границы цели (при минимизации).
  • Ввод аннотаций для python cp_model.py
  • Экспериментальная частичная поддержка панд в cp_model.py
  • Экспериментальный локальный обыск основан на нарушениях работников:
    • включено с параметрами: num_violation_ls:xxx
    • оптимизирован для линейной модели ( linear , bool_or , bool_and , at_most_one , exactly_one )
    • корректно работает с lin_max, продуктом, подразделением
    • поддерживает no_overlap, кумулятивные, цепные, маршруты
    • отключен с помощью no_overlap_2d
    • рекомендуемое количество рабочих ls: num_workers -> num_violation_ls : (8, 1), (16, 2) (24, 3), (32, 4)

Журнал изменений GitHub

март 2023 г.

Анонсируем выпуск OR-Tools v9.6

Мы выпустили OR-Tools v9.6. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения платформы

  • Добавьте поддержку Fedora 37, 38.
  • Удалите Python 3.6 (не поддерживается protobuf ).
  • Удалите Python 3.7 на macOS (не поддерживается scipy ).
  • Добавьте поддержку net7.0 в CMake (используйте -DUSE_DOTNET_7=ON ).
  • Удалите netcore3.1 в пакеты nuget .org.

Зависимости

  • SCIP v801 -> v803 (примечание: теперь SCIP использует лицензию, совместимую с OSI)
  • спуск 20220623.1 -> 20230105.0
  • Протобуф v21.5 -> v21.12
  • СВИГ 4.1.1
  • Java JNA 5.11.0 -> 5.12.1

Базель

  • Добавьте поддержку pybind11.
  • Добавьте поддержку оболочки Java.

Решатели

  • PDLP: оболочка dd python.
  • CP-SAT: Улучшение производительности.
  • GLOP: настройка presolve.
  • ModelBuilder: Python: улучшена поддержка numpy.
  • Маршрутизация: повышение производительности (локальный поиск)

Известные вопросы:

  • CP-SAT: Игнорирование субрешателя pseudo_costs возвращает неверные параметры (см. #3706 ).

ноябрь 2022 г.

Анонсируем выпуск OR-Tools v9.5

Мы выпустили OR-Tools v9.5. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения платформы

  • Добавьте поддержку Debian Sid.
  • Добавьте поддержку Fedora 35, 36.
  • Добавьте поддержку Ubuntu 22.10.
  • Удалите Python 3.6 на macOS.
  • Добавьте поддержку Python 3.11.

Обновление зависимостей

  • Протобуф v19.4 -> v21.5 .
  • SCIP Solver v800 -> v801 .

CP-САТ

  • Улучшения предварительного решения: max(array), логические ограничения, линейные ограничения.
  • Чередованный поиск должен быть детерминированным параллельно.
  • Линейные разрезы: очистка квадратных и int_prod разрезов; переписать вырезанный конвейер.
  • Модель ввода отпечатка пальца и решение (видно в журнале).
  • Планирование улучшений.
  • Обычная куча исправлений (сбой во время пресолва, сбой в разрезах, недопустимые решения, недопустимая модель в LNS).

ГЛОП

  • Ускорение за счет переписывания линейной алгебры, а также правила выбора поворота.

Линейный решатель

  • Добавьте knapsack_interface.cc .
  • Переместите API model_builder в каталог Linear_solver (заголовки и примеры).
  • Добавьте поддержку Гуроби 10.

Маршрутизация

  • Освободите несколько парсеров для решения различных задач маршрутизации.

август 2022 г.

Анонсируем выпуск OR-Tools v9.4

Мы выпустили OR-Tools v9.4. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Платформы

  • Добавьте поддержку Debian-10 (см. #3029 ).
  • Добавьте поддержку Ubuntu 22.04 LTS (см. #3276 ). примечание: не будет поддержки .Net 3.1 (см. dotnet/core#7038 ).
  • Удалить поддержку Ubuntu 21.10.

Разное

  • Разделите архив по языкам и добавьте конфиг CMake к конфигу C++ (#3200).

График

Разделите ortools.graph.pywrapgraph на:

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

Это позволяет использовать numpy для ускорения настройки задач.

CP-САТ

Некоторые улучшения:

  • планирование (распространение, разрезы, нижние границы).
  • MaxSAT (предварительная эвристика на основе ядра).
  • Производительность MIP (пререшение, обрезка).

март 2022 г.

Анонсируем выпуск OR-Tools v9.3

Мы выпустили OR-Tools v9.3. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения платформы

  • Откажитесь от поддержки Debian-10.
  • Откажитесь от поддержки Ubuntu-16.04.
  • Удалите .NET Framework 4.5.2.

Обновление зависимостей

  • Добавьте Эйген 3.4.0 .
  • Добавьте Google re2 2021-11-01 .
  • Протобуф 3.19.1 -> 3.19.4 .
  • SCIP 7.0.1 -> v800 .

Питон

  • Добавьте pybind11.

Функции

  • Добавьте PDLP в качестве экспериментального.
  • Добавьте MathOpt в качестве экспериментального.

CP-САТ

  • Для обеспечения единообразия переименованы некоторые API, например LinearExpr.ScalProd. -> LinearExpr.WeightedSum. .
  • Добавьте методы AddAtLeastOne / AddAtMostOne / AddExactlyOne .
  • Добавьте AddMultiplicationConstraint(z, x, y) на всех языках.
  • Добавьте AddMultipleCircuit() на всех языках.

С++

  • Явный ctor IntVar(BoolVar) .
  • Удален LinearExpr::Add* и заменен оператором, например LinearExpr += .
  • Добавьте арифметические операторы к линейному выражению.
  • Удален LinearExpr::BooleanSum/BooleanScalProd , используйте Sum/WeightedSum .
  • Добавьте CpModelBuilder::FixVariable() , который перезапишет домен переменной одним значением.

Джава

  • Перепишите LinearExpr , добавьте класс инкрементного построителя: LinearExpr.newBuilder().add(x).addSum(<array of variables>).build() .
  • Следуйте API C++: Circuit , MultipleCircuit , Cumulative , Reservoir , AllowedAssignment и ForbiddenAssignment теперь возвращают специализированный класс с инкрементным API для добавления новых переменных, терминов, требований…

С

  • Документируйте все методы.
  • Следуйте API C++: Circuit , MultipleCircuit , Cumulative , Reservoir , AllowedAssignment и ForbiddenAssignment теперь возвращают специализированный класс с инкрементным API для добавления новых переменных, терминов, требований…
  • Добавьте класс LinearExprBuilder для постепенного построения выражений.

Система сборки

CMake

  • Требуется как минимум CMake >= 3.18.

Делать

  • Теперь используйте сборку на основе CMake для внутренних целей.

декабрь 2021 г.

Анонсируем выпуск OR-Tools v9.2

Мы выпустили OR-Tools v9.2. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения платформы

  • Добавьте поддержку Ubuntu 21:10 (последний релиз).

Обновление зависимостей

  • Обновление .Net TFM net5.0 -> net6.0 (нужны .Net SDK 6.0 LTS и .Net SDK 3.1 LTS).
  • abseil-cpp 20210324.2 -> 20211102.0.
  • Протобуф 3.18.0 -> 3.19.1.
  • Гуглтест 1.10.0 -> 1.11.0.
  • Python: добавьте numpy >= 1.13.3.
  • В MacOS скомпилируйте Coin-OR в -O1 , чтобы избежать сбоя в бегунах.

Маршрутизация

  • Улучшение фильтров.
  • Улучшите эвристику первого решения.
  • Улучшите размещение перерывов.

CP-САТ

Критические изменения

  • Базовый буфер протокола несовместим с предыдущими версиями. Любой сохраненный буфер протокола необходимо будет заново сгенерировать с помощью обновленных API-интерфейсов компоновщика (на C++, Python, Java и .NET).
  • В частности, интервал protobuf был чистым, поскольку мы удалили старые поля (start, size и end) и переименовали новые (с помощью _view ), чтобы использовать имена удаленных полей.

Новые возможности

  • Ограничения all_different , reservoir , modulo , multiplication и division принимают аффинные выражения ( a * var + b ) везде, где требуются целочисленные переменные.
  • Цель принимает коэффициенты с плавающей запятой (см. класс DoubleLinearExpr в C++/Java/.NET. См. пример knapsack_2d_sat.py в Python).
  • Ограничение no_overlap_2d поддерживает необязательные интервалы.
  • API C++ реализует операторы + и * для построения выражений.

Улучшения

  • Улучшен код предварительного решения.
  • Более жесткая проверка модели.
  • Переработать ограничение резервуара.
  • Добавьте энергичные разрезы для ограничения no_overlap_2d.
  • Улучшено линейное ослабление ограничений кодирования ( literal implies var == value ).

Устаревшие и удаленные методы

  • Устаревшие C++ BooleanSum и BooleanScalProd . Просто используйте Sum и ScalProd .
  • Удалены C++ AddLinMinEquality и AddLinMaxEquality . Просто используйте AddMinEquality и AddMaxEquality .

Будущие несовместимости

  • В какой-то момент в будущем мы перепишем уровень моделирования Java, чтобы он был ближе к уровню C++.
  • На уровне моделирования C++ мы сделаем явным вектор IntVar(BoolVar var).
  • Мы рассматриваем возможность сделать API Python совместимым с PEP 8 (с использованием имен Snake_case). Если это произойдет, мы предоставим sed-файл для переноса кода.

Система сборки

Базель

  • Исправлена ​​сборка Windows.

CMake

  • Добавьте параметр FETCH_PYTHON_DEPS (по умолчанию ON ).
  • Добавьте дополнительную поддержку решателя GPLK (по умолчанию -DUSE_GLPK=OFF ).

Питон

  • Поддержка numpy в большинстве API CP-SAT.
  • Исправьте отсутствующую __version__ .

сентябрь 2021 г.

Анонсируем выпуск OR-Tools v9.1

Мы выпустили OR-Tools v9.1. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения платформы

  • Python: используйте образ manylinux2014 (см. PEP 599 ).
  • Python: добавьте поддержку aarch64 Linux, используя образ manylinux2014_aarch64 .
  • .Net: добавить поддержку .Net 5.0.

Обновление зависимостей

  • abseil-cpp 20210324.1 -> 20210324.2.
  • Протобуф 3.15.8 -> 3.18.0.
  • SCIP 7.0.1 -> мастер.
  • Гуглтест 1.8.0 -> 1.10.0.
  • python: использование warning в cp_model.py (см. #2530 ).
  • Python: абсл-py 0,11 -> 0,13.

CMake

  • Требуется минимальная версия 3.14 -> 3.15 (см. #2528 ).
  • Python: увеличить минимальную требуемую версию 3.14 -> 3.18 (см. #2774 ).

Делать

Сборка на основе Make устарела. Перейдите на CMake или Bazel для сборки из исходного кода.

Джава

  • Повысьте надежность загрузчика встроенной библиотеки (см. #2742 ).
  • Исправлен сбой сборщика мусора JVM при удалении модели маршрутизации или решателя ограничений (см. #2091 ) (см. #2466 ).
  • Исправлен сбой обратного вызова журнала CP-SAT при использовании нескольких рабочих процессов (см. #2775 ).

CP-САТ

  • Повысьте надежность кода LNS (см. #2525 ).
  • Улучшите код планирования: новые фабричные методы для создания интервалов фиксированного размера, новую эвристику поиска, улучшенное предварительное решение и новые линейные разрезы.
  • Улучшение кода маршрутизации: новый выделенный LNS.
  • Улучшение проверки модели. Теперь он более педантичен, особенно в отношении потенциальных переполнений.
  • Улучшите код MIP: улучшенное предварительное решение и многочисленные улучшения линейной релаксации моделей MIP и CP.
  • Улучшите разнообразие поиска. При использовании более 12 работников добавьте работников, занимающихся улучшением нижней границы цели.
  • Измените код параллелизма: по умолчанию решатель теперь будет использовать все доступные ядра. Используйте num_search_parameters , чтобы указать уровень параллелизма.
  • Устаревшие SearchAllSolutions и SolveWithSolutionCallback .
  • Python API: более педантичные проверки при использовании var == ... или var != ... вне вызова model.Add() .

апрель 2021 г.

Анонсируем выпуск OR-Tools v9.0

Мы выпустили OR-Tools v9.0. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Обновления зависимостей

Джава

Исправление ошибок

  • Улучшите многопоточность при использовании решателя CP-SAT (см. #1588 ).
  • Исправлена ​​поддержка оболочки Python std::vector&ltstd::string&gt (см. #2453 ).
  • Переработана поддержка CPLEX (см. #2470 ).

Известные критические изменения

  • Добавьте доступ к регистратору в Python, Java и .Net (см. #2245 ).
  • Замена всех пользовательских типов Google на те, которые указаны в cstdint .

CP-САТ

  • Методы SearchForAllSolutions() , SearchAllSolutions() и SolveWithSolutionCallback() устарели. Вместо этого используйте Solve() .
  • Улучшена поддержка стандартных операторов Python. Это может привести к поломке неправильного существующего кода.

март 2021 г.

Анонсируем выпуск OR-Tools v8.2

Мы выпустили OR-Tools v8.2. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Обновления зависимостей

  • Abseil-cpp 20200923.2 обновлен до 20200923.3 LTS.
  • Protobuf 3.14.0 обновлен до 3.15.3.

Маршрутизация

  • Добавлены RoutingModel.RegisterTransitMatrix() и RoutingModel.RegisterUnaryTransitVector() .
  • Измените возврат RoutingModel.AddVectorDimension() и RoutingModel.AddMatrixDimension() на std::pair&ltint, bool&gt int которого является идентификатором оценщика транзита.

декабрь 2020 г.

Анонсируем выпуск OR-Tools v8.1

Мы выпустили OR-Tools v8.1. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Обновления зависимостей

  • Abseil-cpp 20200923 обновлен до 20200923.2 LTS.
  • Protobuf 3.13.0 обновлен до 3.14.
  • Добавить поддержку Гуроби 9.1.0
  • Удалить зависимость GLog (заменена специальной реализацией в зависимости от флагов abseil-cpp)
  • Удалить зависимость GFlag (заменена компонентом флагов abseil-cpp)

Исправление ошибок

  • Исправлен двойной учет плавающей лицензии Гуроби (см. #2227 ).
  • Исправьте сборку Windows (см. #2200 ).

октябрь 2020 г.

Анонсируем выпуск OR-Tools v8.0

Мы выпустили OR-Tools v8.0. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения платформы

  • Добавлена ​​поддержка Python 3.9 ( #2187 ).
  • Прекращена поддержка Python 3.5 ( #2186 ) <!-- Ожидается поддержка Microsoft dotnet-sdk, которая может быть создана после выхода версии...
    • Добавлена ​​поддержка Ubuntu 20.10 ( #2188 ) -->
  • Прекращена поддержка Ubuntu 16.04 LTS ( #2188 ).
  • Прекращена поддержка Ubuntu 19.10 ( #2188 ).

Обновления зависимостей

  • Abseil-cpp 20200225.2 обновлен до 20200923 LTS.
  • Protobuf 3.12.2 обновлен до 3.13.0.

Известные критические изменения

  • Теперь исходный код Routing и CP-SAT использует некоторые функции C++17 . Предупреждение. Если вы предоставляете свою собственную версию abseil-cpp убедитесь, что она также построена на C++17 .
  • Подпись MPSolver::CreateSolver была изменена. Аргумент имени модели удален.

CMake

  • Исправлено отключение поддержки SCIP при использовании -DUSE_SCIP=OFF (см. #2129 ).
  • Интегрируйте примеры и примеры в систему сборки CMake. примечание: можно отключить, используя -DBUILD_SAMPLES=OFF и -DBUILD_EXAMPLES=OFF . примечание: можно отключить для определенного языка, используя -DBUILD_<LANG>_SAMPLES=OFF или -DBUILD_<LANG>_EXAMPLES=OFF .
    • С <LANG> среди:
    • CXX ,
    • PYTHON ,
    • JAVA и
    • DOTNET .

Делать

  • Требуется Make >= 4.3 (использование функции Make eval ).
  • Требуется CMake >= 3.14 (использование параметра CMake --verbose ).
  • Добавьте опцию для отключения поддержки SCIP с помощью -DUSE_SCIP=OFF (см. #2134 ).
  • Добавьте опцию для отключения поддержки CLP и CBC, используя -DUSE_COINOR=OFF .

Джава

  • OR-Tools теперь генерируют пакеты maven (см. #202 ).

Исправление ошибок

  • Исправлена ​​сборка C++ и Python на базе FreeBSD (см. #2126 ).
  • Исправлена ​​отладка сборки в Windows (см. #2077 ).
  • Исправлен давний сбой параллельного выполнения CP-SAT в Windows (см. #2001 , #2019 ).

июль 2020 г.

Анонсируем выпуск OR-Tools v7.8

Мы выпустили OR-Tools v7.8. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Обновления зависимостей

  • Gurobi 9.0.2 теперь предварительно интегрирован в готовые двоичные файлы. Он будет искать общую библиотеку gurobi 90 в пути установки по умолчанию установщиков Gurobi в MAC OS X и Windows или в каталоге GUROBI_HOME.
  • SCIP 7.0.1 теперь интегрирован в готовые двоичные файлы. Перед использованием убедитесь в соответствии лицензии SCIP.
  • Добавлена ​​поддержка дополнительного Xpress Solver 8.9.0.

Линейный решатель

  • Добавлен статический метод LinearSolver::CreateSolver() для упрощения проверки поддержки интегрированных серверных модулей линейного решателя. Это работает на всех языках.

Исправление ошибок

  • Исправлена ​​сборка на основе CMake для FreeBSD.
  • Исправлена ​​сортировка CP-SAT при генерации совокупного разреза.
  • Исправлена ​​утечка памяти линейного решателя в оболочке .Net.

июнь 2020 г.

Анонсируем выпуск OR-Tools v7.7

Мы выпустили OR-Tools v7.7. Чтобы обновить свою версию, обратитесь к соответствующему разделу установки OR-Tools .

Обновления зависимостей

  • Abseil-cpp b832dce обновлен до c51510d (LTS 20200225.2).
  • Protobuf 3.11.4 обновлен до 3.12.2.

Новые функции и улучшения

  • Решающая программа CP-SAT теперь возвращает Optimal вместо Feasible в модели выполнимости (т. е. без цели).
  • Добавлена ​​эвристика технико-экономического обоснования от сообщества MIP.

Исправление ошибок

Исправлен сбой многопоточности CP-SAT (см. #2005 ).

апрель 2020 г.

Анонсируем выпуск OR-Tools v7.6

Мы выпустили OR-Tools v7.6. Чтобы обновить свою версию, обратитесь к соответствующему разделу установки OR-Tools .

Новые возможности CP-SAT

Мы добавили в решатель CP-SAT следующие новые функции:

  • Улучшено управление плоскостями разреза для LP.
  • Инструменты отладки.

Обновления зависимостей

Abseil-cpp 8ba96a8 обновлен до b832dce (LTS 20200225).

Исправление ошибок

  • Исправлена ​​ошибка CP-SAT UNSAT в предварительном решении (см. #1908 ).
  • Исправлен URL-адрес swigwin.exe.
  • Исправлено управление картой типов SWIG для Java и .Net.

январь 2020 г.

Анонсируем выпуск OR-Tools v7.5

Мы выпустили OR-Tools v7.5. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения платформы

  • Добавлена ​​поддержка Python 3.8 ( #1719 ).
  • Прекращена поддержка компиляции из исходников в Visual Studio 2017 ( #1852 ).
  • Обновлена ​​поддержка Centos 7 до Centos 8 ( #1827 ).

Обновление зависимостей

Исправление ошибок

Следующие проблемы были исправлены в OR-Tools v7.5 (полный список см. в Milestone v7.5 ).

В частности:

  • Исправлена ​​загрузка сборки. См. № 1421 .
  • Доступны методы GetStartIndex() и GetEndIndex() RouteIndexManager ( #1843 ).
  • Исправлен SWIG для удаления неработающих методов ( #1838 , #1276 ).

октябрь 2019 г.

Анонсируем выпуск OR-Tools v7.4

Мы выпустили OR-Tools v7.4. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Новые функции и улучшения

  • Решающая программа CP-SAT теперь проверяет наличие ограничений, которые не поддерживают литералы принудительного применения. Средство проверки модели вернет ошибку перед решением, если такое ограничение имеет литерал принудительного применения.
  • Улучшенный и быстрый локальный поиск библиотеки маршрутизации.
  • Линейный решатель теперь поддерживает стороннее программное обеспечение Xpress-MP. Чтобы использовать его, вам нужно будет пересобрать OR-Tools из исходного кода .
  • Архитектура пакета NuGet была полностью переписана. В частности, теперь он поддерживает платформу .NET >= 4.5.2 на платформах Windows.

Устаревшая платформа

Как было объявлено в примечаниях к выпуску за июль 2019 года, OR-Tools больше не поддерживает Python 2.7.

Обновление зависимостей

Protobuf 3.9.0 обновлен до 3.10.0.

август 2019 г.

Анонсируем выпуск OR-Tools v7.3

Мы выпустили OR-Tools v7.3. Чтобы обновить свою версию, обратитесь к соответствующему разделу установки OR-Tools .

Устаревшая платформа

Мы прекращаем поддержку Python 2.7 в связи с переходом Google на Python 3. Это будет последний выпуск OR-Tools, поддерживающий Python 2.7.

Обновление зависимостей

Protobuf 3.8.0 обновлен до 3.9.0.

Исправление ошибок

Следующие проблемы были исправлены в OR-Tools v7.3. (Полный список см. в Kanban v7.3 ).

В частности:

  • Исправлена ​​проблема с приведением init/int64 на Java ( #1448 ),
  • Исправлена ​​проверка предварительного решения при обработке пустых накопительных ограничений.

июль 2019 г.

Анонсируем выпуск OR-Tools v7.2

Мы выпустили OR-Tools v7.2. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения платформы

  • Мы прекращаем поддержку Python 2.7 в связи с переходом Google на Python 3. Будет выпущен не более одного выпуска OR-Tools, поддерживающего Python 2.7.
  • Ubuntu 18.10 обновлен до Ubuntu 19.04.
  • Добавлена ​​поддержка компиляции из исходников в Visual Studio 2019.
  • Python 3.5 больше не поддерживается в Windows; используйте Python 3.6 или выше.

Обновления зависимостей

  • Теперь мы нацелены на CBC 2.10.3.
  • Теперь мы нацелены на Protobuf 3.8.0.

CP-САТ

  • Мы внесли множество улучшений в функции поиска, параллелизма и линейной релаксации.
  • Добавлены API-интерфейсы LinearExpr.Sum() и LinearExpr.ScalProd() в Python.
  • Устаревшие API IntVar[].Sum() и IntVar[].ScalProd() в C#.
  • C++: удален SolveWithModel() , поскольку он был дубликатом SolveCpModel() .
  • В Java API добавлены методы CpModel.addGreaterThan() и CpModel.addLessThan() .

Линейный решатель

  • Добавлен MPSolver.SetHint() для Python, Java и C# (поддерживается SCIP и Gurobi).
  • Добавлен MPSolver.SetNumThreads() для Python, Java и C# (поддерживается CBC, Gurobi и SCIP).
  • Переписана поддержка SCIP 6.0.1.

Справочная документация

  • Мы добавили справочные руководства на основе doxygen и pdoc3 для всех языков и всех инструментов (алгоритмы, маршрутизация, график, Linear_solver и CP-SAT). См. Справочное руководство по OR-Tools .
  • Полная справочная документация для C++ (все продукты) и CP-SAT (C++, Python, Java).
  • Мы находимся в процессе экспорта всей документации C++ в Python и Java.
  • Документация по .NET отсутствует, и в обозримом будущем у нас нет решения, как это исправить. Мы сохранили его, поскольку он по-прежнему показывает доступный API.

май 2019 г.

Анонсируем выпуск OR-Tools v7.1

Мы выпустили OR-Tools v7.1. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения в необходимых зависимостях

OR-Tools v7.1 имеет следующие новые и обновленные зависимости:

  • glog v0.3.5 обновлен до v0.4.0
  • protobuf v3.6.1 обновлен до v3.7.1
  • Cbc 2.9.9 обновлен до 2.10.1
  • Cgl 0.59.10 обновлен до 0.60.1
  • Clp 1.16.11 обновлен до 1.77.1
  • Оси 0.107.9 обновлена ​​до 0.108.1
  • CoinUtils 2.10.14 обновлен до 2.11.1

Изменения API CP-SAT

В следующих разделах описаны изменения в API CP-SAT в OR-Tools 7.1.

Использование домена для создания переменных

В следующих примерах показано, как создать целочисленную переменную с несмежными доменами. Это заменяет удаленный метод NewEnumeratedIntVar() . Здесь переменная x может иметь любое из значений 1, 3, 4 или 6:

Питон

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

С++

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

Джава

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

С#

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

Переменные также можно создавать с помощью списка интервалов. Ниже переменная x ограничена значениями 1, 2, 4, 5 или 6:

Питон

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

С++

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

Джава

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

С#

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

Использование домена в линейном выражении

В следующих примерах показано, как ограничить линейное выражение в несмежной области. Здесь линейное выражение linear_expr определено для чисел 5, 6, 8, 9 и 10:

Питон

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

С++

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

Джава

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

.Сеть

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

Использование помощников по линейным выражениям

В следующих примерах показано, как использовать вспомогательные методы для создания сумм и скалярных произведений. Вот примеры, где мы хотим x + y == 20 и 4 * x + 2 * y = 56 :\

Питон

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

С++

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

Джава

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

.Сеть

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

март 2019 г.

Анонсируем выпуск OR-Tools v7.0

Мы выпустили OR-Tools v7.0. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Изменения в поддерживаемых платформах

OR-Tools v7.0 больше не поддерживает следующие платформы:

  • Визуал С++ 2015
  • Убунту 14.04
  • Python 3.4 в Linux

Если вы используете одну из этих платформ, вы все равно можете установить OR-Tools v6.10 .

Изменения в необходимых зависимостях

OR-Tools v7.0 имеет следующие новые и обновленные зависимости:

В следующих разделах описаны новые функции и улучшения OR-Tools 7.0.

Новый менеджер индексов для программ маршрутизации

В OR-Tools v7.0 программы маршрутизации транспортных средств должны использовать новый RoutingIndexManager . Это гарантирует, что стандартные индексы местоположений соответствуют внутренним индексам, используемым решателем, и помогает предотвратить ошибки в вашем коде.

Новый RoutingIndexManager требует некоторых незначительных изменений в программах маршрутизации, которые описаны в следующих разделах:

Включить/импортировать RoutingIndexManager

В OR-Tools 7.0 программы маршрутизации на C++ и Java должны включать или импортировать RoutingIndexManager , как показано в примерах ниже:

С++

#include "ortools/constraint_solver/routing_index_manager.h"

Джава

import com.google.ortools.constraintsolver.RoutingIndexManager;

Импорт Python и C# не изменился.

Объявить RoutingIndexManager

В OR-Tools v7.0 программы маршрутизации должны объявить RoutingIndexManager и создать модель маршрутизации, как показано в следующих примерах:

Питон

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

С++

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

Джава

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

.Сеть

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

Аргументы RoutingIndexManager :

  • Количество локаций
  • Количество транспортных средств
  • Индекс депо (место начала и окончания для всех транспортных средств)

Обратные вызовы

В OR-Tools v7.0 вам необходимо использовать RoutingIndexManager для создания обратных вызовов, таких как обратный вызов расстояния, который затем передается решателю. В следующих примерах показано, как создать дистанционный обратный вызов.

Питон

    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)

С++

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

Джава

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

.Сеть

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

Метод IndexToNode преобразует внутренние индексы местоположения, используемые решателем, в стандартные индексы для матрицы расстояний.

Вместо передачи обратного вызова непосредственно решателю, как в предыдущих версиях, в версии 7.0 вы сначала создаетеtransit transit&nbsp;callback&nbsp;index , ссылку на обратный вызов, и передаете ее решателю (в данном случае с помощью SetArcCostEvaluatorOfAllVehicles ).

Размеры

В следующих примерах показано, как создать измерение потребностей и мощностей, которое используется для решения задачи маршрутизации груженых транспортных средств .

Питон

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

С++

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

Джава

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

.Сеть

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

Решения для печати

В OR-Tools v7.0 необходимо использовать RoutingIndexManager для отображения маршрутов транспортных средств в решении. В следующих примерах показано, как распечатать решения на всех поддерживаемых языках.

Питон

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)

С++

//! @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";
}

Джава

  /// @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");
  }

.Сеть

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

Поддержка VRP с самовывозом и доставкой

OR-Tools v7.0 обеспечивает поддержку решения задач маршрутизации транспортных средств (VRP) с погрузкой и доставкой, целью которых является поиск кратчайших маршрутов для парка транспортных средств, забирающих и доставляющих товары в различные места. Вы создаете задачу аналогично стандартному VRP, но дополнительно указываете пару (i, j) мест для каждого товара, где i — место получения, а j — место высадки. Решатель маршрутов возвращает маршруты транспортных средств так, что для каждой пары (i, j) i и j находятся на одном и том же маршруте, и транспортное средство посещает i раньше j .

Пример решения проблемы такого типа см. в разделе «Маршрутизация транспортных средств с получением и доставкой» .

Поддержка лямбда-функций

OR-Tools v7.0 теперь включает поддержку лямбда-функций в C# и Java (в дополнение к C++ и Python, которые уже поддерживались). Лямбда-функции предоставляют удобный способ определения обратных вызовов в программах маршрутизации. Однако вы можете определить обратные вызовы с помощью стандартных функций, если считаете, что это сделает ваш код более читабельным.

Приведенные выше примеры обратного вызова C# и Java иллюстрируют, как определять обратные вызовы с помощью лямбда-функций.

ноябрь 2018 г.

Анонсируем выход версии v6.10

Мы выпустили OR-Tools версии 6.10. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

В следующих разделах описаны новые функции и улучшения версии 6.10.

Упрощенные команды для сборки и запуска программ.

В версии 6.10 вы можете создавать и запускать программы, вводя такие команды:

make run SOURCE=relative/path/to/program.cc
где <var>relative/path/to</var> — это путь к каталогу, содержащему программу.

Чтобы создать программу, не запуская ее, введите:

make build SOURCE=relative/path/to/program.cc
См. «Начало работы с OR-Tools» для получения конкретных инструкций по запуску программ в зависимости от языка.

Поддержка SCIP 6.0.0

OR-Tools теперь поддерживает SCIP 6.0.0.

Бинарные файлы

Бинарные дистрибутивы были созданы с использованием Java JDK 8 (JDK 7 для Ubuntu 14.04).

Решатель CP-SAT

Обновите API

  • Добавьте API C++ CP-SAT CpModelBuilder.

Примеры

Некоторые примеры были перенесены.

  • Переместите примеры сообщества в examples/contrib .
  • Переместите несколько примеров в ortools/<var>component</var>/samples (например ortools/linear_solver/samples/simple_program.java ).

Сентябрь 2018 г.

Анонсируем выпуск версии v6.9

Мы выпустили OR-Tools версии 6.9. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Обновленные зависимости

  • Протобуф 3.5.1 -> 3.6.1.
  • SCIP 4.0 -> 6.0.

Решатель CP-SAT

  • Критические изменения в API – полная информация здесь :
  • Переименуйте SolveWithSolutionObserver в SolveWithSolutionCallback в Python.
  • Переименуйте NewSolution в OnSolutionCallback в классе CpSolverSolutionCallback в Python. В следующем примере показан новый способ создания обратного вызова решения в 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

  • Предоставляйте StopSearch обратный вызов решения в Python, Java и C#. Документация здесь .

  • Предоставляйте ModelStats и CpSolverResponseStats в Python, Java и C#.

  • Улучшите документацию по строке документации Python. Документация здесь .

  • Обновления Java-реализации интерфейса решателя и кулинарной книги.

  • Реализовать по модулю.

  • Измените реализацию резервуара: добавьте API с логическим значением, чтобы указать дополнительные события слива/заполнения.

Линейный решатель

  • Используйте InterruptSolve в Java и C#.

CP-решатель

  • Откройте директорию SolutionCollector на C#.

Питон

  • Добавьте поддержку Python 3.7 .
  • При компиляции из исходного кода: при обнаружении Python отдавайте предпочтение python3 , а не python2 .

.СЕТЬ

  • Полная переработка слоя .NET.
  • Предоставьте пакет Nuget Google.OrTools NetStandard 2.0, совместимый с идентификатором среды выполнения win-x64 , linux-x64 и osx-x64 .
  • Предоставьте пакет Nuget Google.OrTools.FSharp .
  • Добавьте файл проекта для всех примеров .NET.
  • Обновите все примеры сценариев F# (.fsx) до обычного проекта F# (.fs).
  • Добавьте сюда документацию по генерации сборок пакетов .NET.

Флэтцинк

  • Добавить поддержку наборов в Flatzinc (используя носец.мзн).

Взносы

июль 2018 г.

Анонсируем выпуск версии v6.8

Мы выпустили OR-Tools версии 6.8. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Анонс решателя CP-SAT

Решатель CP-SAT — это новый решатель для программирования в ограничениях. Решатель CP-SAT работает быстрее, чем исходный решатель CP, и его следует использовать для решения задач CP.

Примеры, в которых используется решатель CP-SAT, найдите в каталоге примеров на GitHub файлы, в именах которых есть _sat .

Исходный решатель CP будет продолжать поддерживаться в течение определенного периода времени для поддержки существующего кода, но он устарел.

Новые возможности решателя CP-SAT

Следующие опции решателя CP-SAT являются новыми в этом выпуске:

  • Поиск локального окружения (LNS): используйте параметр SatParameters.use_lns , чтобы включить LNS.
  • Параллельный поиск: используйте параметр SatParameters.num_search_workers , чтобы включить несколько потоков во время поиска. Каждый поток может иметь разные параметры и разные случайные начальные числа. Это максимизирует разнообразие и вероятность того, что хотя бы один поток найдет решения.

Улучшения производительности решателей

Мы улучшили производительность решателей CP-SAT и Glop.

март 2018 г.

Анонсируем выпуск версии v6.7

Мы выпустили OR-Tools версии 6.7. Чтобы обновить свою версию, смотрите соответствующий раздел установки OR-Tools .

Обновите необходимые зависимости

  • Протобуф 3.5.0 -> 3.5.1.

Разное

  • База рефакторинга для подготовки интеграции abseil-cpp .
  • Использование сервисов непрерывной интеграции (CI) Travis CI и Appveyor.

СИДЕЛ

  • Улучшение производительности.
  • Улучшает API Python.
  • Добавьте C# API, известный как CpSolver.cs (ЭКСПЕРИМЕНТАЛЬНАЯ).

Глоп

  • Рефакторинг кода.
  • Улучшение производительности.

Поддержка CMake (ЭКСПЕРИМЕНТАЛЬНАЯ)

  • Добавьте поддержку CMake в C++ OR-Tools.
  • Уметь создавать OR-Tools как отдельный проект CMake.
  • Уметь включать OR-Tools в существующий проект CMake.
  • Добавьте сборку на основе Python OR-Tools CMake.
  • Создайте пакет Python (колесо) с помощью CMake.

Взносы

  • Исправлено переопределение winsock2.h в Windows. Спасибо Флорану Толлену де Риваролю .
  • Добавить поддержку F# (ЭКСПЕРИМЕНТАЛЬНО). Спасибо Мэтью Муру . Примечание: доступно только с помощью компоновщика Makefile.
  • Добавьте стандартную поддержку .NET (ЭКСПЕРИМЕНТАЛЬНАЯ). Спасибо Зиаду Эль Малки . ПРИМЕЧАНИЕ. Доступно только с Makefile Builder.

ноябрь 2017 г.

Объявление о выпуске версии v6.6

Мы выпустили или сталкиваются с версией 6.6. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Обновления требуемых зависимостей

  • Протобуф до 3.3.0 -> 3.5.0.
  • GFLAGS до 2.2.0 -> 2.2.1.
  • CBC 2.9.8 -> 2.9.9.
  • Добавьте модуль Python Six (1,10) в качестве необходимой зависимости для Python.

Исправление ошибок

  • Получите запрос № 494 Рефакторинг. Добавление комментариев к Intellisense в некоторых редакторах. Спасибо Мэтью Мур .
  • Получите запрос # 516 Инструкция для F # Sandalone Binary. Спасибо Мэтью Мур .
  • Улучшить точность в GLOP.

SAT Solver

  • Улучшить внутренний решатель SAT, исправить различные ошибки.
  • Добавьте ограничение VRP в решатель SAT, связанный с решателем LP.
  • Измените наблюдатель из решения в решателе SAT, чтобы взять CpSolverResponse в качестве параметра.
  • Улучшить использование GLOP в SAT Solver.
  • Ускорение SAT-LP Connection.
  • Добавьте ограничение водохранилища в формат SAT CP_Model Protobuf.

SAT/Python

Примеры

  • Перепишите rcpsp_parser , чтобы использовать формат Protobuf для хранения проблемы.
  • Улучшение анализатора RCPSP.

Октябрь 2017 г.

Объявление о выпуске версии v6.5

Мы выпустили или сталкиваются с версией 6.5. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Изменение платформ

  • Модуль PYPI Py3-ortools был объединен в модуль Ortools. Теперь есть только один модуль: «Ortools».
  • Основным форматом для этих модулей Python теперь являются колесные файлы. Чтобы установить или инструкции для Python от PYPI, просто запустите pip install ortools . Вам нужна недавняя версия PIP, установленную (> = 9.0.1). Это должно вывести последний релиз (v6.5).

Ошибка в программе исправлена

Файл JAR Protobuf теперь правильно построен с составленными классами.

Новые примеры

  • Больше примеров F# было внесено в каталог примеров/FSHARP (еще раз спасибо Мэтью Мур).
  • Примеры Java MIP также были внесены (спасибо, Дариан).

Сентябрь 2017 г.

Объявление о выпуске версии v6.4

Мы выпустили или сталкиваются с версией 6.4. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Изменение платформ

  • Модули PYPI на платформах Linux теперь доставляются в виде колесных файлов с использованием тега ManyLinux1. Спасибо Federico Ficarelli . С этим изменением мы отступили модули для линины, представленные в выпуске в июле 2017 года.

Новые возможности

  • Улучшенный метод масштабирования, используемый внутри GLOP.
  • Исправьте обертку оценщиков в библиотеке маршрутизации C#. Спасибо Devnamedzed .
  • Повышение производительности представленной Flatzinc для больших моделей.
  • По умолчанию используйте SAT SAT для Flatzinc.
  • Повышение производительности основного подхода для решателя SAT.
  • Исправьте ошибку в алгоритме линейного назначения, который неверно не удался.
  • Добавлены примеры F# в Ortools/Примеры/FSHARP.
  • Удалить проверку на положительные штрафы в библиотеке маршрутизации.

август 2017 г.

Объявление о выпуске версии v6.3

Мы выпустили или тщательную версию 6.3. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Новые файлы загрузки

Файлы колеса Python для Linux теперь доступны для загрузки на странице выпуска или Tools , а также последние версии всех загрузок.

Minizinc Solver

Эта версия содержит окончательный код SAT и Flatzinc, отправленный для Challenge Minizinc 2017 .

июль 2017 г.

Объявление о выпуске версии V6.2

Мы выпустили или сталкиваются с версией 6.2. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Изменение платформ

  • Теперь мы поддерживаем несколько бинарных распределений Linux (Ubuntu 14.04, 16.04, 17.04, centos 7, debian 9).
  • Модули PYPI на платформах Linux теперь включают тег, который описывает распределение (Ubuntu-1404, Ubuntu-16.04, Ubuntu-17.04, CentOS-7, Debian-9).

Новые возможности

Мы добавили поддержку Docker для создания артефактов Linux. Перейдите в or-tools/tools/docker и посмотрите на Makefile , чтобы увидеть возможные цели ( make archive , make pypi и make pypi3 ).

Эти команды создадут подкаталог export и добавят в него бинарные артефакты.

июнь 2017 г.

Объявление о выпуске версии v6.1

Мы выпустили или сталкиваются с версией 6.1. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Изменение платформ

  • Visual Studio 2017 поддерживается; Visual Studio 2013 больше не поддерживается.
  • Версии MacOS 10.9 и выше поддерживаются.

Новые возможности

Мы добавили новый формат ProtoBuf для нашего решателя CP-SAT. См. ortools/sat/cp_model.proto , чтобы определить вашу модель, и ortools/sat/cp_model_solver.h , чтобы решить вашу проблему.

Исправление ошибок

Выпуск № 420: Мы исправили атрибут __version__ на модулях Python PYPI на всех платформах.

май 2017 г.

Объявление о выпуске версии v6.0

Мы выпустили или сталкиваются с версией 6.0. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Новая структура каталогов в C ++

Мы изменили источник/включали структуру или инструкции при использовании C ++. Цель состоит в том, чтобы обеспечить лучшую инкапсуляцию C ++, включающие файлы. Он также имеет преимущество в выравнивании структур C ++ и каталога Python.

  • src/ был переименован ortools/ .
  • Все команды #include в файлах C ++ теперь добавлены префикс ortools . #include "constraint/constraint_solver.h" теперь #include "ortools/constraint/constraint_solver.h" .

Новые возможности

  • Базель поддержка. Теперь вы можете построить или инструменты Bazel , инструмент Google's Build. Он работает на Linux и Mac OS X. После загрузки Bazel версии 0.4.5 или более поздней версии измените каталог на или постройте примеры: bazel build examples/cpp/...

Маршрутизация

Мы внедрили поддержку для перерывов (например, время простоя автомобиля из -за того, что водители обедают) в библиотеке маршрутизации. Эта функция показана в примере cvrptw_with_breaks.cc .

Поддержка SCIP

Линейная обертка решателя теперь поддерживает SCIP 4.0. Теперь вам нужно сначала построить SCIP, а затем сказать или сказать, что вы будете использовать его. Инструкции доступны здесь .

Поддержка GLPK

Мы также изменили путь с Build с GLPK. Глянь сюда .

Уборки

  • Мы удалили все использование hash_map и hash_set в кодовой базе C ++, поскольку они устарели. Они были заменены на неупорядоченное_MAP и Unordered_set из STL.
  • Очистка C# Makefiles, любезно предоставлено Майклом Пауэллом.

Январь 2017 г.

Объявление о выпуске версии V5.1

Мы выпустили или сталкиваются с версией 5.1. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Новые возможности

Установка

Маршрутизация

Внедрил алгоритм для вычисления нижней границы с удерживаемой карпами для симметричных проблем с продажателем. Это позволяет вам вычислять верхнюю границу с разрывом между стоимостью потенциально не оптимального решения и стоимостью оптимального решения.

  • Добавлен новый метод в библиотеку маршрутизации транспортного средства, RoutingModel::SetBreakIntervalsOfVehicle , которая позволяет добавлять интервалы разрыва - периоды времени, когда транспортное средство не может выполнять какие -либо задачи (например, путешествие или посещение узла). Для примера, который использует эту опцию, см. CVRPTW_WITH_BREAKS.CC

Планирование

SAT Solver

  • Совокупное ограничение SAT Solver теперь принимает дополнительные интервалы, созданные с помощью метода NewOptionalInterval . Для примера см. Https://github.com/google/or-tools/blob/master/examples/cpp/rcpsp_sat.cc .
  • Теперь вы можете решить максимум SAT (задача максимальной удовлетворенности_, ​​указав цель как взвешенную сумму литералов. Больше не необходима для создания промежуточной целочисленной переменной.

Улучшение производительности

  • SAT Solver - улучшенная производительность SAT решателя, особенно для кумулятивного ограничения.
  • Glop Solver - Улучшенная численная надежность решателя GLOP, который теперь возвращает еще более точные решения жестких численных задач.
  • Flatzinc Solver
  • Значительно улучшенная производительность бэкэнд SAT для переводчика Flatzinc.
  • Упростил интерфейс C# Flatzinc. Для примера нового интерфейса см .

Исправление ошибок

  • Использование эвристики PathCheapestArc на моделях маршрутизации с одним транспортным средством и боковыми ограничениями иногда приводит к тому, что решатель работает в течение чрезмерно долгого времени. Это было исправлено, правильно приняв во внимание побочные ограничения.
  • В Java решатель маршрутизации иногда падает при решении проблем маршрутизации транспортных средств. Это было исправлено в последнем выпуске.

ноябрь 2016 г.

Объявление о выпуске версии V5.0

Мы выпустили или тщательную версию 5.0. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Заводящие примеры

  • Введены цели, специфичные для языка, которые облегчают компиляцию и запуск ваших программ, а также примеры, которые поставляются с или инструментами.

Сидел

Flatzinc

Решатель ограничений

  • Реализовано следующие ограничения:
  • At Most : устанавливает верхнюю границу для количества переменных, которые равны данному значению.
  • MakePathPrecedenceSonstraint и MakePathTransitPrecedenceConstraint : реализуйте ограничение приоритета для набора пар.

Маршрутизация

  • Реализованный AddatSolutionCallback , который представляет собой обратный вызов, называемый каждый раз, когда решение встречается во время поиска.
  • Удалили конструкторы без депо RoutingModel. Указание хотя бы одного депо в модели маршрутизации теперь является обязательной.

Сентябрь 2016 г.

Объявление о выпуске версии V4.4

Мы выпустили или сталкиваются с версией 4.4. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Сидел

  • Расширенное планирование API и модифицированные примеры (Weeshed_Tardiness_SAT и Jobshop_SAT) для его использования.

График

  • Добавлены черты итератора в классы графиков.

Или дистрибуция диска

  • Пакет Nuget снова поддерживается.

август 2016 г.

Объявление о выпуске версии V4.3

Мы выпустили или тщательную версию 4.3. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Решатель ограничений

  • Внедрено NotBetween методом ограничения переменной находится за пределами данного интервала.

маршрутизация

  • Добавлен анализ модели для проверки существующих ограничений NotMember , как показано в этом примере , и используйте их в локальных поисковых фильтрах.
  • Добавлено локальное профилирование поиска.
  • Исправить местные движения.

Линейный решатель

  • Исправлена ​​отчетность по статусу SCIP.

Сидел

  • Реализованный метод SolveWithProvels для упрощения использования SAT -презентации.
  • Перегруппированный поиск в SRC/SAT/UTIL.H | CC.
  • Реализовано SMT (Lazy Clause Generation) Планирование ограничений: см. Jobshop_sat.cc и Wheesed_tardiness_sat.cc .

Глоп

  • Повышенная производительность за счет использования разреженности на большем количестве вычислений.

Flatzinc

  • Исправлены ошибки, найденные Minizinc Challenge.

Lp_data

  • Продолжение упрощения шаблонов в итераторах.

Или дистрибуция диска

  • C# Собрание теперь сильно названы по умолчанию.
  • Модернизировано до Protobuf3.0.0.
  • Добавлен сценарий Python для проверки или архивных зависимостей.

июль 2016 г.

Объявление о выпуске версии V4.2

Мы выпустили или сталкиваются с версией 4.2. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Решатель ограничений (маршрутизация)

  • Дизъюнкция теперь может быть определена с кардинальностью, которая представляет собой максимальное количество узлов, которые могут быть активными в рамках этой дизъюнкции. Например, если вы добавляете дизъюнкцию с N -узлами и кардинальностью K, то k -узлы среди N -узлов могут быть активными. Вы можете использовать новое определение AddDiscunction , чтобы сделать это.
  • Добавлена ​​поддержка для нескольких дизъюнкций на узел. Например, теперь вы можете добавить узел, n1, ко многим дизъюнкциям (D1..DM). Это увеличивает его шанс быть активным в любом из них. Введен более быстрый алгоритм поиска маршрутизации для проблем, связанных с разъединенными временными окнами.
  • Добавлены параметры решателя ограничений для параметров модели маршрутизации и log_search для параметров поиска маршрутизации.
  • Локальный алгоритм поиска быстрее с решением проблем с непересекающимися временными окнами. Проверьте пример CVRP_DISJOINT_TW.CC для получения более подробной информации.

GLOP (линейная оптимизация)

  • Представил более быстрый алгоритм простого.

Или дистрибуция диска

  • Один архив на платформу, а не отдельные архивы для каждого из C ++, Java и .net. Архивы Python все еще размещены на PYPI.
  • На PYPI мы переключились на модули колеса (.WHL) на Mac OS X и Windows. Представил основную схему нумерации. Эти цифры используются имена архива, версия, хранящаяся в общих библиотеках Mac OS X, модулях Python, .NET Assemblies. Первая версия, которую мы выпускаем, с этой схемой v4.2

июнь 2016 г.

Объявление о выпуске версии V2016-06

Мы выпустили версию V2016-06 или Tools. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Решатель ограничений

  • Удалили большинство экземпляров обратных вызовов (src/base/callback.h) из библиотеки CP.
  • Добавлено Notmemberct (переменная не может принадлежать к набору интервалов).

Библиотека маршрутизации

  • Несовместимое изменение: Чтобы указать емкость транспортных средств в AddDimensionWithVehicleCapacity , теперь вам необходимо пройти массив (вектор в C ++) вместо обратного вызова.

Глин

  • Изменить внутреннее представление редкой матрицы.
  • Улучшение производительности.

График

  • Перепишите алгоритмы Dijkstra и Bellman-Ford, чтобы заменить обратные вызовы на std::function (c ++).
  • Измените API различной реализации графика, когда итерация над дугами и узлами.

Сидел

  • Удалить неиспользованный метод ядра (узлы разрешения).
  • Добавлен писатель Drat, чтобы проверить доказательства на неудовлетворенность.
  • Добавить препроцессор.

Боп

  • Добавить новые районы.

Примеры

  • C ++: избавление от FileLinerEader в примерах.
  • Данные: Добавьте проблемы с расписанием с одним машин.

Документация

апрель 2016 г.

Объявление о выпуске версии V2016-04

Мы выпустили версию V2016-04 или Tools. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Обновленные зависимости

декабрь 2015 г.

Объявление о выпуске версии V2015-12

Мы выпустили или сталкиваются с версией V2015-12. Чтобы обновить вашу версию, см. Подходящий раздел установки OR OLOULS .

Решатель ограничений

  • Совместимость сломана в большом поиске по соседству в решателе CP (см. examples/cpp/ls_api.cc , examples/python/pyls_api.py , examples/csharp/csls_api.cs и examples/com/google/ortools/sample/LsApi.java , чтобы увидеть новый API).
  • Очистил обертывание Python. Поддержите пользовательское решение в решателе CP (см. examples/test/test_cp_api.py , чтобы увидеть API в действии).
  • Различные улучшения и исправления ошибок.

Сентябрь 2015 г.

Объявление первого релиза на GitHub.

Файлы будут храниться там с этого момента.

Flatzinc

  • Добавлена ​​бинарные архивы для интерпретатора Flatzinc (см. Www.minizinc.org ).
  • Содержит несколько исправлений для версии, используемой в вызове.