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

Модели

Модели JuMP — это базовые структурные элементы, которые используются для построения задач оптимизации. Они содержат такие данные, как переменные и ограничения, а также информацию об используемом решателе и даже о решении.

В JuMP термин «оптимизатор» используется как синоним термина «решатель». Мы будем придерживаться следующего соглашения: термин «решатель» будет относиться к базовому программному обеспечению, а термин «оптимизатор» будет означать объект Julia, в который заключен решатель. Например, HiGHS — это решатель, а HiGHS.Optimizer — оптимизатор.

Список доступных решателей см. в разделе Supported solvers.

Создание модели

Чтобы создать модель, передайте оптимизатор в Model:

julia> model = Model(HiGHS.Optimizer)
A JuMP Model
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Если на момент создания неизвестно, какой оптимизатор будет использоваться, создайте модель без оптимизатора, а затем вызовите set_optimizer в любой момент до вызова optimize!:

julia> model = Model()
A JuMP Model
├ solver: none
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

julia> set_optimizer(model, HiGHS.Optimizer)

Не знаете, что означают поля Model mode и CachingOptimizer state? Прочитайте раздел Backends.

В чем различие?

Для большинства моделей между передачей оптимизатора в Model и вызовом set_optimizer нет разницы.

Однако если оптимизатор не поддерживает ограничение в модели, время возникновения ошибки может отличаться:

  • Если передается оптимизатор, ошибка возникнет при попытке добавить ограничение.

  • Если вызывается set_optimizer, ошибка возникнет при попытке решить модель с помощью optimize!.

Поэтому большинству пользователей следует передавать оптимизатор в Model](../api.md#JuMP.Model): это позволит раньше получать предупреждение о том, что решатель не подходит для создаваемой модели. Однако если вы изменяете задачу, добавляя и удаляя различные типы ограничений, вам может потребоваться использовать set_optimizer. Пример того, когда это может быть полезно, см. в разделе [Switching optimizer for the relaxed problem.

Сокращение задержки до первого решения

По умолчанию JuMP использует мосты для переформулирования создаваемой модели в эквивалентную модель, поддерживаемую решателем.

Однако если модель уже поддерживается решателем, мосты увеличивают задержку (см. раздел The "time-to-first-solve" issue). Это особенно заметно в случае с небольшими моделями.

Чтобы сократить задержку до первого решения, попробуйте передать add_bridges = false.

julia> model = Model(HiGHS.Optimizer; add_bridges = false);

или

julia> model = Model();

julia> set_optimizer(model, HiGHS.Optimizer; add_bridges = false)

Однако будьте осторожны. Если для вашего сочетания модели и решателя требуются мосты, будет выдана ошибка:

julia> model = Model(SCS.Optimizer; add_bridges = false);


julia> @variable(model, x)
x

julia> @constraint(model, 2x <= 1)
ERROR: Constraints of type MathOptInterface.ScalarAffineFunction{Float64}-in-MathOptInterface.LessThan{Float64} are not supported by the solver.

If you expected the solver to support your problem, you may have an error in your formulation. Otherwise, consider using a different solver.

The list of available solvers, along with the problem types they support, is available at https://jump.dev/JuMP.jl/stable/installation/#Supported-solvers.
[...]

Решатели, принимающие среды

Некоторые решатели принимают (или требуют) позиционные аргументы, например лицензионную среду или путь к исполняемому файлу. Для таких решателей можно передать в Model функцию, которая принимает ноль аргументов и возвращает экземпляр оптимизатора.

Распространенным случаем использования является передача среды или вложенного решателя в оптимизатор:

julia> import HiGHS

julia> import MultiObjectiveAlgorithms as MOA

julia> model = Model(() -> MOA.Optimizer(HiGHS.Optimizer))
A JuMP Model
├ solver: MOA[algorithm=MultiObjectiveAlgorithms.Lexicographic, optimizer=HiGHS]
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Параметры решателей

В JuMP термин «атрибут» используется как синоним термину «параметр». Для создания оптимизатора с инициализированными атрибутами используйте метод optimizer_with_attributes:

julia> model = Model(
           optimizer_with_attributes(HiGHS.Optimizer, "output_flag" => false),
       )
A JuMP Model
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Можно также воспользоваться методом set_attribute, чтобы задать атрибут после создания модели:

julia> model = Model(HiGHS.Optimizer);

julia> set_attribute(model, "output_flag", false)

julia> get_attribute(model, "output_flag")
false

Атрибуты можно также изменять внутри объекта optimizer_with_attributes:

julia> solver = optimizer_with_attributes(HiGHS.Optimizer, "output_flag" => true);

julia> get_attribute(solver, "output_flag")
true

julia> set_attribute(solver, "output_flag", false)

julia> get_attribute(solver, "output_flag")
false

julia> model = Model(solver);

Изменение числовых типов

По умолчанию коэффициенты аффинных и квадратичных выражений — это числа типа Float64 или Complex{Float64} (см. раздел Complex number support).

Тип Float64 можно изменить с помощью конструктора GenericModel:

julia> model = GenericModel{Rational{BigInt}}();

julia> @variable(model, x)
x

julia> @expression(model, expr, 1 // 3 * x)
1//3 x

julia> typeof(expr)
GenericAffExpr{Rational{BigInt}, GenericVariableRef{Rational{BigInt}}}

Использование типа value_type, отличного от Float64, — это сложная операция, к которой следует прибегать только в том случае, если базовый решатель действительно решает задачу с использованием указанного типа значения.

Nonlinear Modeling в настоящее время ограничено числовым типом Float64.

Вывод модели

По умолчанию show(model) выводит сводку задачи:

julia> model = Model(); @variable(model, x >= 0); @objective(model, Max, x);

julia> model
A JuMP Model
├ solver: none
├ objective_sense: MAX_SENSE
│ └ objective_function_type: VariableRef
├ num_variables: 1
├ num_constraints: 1
│ └ VariableRef in MOI.GreaterThan{Float64}: 1
└ Names registered in the model
  └ :x

Используйте print для вывода формулировки модели (в IJulia она отображается в разметке LaTeX).

julia> print(model)
Max x
Subject to
 x ≥ 0

Этот формат характерен именно для JuMP и может измениться в будущем выпуске. Он не предназначен для использования в качестве формата экземпляра. Чтобы записать модель в файл, используйте вместо этого метод write_to_file.

Используйте latex_formulation для отображения модели в формате LaTeX.

julia> latex_formulation(model)
$$ \begin{aligned}
\max\quad & x\\
\text{Subject to} \quad & x \geq 0\\
\end{aligned} $$

Для отображения модели в IJulia (и Documenter) в формате LaTeX ячейка должна завершаться методом latex_formulation:

latex_formulation(model)
$$ \begin{aligned}
\max\quad & x\\
\text{Subject to} \quad & x \geq 0\\
\end{aligned} $$

Отключение вывода

Чтобы отключить или включить вывод результатов работы решателя, используйте методы set_silent и unset_silent.

julia> model = Model(HiGHS.Optimizer);

julia> set_silent(model)

julia> unset_silent(model)

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

Установка предельного времени

Для управления ограничениями по времени используйте методы set_time_limit_sec, unset_time_limit_sec и time_limit_sec.

julia> model = Model(HiGHS.Optimizer);

julia> set_time_limit_sec(model, 60.0)


julia> time_limit_sec(model)
60.0

julia> unset_time_limit_sec(model)

julia> limit = time_limit_sec(model)

julia> limit === nothing
true

Если временное ограничение представлено объектом Dates.Period, преобразуйте его в тип Float64 для set_time_limit_sec с помощью следующего кода:

julia> import Dates

julia> seconds(x::Dates.Period) = 1e-3 * Dates.value(round(x, Dates.Millisecond))
seconds (generic function with 1 method)

julia> set_time_limit_sec(model, seconds(Dates.Hour(1)))

julia> time_limit_sec(model)
3600.0

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

Запись модели в файл

JuMP может записывать модели в файлы различных форматов с помощью методов write_to_file и Base.write.

Для большинства распространенных форматов файлов тип файла определяется по расширению.

Например, так можно выполнить запись в файл MPS:

julia> model = Model();

julia> write_to_file(model, "model.mps")

Другие поддерживаемые форматы файлов:

Для записи в определенный поток io::IO используйте метод Base.write](../api.md#Base.write-Tuple{IO, GenericModel}). Чтобы указать тип файла, передайте перечисление [MOI.FileFormats.FileFormat.

julia> model = Model();

julia> io = IOBuffer();

julia> write(io, model; format = MOI.FileFormats.FORMAT_MPS)

Считывание модели из файла

Модели JuMP можно создавать из файлов различных форматов с помощью методов read_from_file и Base.read.

julia> model = read_from_file("model.mps")
A JuMP Model
├ solver: none
├ objective_sense: MIN_SENSE
│ └ objective_function_type: AffExpr
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

julia> seekstart(io);

julia> model2 = read(io, Model; format = MOI.FileFormats.FORMAT_MPS)
A JuMP Model
├ solver: none
├ objective_sense: MIN_SENSE
│ └ objective_function_type: AffExpr
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Так как форматы файлов не сериализуют контейнеры переменных и ограничений JuMP, имена в модели не регистрируются. Поэтому к именованным переменным и ограничениям невозможно получить доступ посредством model[:x]. Вместо этого для доступа к определенным переменным и ограничениям используйте метод variable_by_name или constraint_by_name.

Ослабление целочисленности

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

julia> model = Model();

julia> @variable(model, x, Int)
x

julia> num_constraints(model, VariableRef, MOI.Integer)
1

julia> undo = relax_integrality(model);

julia> num_constraints(model, VariableRef, MOI.Integer)
0

julia> undo()

julia> num_constraints(model, VariableRef, MOI.Integer)
1

Переключение оптимизатора для решения задачи с ослабленными ограничениями

Распространенной причиной ослабления целочисленности является вычисление двойственных переменных в задаче с ослабленными ограничениями. Однако некоторые частично целочисленные линейные решатели (например, Cbc) не возвращают двойственных решений, даже если задача не имеет ограничений целочисленности.

Поэтому после relax_integrality следует вызвать set_optimizer с решателем, который поддерживает двойственные решения, например Clp.

Например, вместо следующего кода:

using JuMP, Cbc
model = Model(Cbc.Optimizer)
@variable(model, x, Int)
undo = relax_integrality(model)
optimize!(model)
reduced_cost(x)  # Выдает ошибку

выполните такой:

using JuMP, Cbc, Clp
model = Model(Cbc.Optimizer)
@variable(model, x, Int)
undo = relax_integrality(model)
set_optimizer(model, Clp.Optimizer)
optimize!(model)
reduced_cost(x)  # Работает

Получение матричного представления

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

julia> begin
           model = Model()
           @variable(model, x >= 1, Bin)
           @variable(model, 2 <= y)
           @variable(model, 3 <= z <= 4, Int)
           @constraint(model, x == 5)
           @constraint(model, 2x + 3y <= 6)
           @constraint(model, -4y >= 5z + 7)
           @constraint(model, -1 <= x + y <= 2)
           @objective(model, Max, 1 + 2x)
       end;

julia> data = lp_matrix_data(model);

julia> data.A
4×3 SparseArrays.SparseMatrixCSC{Float64, Int64} with 7 stored entries:
 1.0    ⋅     ⋅
  ⋅   -4.0  -5.0
 2.0   3.0    ⋅
 1.0   1.0    ⋅

julia> data.b_lower
4-element Vector{Float64}:
   5.0
   7.0
 -Inf
  -1.0

julia> data.b_upper
4-element Vector{Float64}:
  5.0
 Inf
  6.0
  2.0

julia> data.x_lower
3-element Vector{Float64}:
 1.0
 2.0
 3.0

julia> data.x_upper
3-element Vector{Float64}:
 Inf
 Inf
  4.0

julia> data.c
3-element Vector{Float64}:
 2.0
 0.0
 0.0

julia> data.c_offset
1.0

julia> data.sense
MAX_SENSE::OptimizationSense = 1

julia> data.integers
1-element Vector{Int64}:
 3

julia> data.binaries
1-element Vector{Int64}:
 1

Типы задач, поддерживаемые методом lp_matrix_data](../api.md#JuMP.lp_matrix_data-Union{Tuple{GenericModel{T}}, Tuple{T}} where T), и структура выводимых им матриц намеренно ограничены. В первую очередь он предназначен для обучения и отладки. Его не следует использовать для взаимодействия с решателями; вместо этого см. раздел [Implementing a solver interface.

Бэкенды

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

Модель JuMP Model](../api.md#JuMP.Model) — это тонкая оболочка вокруг бэкенда типа [MOI.ModelLike, который содержит задачу оптимизации и действует как решатель оптимизации.

Однако если модель создается, например, посредством вызова Model(HiGHS.Optimizer), то бэкендом будет не HiGHS.Optimizer, а более сложный объект.

Получить доступ к бэкенду MOI из JuMP можно с помощью функции backend. Давайте посмотрим, что представляет собой backend для модели JuMP Model:

julia> model = Model(HiGHS.Optimizer);

julia> b = backend(model)
MOIU.CachingOptimizer
├ state: EMPTY_OPTIMIZER
├ mode: AUTOMATIC
├ model_cache: MOIU.UniversalFallback{MOIU.Model{Float64}}
│ ├ ObjectiveSense: FEASIBILITY_SENSE
│ ├ ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
│ ├ NumberOfVariables: 0
│ └ NumberOfConstraints: 0
└ optimizer: MOIB.LazyBridgeOptimizer{HiGHS.Optimizer}
  ├ Variable bridges: none
  ├ Constraint bridges: none
  ├ Objective bridges: none
  └ model: A HiGHS model with 0 columns and 0 rows.

Вот так. Хотя мы передали HiGHS.Optimizer, бэкенд — гораздо более сложный объект.

CachingOptimizer

MOIU.CachingOptimizer — это слой, который абстрагирует различие между решателями, поддерживающими пошаговое изменение (например, добавление переменных по одной), и решателями, требующими всю задачу в одном вызове API (например, принимающими только матрицы A, b и c линейной программы).

Он состоит из двух частей:

  1. Кэша, позволяющего создавать и изменять модель пошагово:

julia> b.model_cache
MOIU.UniversalFallback{MOIU.Model{Float64}}
├ ObjectiveSense: FEASIBILITY_SENSE
├ ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
├ NumberOfVariables: 0
└ NumberOfConstraints: 0

  1. Оптимизатора, который служит для решения задачи:

julia> b.optimizer
MOIB.LazyBridgeOptimizer{HiGHS.Optimizer}
├ Variable bridges: none
├ Constraint bridges: none
├ Objective bridges: none
└ model: A HiGHS model with 0 columns and 0 rows.

В разделе LazyBridgeOptimizer объясняется, что представляет собой объект LazyBridgeOptimizer.

CachingOptimizer содержит логику для определения того, когда следует копировать задачу из кэша в оптимизатор, а когда оптимизатор можно эффективно обновить на месте.

CachingOptimizer может находиться в одном из трех состояний:

  • NO_OPTIMIZER: у CachingOptimizer нет оптимизатора.

  • EMPTY_OPTIMIZER: у CachingOptimizer есть пустой оптимизатор, но он не синхронизирован с кэшированной моделью.

  • ATTACHED_OPTIMIZER: у CachingOptimizer есть оптимизатор, и он синхронизирован с кэшированной моделью.

CachingOptimizer имеет два режима работы:

  • AUTOMATIC: состояние CachingOptimizer меняется при необходимости. Например, optimize! автоматически вызывает attach_optimizer (оптимизатор должен быть предварительно задан). Попытка добавить ограничение или выполнить изменение, не поддерживаемое оптимизатором, приводит к переходу в режим EMPTY_OPTIMIZER.

  • MANUAL: состояние CachingOptimizer должно меняться пользователем с помощью MOIU.reset_optimizer(::JuMP.Model), MOIU.drop_optimizer(::JuMP.Model), and MOIU.attach_optimizer(::JuMP.Model). Attempting to perform операция в неверном состоянии приводит к ошибке.

По умолчанию Model создает CachingOptimizer в режиме AUTOMATIC.

LazyBridgeOptimizer

Второй слой, который JuMP применяет автоматически, — это MOI.Bridges.LazyBridgeOptimizer. MOI.Bridges.LazyBridgeOptimizer — это слой MOI, который пытается преобразовать задачу из формулировки, предоставленной пользователем, в эквивалентную задачу, поддерживаемую решателем. При этом в оптимизатор могут добавляться новые переменные и ограничения. Преобразования выбираются из набора известных схем, называемых мостами.

Распространенным примером является мост, который разделяет интервальное ограничение, например @constraint(model, 1 <= x + y <= 2), на два ограничения: @constraint(model, x + y >= 1) и @constraint(model, x + y <= 2).

Для удаления мостового слоя используйте именованный аргумент add_bridges = false:

julia> model = Model(HiGHS.Optimizer; add_bridges = false)
A JuMP Model
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

julia> backend(model)
MOIU.CachingOptimizer
├ state: EMPTY_OPTIMIZER
├ mode: AUTOMATIC
├ model_cache: MOIU.UniversalFallback{MOIU.Model{Float64}}
│ ├ ObjectiveSense: FEASIBILITY_SENSE
│ ├ ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
│ ├ NumberOfVariables: 0
│ └ NumberOfConstraints: 0
└ optimizer: A HiGHS model with 0 columns and 0 rows.

Мосты можно добавлять в объект MOI.Bridges.LazyBridgeOptimizer и удалять из него с помощью методов add_bridge](../api.md#JuMP.add_bridge-Union{Tuple{T}, Tuple{S}, Tuple{GenericModel{S}, Type{<:MathOptInterface.Bridges.AbstractBridge}}} where {S, T}) и remove_bridge. Чтобы просмотреть мосты, используемые для переформулирования модели, используйте метод print_active_bridges. Дополнительные сведения см. в руководстве [Ellipsoid approximation.

Небезопасный бэкенд

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

julia> backend(model)
MOIU.CachingOptimizer
├ state: EMPTY_OPTIMIZER
├ mode: AUTOMATIC
├ model_cache: MOIU.UniversalFallback{MOIU.Model{Float64}}
│ ├ ObjectiveSense: FEASIBILITY_SENSE
│ ├ ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
│ ├ NumberOfVariables: 0
│ └ NumberOfConstraints: 0
└ optimizer: MOIB.LazyBridgeOptimizer{HiGHS.Optimizer}
  ├ Variable bridges: none
  ├ Constraint bridges: none
  ├ Objective bridges: none
  └ model: A HiGHS model with 0 columns and 0 rows.

julia> unsafe_backend(model)
A HiGHS model with 0 columns and 0 rows.

backend и unsafe_backend — это сложные подпрограммы. Ознакомьтесь с подводными камнями их использования в docstring и вызывайте их только в том случае, если требуется доступ к низкоуровневым функциям решателя.

Прямой режим

Использование CachingOptimizer приводит к тому, что JuMP сохраняет дополнительную копию модели в поле .model_cache. Чтобы избежать этих накладных расходов, создавайте модели JuMP с помощью direct_model:

julia> model = direct_model(HiGHS.Optimizer())
A JuMP Model
├ mode: DIRECT
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

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

Преимущество использования direct_model заключается в том, что между model и предоставленным оптимизатором нет дополнительных слоев (например, Cachingoptimizer или LazyBridgeOptimizer):

julia> backend(model)
A HiGHS model with 0 columns and 0 rows.

Недостатком прямого режима является отсутствие мостового слоя. Поэтому поддерживаются только те ограничения, которые изначально поддерживаются решателем. Например, HiGHS.jl не реализует квадратичные ограничения:

julia> model = direct_model(HiGHS.Optimizer());

julia> set_silent(model)

julia> @variable(model, x[1:2]);

julia> @constraint(model, x[1]^2 + x[2]^2 <= 2)
ERROR: Constraints of type MathOptInterface.ScalarQuadraticFunction{Float64}-in-MathOptInterface.LessThan{Float64} are not supported by the solver.

If you expected the solver to support your problem, you may have an error in your formulation. Otherwise, consider using a different solver.

The list of available solvers, along with the problem types they support, is available at https://jump.dev/JuMP.jl/stable/installation/#Supported-solvers.
Stacktrace:

Другим недостатком прямого режима является то, что способ выполнения запроса информации о решении после изменения задачи зависит от решателя. Это может приводить к ошибкам или к возвращению неверного значения решателем без предупреждения. Дополнительные сведения см. в разделе OptimizeNotCalled errors.