Джулия Джамп: Получение всех возможных решений для мип

Я хотел бы иметь вместо только вектора оптимального решения mip все допустимые (субоптимальные) векторы.
Я нашел здесь несколько старых вопросов, но я не уверен, как они работают.

Прежде всего, есть ли какой-нибудь новый библиотечный инструмент/способ сделать это автоматически?
Я пробовал это, но ничего не сделал:

if termination_status(m) == MOI.FEASIBLE_POINT
    println(x)
end
optimize!(m);

Если нет, то как проще всего?
Я подумал о том, чтобы сканировать оптимальное решение, пока не найду первую ненулевую переменную решения, затем ограничить эту переменную равной нулю и снова решить модель.

for i in 1:active_variables
    if value.(z[i])==1
        @constraint(m, x[i] == 0)
        break
    end
end

optimize!(m);

Но я вижу эту проблему с этим методом**:

  1. Если я ограничу x[i] равным нулю, на следующем шаге я, возможно, захочу снова отказаться от этого ограничения? Это сводится к тому, могут ли существовать два (или более) различных решения, в которых x[i]==1

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

Przemyslaw Szufel 02.12.2022 20:39

@PrzemyslawSzufel Думаю, я хочу оба, но второй более общий

tonythestark 02.12.2022 20:40

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

Dan Getz 02.12.2022 20:58

@DanGetz как-то игнорируется.. Я написал этот код и ничего не печатает.. Я добавил это после первого звонка optimize();

tonythestark 02.12.2022 21:22
Загадки Python - Генерация простых чисел!
Загадки Python - Генерация простых чисел!
Обычно существует несколько способов решения задач даже пограничной сложности. Как же определить оптимальное и эффективное решение?
5
4
167
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

JuMP поддерживает возврат нескольких решений.

Документация: https://jump.dev/JuMP.jl/stable/manual/solutions/#Multiple-solutions

Рабочий процесс примерно такой:

using JuMP
model = Model()
@variable(model, x[1:10] >= 0)
# ... other constraints ...
optimize!(model)

if termination_status(model) != OPTIMAL
    error("The model was not solved correctly.")
end

an_optimal_solution = value.(x; result = 1)
optimal_objective = objective_value(model; result = 1)
for i in 2:result_count(model)
    @assert has_values(model; result = i)
    println("Solution $(i) = ", value.(x; result = i))
    obj = objective_value(model; result = i)
    println("Objective $(i) = ", obj)
    if isapprox(obj, optimal_objective; atol = 1e-8)
        print("Solution $(i) is also optimal!")
    end
end

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

См. этот пост в блоге: https://jump.dev/tutorials/2021/11/02/tutorial-multi-jdf/

Я пробовал именно это, но кажется, что я никогда не попадал в цикл for (я на самом деле напечатал result_count, и это было 1), так что, может быть, я выбрал неправильный решатель?

tonythestark 03.12.2022 11:00

Вам нужно будет выбрать Gurobi или CPLEX и соответствующим образом настроить их параметры (см. сообщение в блоге). Большинство решателей не поддерживают возврат нескольких решений.

Oscar Dowson 04.12.2022 20:49
Ответ принят как подходящий

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

Во-первых, давайте получим пакеты и определим пример проблемы:

using Random, JuMP, HiGHS, MathOptInterface

function example_knapsack()
    profit = [5, 3, 2, 7, 4]
    weight = [2, 8, 4, 2, 5]
    capacity = 10
    minprofit = 10
    model = Model(HiGHS.Optimizer)
    set_silent(model)
    @variable(model, x[1:5], Bin)
    @objective(model, FEASIBILITY_SENSE, 0)
    @constraint(model, weight' * x <= capacity)
    @constraint(model, profit' * x >= minprofit)
    return model
end

(это задача о рюкзаке из документации JuMP).

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

function findallsol(model, x)
    perm = shuffle(1:length(x))
    res = Vector{Float64}[]
    _findallsol!(res, model, x, perm, 0)
    return res
end

function _findallsol!(res, model, x, perm, depth)
    n = length(x)
    depth > n && return
    optimize!(model)
    if termination_status(model) == MathOptInterface.OPTIMAL
        if depth == n
            push!(res, value.(x))
            return
        else
            idx = perm[depth+1]
            v = value(x[idx])
            newcon = @constraint(model, x[idx] == v)
            _findallsol!(res, model, x, perm, depth + 1)
            delete(model, newcon)
            newcon = @constraint(model, x[idx] == 1 - v)
            _findallsol!(res, model, x, perm, depth + 1)
            delete(model, newcon)
        end
    end
    return
end

Теперь мы можем:

julia> m = example_knapsack()
A JuMP Model
Maximization problem with:
Variables: 5
...
Names registered in the model: x

julia> res = findallsol(m, m.obj_dict[:x])
5-element Vector{Vector{Float64}}:
 [1.0, 0.0, 0.0, 1.0, 1.0]
 [0.0, 0.0, 0.0, 1.0, 1.0]
 [1.0, 0.0, 1.0, 1.0, 0.0]
 [1.0, 0.0, 0.0, 1.0, 0.0]
 [0.0, 1.0, 0.0, 1.0, 0.0]

И получаем вектор со всеми решениями.

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

P.S. Это не оптимальный метод. Эта проблема хорошо изучена. Возможные термины для поиска: «подсчет моделей» (особенно в логической области).

(ОБНОВЛЕНИЕ: цель изменена на использование FEASIBLE)

Я отмечаю это как наиболее полезное, так как мне было легко устанавливать максимумы, в то время как у меня были проблемы с cplex. Вместо всех оптимальных решений я хочу все возможные. Так что, может быть, мне нужно изменить ``` iftermination_status(model) == MathOptInterface.OPTIMAL``` на что-то другое?

tonythestark 04.12.2022 16:18

@tonythestark Вы правы, целевая функция не нужна, и JuMP позволяет установить цель sense на FEASIBILITY_SENSE для достижения этой цели. [Обновление ответа, чтобы включить его]

Dan Getz 04.12.2022 18:10

было бы очень полезно, если бы вы показали мне, как кодировать это

tonythestark 07.12.2022 12:32

@tonythestark Конечно. Изменение ответа, чтобы отразить его (на самом деле сделал это раньше). Обратите внимание на определение @objective в задаче.

Dan Getz 07.12.2022 16:04

Другие вопросы по теме