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

Обратные вызовы, не зависящие от решателя

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

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

  1. отложенные ограничения;

  2. пользовательские сечения;

  3. эвристические решения.

Доступные решатели

Поддержка обратных вызовов, не зависящих от решателя, ограничена несколькими решателями. К ним относятся CPLEX, GLPK, Gurobi, Xpress и SCIP (SCIP не поддерживает отложенные ограничения).

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

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

Допустимые и недопустимые действия во время обратных вызовов, не зависящих от решателя

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

Использование любой другой части API JuMP (например, добавление ограничения с помощью @constraint или изменение границы переменной с помощью set_lower_bound) является неопределенным действием, и решатель может выдать ошибку, вернуть неверное решение или инициировать аварийное завершение работы Julia.

В любом из трех не зависящих от решателя обратных вызовов можно запросить два вида информации:

  • callback_node_status](../api.md#JuMP.callback_node_status-Tuple{Any, GenericModel}) returns an [MOI.CallbackNodeStatusCode перечисление, указывающее, является ли текущее прямое решение целочисленно допустимым.

  • callback_value returns the current primal solution of a variable.

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

Если необходимо изменить задачу в обратном вызове, следует использовать отложенное ограничение.

Задать каждый обратный вызов можно только один раз. При повторном вызове set предыдущий обратный вызов будет перезаписан. Кроме того, при использовании обратного вызова, не зависящего от решателя, задать зависимый от решателя обратный вызов нельзя.

Отложенные ограничения

Отложенные ограничения полезны в случае, когда полный набор ограничений слишком велик для явного включения в исходную формулировку. Когда решатель MIP находит новое решение, например с помощью эвристики или в результате решения задачи в узле дерева ветвей и границ, он дает пользователю возможность указать ограничения, которые сделают текущее решение недопустимым. Дополнительные сведения об отложенных ограничениях см. в этой записи в блоге Пола Рубина (Paul Rubin).

Обратный вызов отложенного ограничения можно задать посредством следующего синтаксиса:

julia> import GLPK

julia> model = Model(GLPK.Optimizer);

julia> @variable(model, x <= 10, Int)
x

julia> @objective(model, Max, x)
x

julia> function my_callback_function(cb_data)
           status = callback_node_status(cb_data, model)
           if status == MOI.CALLBACK_NODE_STATUS_FRACTIONAL
               # `callback_value(cb_data, x)` не является целым числом (с некоторым допуском).
               # Если, например, генератору отложенного ограничения требуется
               # целочисленно допустимое прямое решение, здесь можно добавить `return`.
               return
           elseif status == MOI.CALLBACK_NODE_STATUS_INTEGER
               # `callback_value(cb_data, x)` является целым числом (с некоторым допуском).
           else
               @assert status == MOI.CALLBACK_NODE_STATUS_UNKNOWN
               # `callback_value(cb_data, x)` может быть дробным или целым числом.
           end
           x_val = callback_value(cb_data, x)
           if x_val > 2 + 1e-6
               con = @build_constraint(x <= 2)
               MOI.submit(model, MOI.LazyConstraint(cb_data), con)
           end
       end
my_callback_function (generic function with 1 method)

julia> set_attribute(model, MOI.LazyConstraintCallback(), my_callback_function)

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

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

 
model = Model(GLPK.Optimizer)
@variable(model, x <= 10, Int)
@objective(model, Max, x)
function bad_callback_function(cb_data)
    # Don't do this!
    con = @build_constraint(x <= 2)
    MOI.submit(model, MOI.LazyConstraint(cb_data), con)
end
function good_callback_function(cb_data)
    if callback_value(x) > 2
        con = @build_constraint(x <= 2)
        MOI.submit(model, MOI.LazyConstraint(cb_data), con)
    end
end
set_attribute(model, MOI.LazyConstraintCallback(), good_callback_function)

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

Пользовательские сечения

Пользовательские сечения, или просто сечения, дают пользователю возможность сократить ослабление задачи LP, используя специальные знания, которые решатель не в состоянии вывести из модели. Как и в случае с отложенными ограничениями, когда решатель MIP достигает нового узла дерева ветвей и границ, он дает пользователю возможность предоставить сечения, чтобы сделать текущее ослабленное (дробное) решение недопустимым в расчете на получение целочисленного решения. Дополнительные сведения о разнице между пользовательскими сечениями и отложенными ограничениями см. в упомянутой выше записи в блоге.

Обратный вызов пользовательского сечения можно задать посредством следующего синтаксиса:

julia> import GLPK

julia> model = Model(GLPK.Optimizer);

julia> @variable(model, x <= 10.5, Int)
x

julia> @objective(model, Max, x)
x

julia> function my_callback_function(cb_data)
           x_val = callback_value(cb_data, x)
           con = @build_constraint(x <= floor(x_val))
           MOI.submit(model, MOI.UserCut(cb_data), con)
       end
my_callback_function (generic function with 1 method)

julia> set_attribute(model, MOI.UserCutCallback(), my_callback_function)

Пользовательские сечения не должны изменять множество целочисленных допустимых решений. Аналогично, пользовательские сечения могут удалять только дробные решения. Если добавить сечение, которое удаляет целочисленное решение (даже не оптимальное), решатель может вернуть неверное решение.

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

Эвристические решения

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

Некоторые эвристические решения берут целочисленные решения и исследуют их «локальную окрестность» (например, инвертируя двоичные переменные, фиксируя некоторые переменные и решая более узкую задачу MILP), а другие берут дробные решения и пытаются округлить их рациональным образом.

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

Обратный вызов эвристического решения можно задать посредством следующего синтаксиса:

julia> import GLPK

julia> model = Model(GLPK.Optimizer);

julia> @variable(model, x <= 10.5, Int)
x

julia> @objective(model, Max, x)
x

julia> function my_callback_function(cb_data)
           x_val = callback_value(cb_data, x)
           status = MOI.submit(
               model, MOI.HeuristicSolution(cb_data), [x], [floor(Int, x_val)]
           )
           println("I submitted a heuristic solution, and the status was: ", status)
       end
my_callback_function (generic function with 1 method)

julia> set_attribute(model, MOI.HeuristicCallback(), my_callback_function)

Третий аргумент submit — это вектор переменных JuMP, а четвертый — это вектор значений, соответствующих каждой переменной.

MOI.submit возвращает перечисление, которое зависит от того, принял ли решатель решение. Возможные коды возврата:

  • MOI.HEURISTIC_SOLUTION_ACCEPTED

  • MOI.HEURISTIC_SOLUTION_REJECTED

  • MOI.HEURISTIC_SOLUTION_UNKNOWN

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

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