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

GLPK.jl

GLPK.jl — это оболочка для решателя библиотеки комплекта линейного программирования GNU.

Оболочка имеет два компонента:

  • тонкая оболочка вокруг полного API для C

  • интерфейс для MathOptInterface

Принадлежность

Эта оболочка поддерживается сообществом JuMP и не является проектом GNU.

Использование с JuMP

Чтобы использовать GLPK с JuMP, воспользуйтесь GLPK.Optimizer:

using JuMP, GLPK
model = Model(GLPK.Optimizer)
set_attribute(model, "tm_lim", 60 * 1_000)
set_attribute(model, "msg_lev", GLPK.GLP_MSG_OFF)

Если модель является прямо или двойственно невыполнимой, GLPK попытается найти свидетельство о невыполнимости. Это может быть дорого, особенно если вы не собираетесь использовать это свидетельство. В этом случае используйте:

model = Model(() -> GLPK.Optimizer(; want_infeasibility_certificates = false))

API MathOptInterface

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

Список поддерживаемых целевых функций:

  • MOI.ObjectiveFunction{MOI.ScalarAffineFunction{Float64}}

Список поддерживаемых типов переменных:

  • MOI.Reals

Список поддерживаемых типов ограничений:

  • MOI.ScalarAffineFunction{Float64} в MOI.EqualTo{Float64}

  • MOI.ScalarAffineFunction{Float64} в MOI.GreaterThan{Float64}

  • MOI.ScalarAffineFunction{Float64} в MOI.LessThan{Float64}

  • MOI.VariableIndex в MOI.EqualTo{Float64}

  • MOI.VariableIndex в MOI.GreaterThan{Float64}

  • MOI.VariableIndex в MOI.Integer

  • MOI.VariableIndex в MOI.Interval{Float64}

  • MOI.VariableIndex в MOI.LessThan{Float64}

  • MOI.VariableIndex в MOI.ZeroOne

Список поддерживаемых атрибутов моделей:

  • MOI.HeuristicCallback()

  • MOI.LazyConstraintCallback()

  • MOI.Name()

  • MOI.ObjectiveSense()

  • MOI.UserCutCallback()

Параметры

Параметры для GLPK подробно описаны в документации в формате PDF, но их трудно найти.

  • Параметры для решения линейной программы определены в разделе 2.8.1

  • Параметры для решения смешанной целочисленной программы определены в разделе 2.10.5

Однако наиболее полезными окажутся следующие.

Параметр Пример Объяснение

msg_lev

GLPK.GLP_MSG_ALL

Уровень сообщения для вывода в терминале

presolve

GLPK.GLP_ON

Включение или отключение предварительного решения

tol_int

1e-5

Абсолютный допуск для применимости целочисленных значений

tol_obj

1e-7

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

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

Вот пример использования обратных вызовов, характерных для решателя, в GLPK.

using JuMP, GLPK, Test

model = Model(GLPK.Optimizer)
@variable(model, 0 <= x <= 2.5, Int)
@variable(model, 0 <= y <= 2.5, Int)
@objective(model, Max, y)
reasons = UInt8[]
function my_callback_function(cb_data)
    reason = GLPK.glp_ios_reason(cb_data.tree)
    push!(reasons, reason)
    if reason != GLPK.GLP_IROWGEN
        return
    end
    x_val = callback_value(cb_data, x)
    y_val = callback_value(cb_data, y)
    if y_val - x_val > 1 + 1e-6
        con = @build_constraint(y - x <= 1)
        MOI.submit(model, MOI.LazyConstraint(cb_data), con)
    elseif y_val + x_val > 3 + 1e-6
        con = @build_constraint(y - x <= 1)
        MOI.submit(model, MOI.LazyConstraint(cb_data), con)
    end
end
MOI.set(model, GLPK.CallbackFunction(), my_callback_function)
optimize!(model)
@test termination_status(model) == MOI.OPTIMAL
@test primal_status(model) == MOI.FEASIBLE_POINT
@test value(x) == 1
@test value(y) == 2
@show reasons

API для C

Доступ к API для C можно получить с помощью функций GLPK.glp_XXX, имена и аргументы которых идентичны API для C. Для вдохновения просмотрите папку /tests.

Потокобезопасность

GLPK не является потокобезопасным и не должен использоваться с многопоточностью.