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

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

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

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

май 2024 г.

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

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

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

март 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 для создания переменных.
  • посмотреть задание
  • см. bin_packing
• Полная информация о вводе

ПДЛП

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

CP-САТ

• Улучшения производительности. (feasibility_jump, lin_max)
• Улучшите управление обрезкой
• Новый рабочий объект Object_shaving_search, предназначенный для улучшения нижней границы цели (при минимизации).
• Ввод аннотаций для python cp_model.py
• Экспериментальная частичная поддержка панд в cp_model.py
  • посмотреть задание
  • см. bin_packing
• Экспериментальный локальный обыск основан на нарушениях работников:
  • включено с параметрами: 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
• SWIG 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 .

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

• Abseil-cpp 20200923.3 обновлен до 20210324.1 LTS.
• Protobuf 3.15.3 обновлен до 3.15.8.
• Java: jna-платформа 5.5.0 обновлена ​​до 5.8.0

Джава

• OR-Tools теперь доступен на Maven Central (см. com.google.ortools:ortools-java ).

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

• Улучшите многопоточность при использовании решателя 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 ).

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

• protobuf v3.10.0 обновлен до v3.11.2 ( #1829 ).

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

Следующие проблемы были исправлены в 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 Framework >= 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() .
• В API Java добавлены методы 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 имеет следующие новые и обновленные зависимости:

• Новое: Abseil-cpp
• gflags 2.2.1 обновлен до 2.2.2

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

• Новый менеджер индексов для программ маршрутизации
• Поддержка VRP с самовывозом и доставкой
• Поддержка лямбда-функций в Java и C#.

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

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

Примечание. Стандартные индексы локаций — от 0 до N-1, где N — количество локаций (включая депо). По техническим причинам внутренние индексы местоположения решателя могут находиться за пределами этого диапазона.

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

• Включите или импортируйте RoutingIndexManager в C++ и Java.
• Объявить RoutingIndexManager
• Добавьте 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 :

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

Примечание. В предыдущих версиях эти аргументы передавались непосредственно в RoutingModel вместо 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 callback 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> — это путь к каталогу, содержащему программу.

Примечание. Для запуска программ больше не требуется редактировать Makefile.

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

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

Флэтцинк

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

Взносы

• Добавьте поддержку Binder. Спасибо Кевину Мэдеру .
• Сделайте DecisionVisitor типом директора в привязках Java. Спасибо Джереми Эпторпу .

июль 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.
• Добавьте питон или инструкции на основе Cmake Build.
• Создать пакет Python (колеса) с использованием Cmake.

Взносы

• Исправить Winsock2.h переопределения в Windows. Спасибо Флоренту Толлин де Риварол .
• Добавить F# поддержку (экспериментальный). Спасибо Мэтью Мур . ПРИМЕЧАНИЕ. Доступно только с Makefile Builder.
• Добавить стандартную поддержку .NET (экспериментальная). Спасибо Ziad El Malki . ПРИМЕЧАНИЕ. Доступно только с 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

• Введение SAT API в Python.
• Код в ortools/sat/python/cp_model.py .
• Добавьте примеры в примерах/ Python/ :
• Назначение_SAT.PY
• Назначение_with_constraints_sat.py
• code_samples_sat.py
• cp_is_fun_sat.py
• gate_scheduling_sat.py
• hidato_sat.py
• jobshop_ft06_sat.py
• nqueens_sat.py
• Медсестры_sat.py
• rcpsp_sat.py
• Steel_mill_slab_sat.py
• Worker_schedule_sat.py
• Добавьте поддержку ноутбука Ipython .
• Примеры 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 .

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

Установка

• Введены более простые процедуры для установки или инструкции, либо из двоичных распределений, либо из исходного кода. См. Установку или инструкции из двоичного или установку или инструкции из Source для получения дополнительной информации.

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

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

• Добавлен новый метод в библиотеку маршрутизации транспортного средства, 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 .

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

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

Сидел

• Добавлена ​​поддержка программирования ограничений.
• Реализовано ограничения Diffn , кумулятивные , схемы и субсиргии .
• Реализовал проверку перегрузки на основе алгоритма фильтрации энергии MAX для дискретного кумулятивного ограничения .
• Реализовал все различное согласованное пропагатор , который реализует лучшее распространение для ограничений.

Flatzinc

• Реализовано решатель SAT для проблем 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 .

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

• Используйте Protobufs вместо флагов в библиотеках программирования и маршрутизации ограничений. См. Http://or-tools.blogspot.fr/2016/02/heads-uppering-comingabitability-in.html для деталей.

декабрь 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 ).
• Содержит несколько исправлений для версии, используемой в вызове.