Программирование в ограничениях
JuMP поддерживает ряд ограничений для программирования в ограничениях посредством соответствующих множеств в MathOptInterface. Для большинства ограничений есть встроенные переформулировки, которые преобразуют ограничение программирования в ограничениях в эквивалентное ограничение частично целочисленного программирования.
Из-за такой переформулировки все переменные должны быть целочисленными и, как правило, иметь конечные границы. Если переформулировка требует конечности, а переменная имеет неконечные границы, выдается ошибка.
В этом руководстве используются следующие пакеты.
using JuMP
import HiGHSAllDifferent
Множество MOI.AllDifferent гарантирует, что все элементы в списке принимают разные целочисленные значения.
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, 1 <= x[1:4] <= 4, Int)
@constraint(model, x in MOI.AllDifferent(4))
optimize!(model)
@assert is_solved_and_feasible(model)
value.(x)4-element Vector{Float64}:
1.0
4.0
3.0000000000000004
1.9999999999999996BinPacking
С помощью множества MOI.BinPacking можно разделить множество элементов на группы так, чтобы сумма их весов не превышала вместимости контейнера.
weights, capacity = Float64[1, 1, 2, 2, 3], 3.0;
number_of_bins = 3
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, 1 <= x[1:length(weights)] <= number_of_bins, Int)
@constraint(model, x in MOI.BinPacking(capacity, weights))
optimize!(model)
@assert is_solved_and_feasible(model)
value.(x)5-element Vector{Float64}:
2.0
1.0
2.0
1.0
3.0Здесь значение x[i] — это контейнер, в который был помещен элемент i.
Circuit
Множество MOI.Circuit служит для построения маршрута обхода списка из N переменных. Каждой из них присваивается целочисленное значение от 1 до N, указывающее следующий элемент в списке:
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, x[1:4], Int)
@constraint(model, x in MOI.Circuit(4))
optimize!(model)
@assert is_solved_and_feasible(model)Посмотрим, какой маршрут обхода был найден, начиная с узла номер 1:
y = round.(Int, value.(x))
tour = Int[1]
while length(tour) < length(y)
push!(tour, y[tour[end]])
end
tour4-element Vector{Int64}:
1
4
3
2CountAtLeast
Множество MOI.CountAtLeast гарантирует, что по крайней мере n элементов во множестве переменных принадлежат множеству значений.
Например, вот модель с тремя переменными, ограниченными значениями в диапазоне от 0 до 5:
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, 0 <= x[1:3] <= 5, Int)3-element Vector{VariableRef}:
x[1]
x[2]
x[3]Если нужно гарантировать, что хотя бы один элемент из каждого множества {x[1], x[2]} и {x[2], x[3]} принадлежит множеству {3}, следует создать список переменных, объединив множества:
variables = [x[1], x[2], x[2], x[3]]4-element Vector{VariableRef}:
x[1]
x[2]
x[2]
x[3]Затем необходимо получить список разделов, содержащий количество элементов в каждом множестве переменных:
partitions = [2, 2]2-element Vector{Int64}:
2
2Наконец, потребуется множество значений, которому должны принадлежать элементы:
values = Set([3])Set{Int64} with 1 element:
3И количество элементов, которые должны принадлежать множеству values:
n = 11Ограничение выглядит так:
@constraint(model, variables in MOI.CountAtLeast(n, partitions, values))[x[1], x[2], x[2], x[3]] ∈ MathOptInterface.CountAtLeast(1, [2, 2], Set([3]))Чтобы обеспечить уникальность решения, добавим ограничение, согласно которому x[2] должно быть <= 2. Это гарантирует, что единственным допустимым решением для x[1] и x[3] будет 3:
@constraint(model, x[2] <= 2)x[2] ≤ 2Проверим, найдено ли допустимое решение:
optimize!(model)
@assert is_solved_and_feasible(model)
value.(x)3-element Vector{Float64}:
3.0
0.0
3.0CountBelongs
Множество MOI.CountBelongs подсчитывает количество элементов во множестве переменных, принадлежащих множеству значений.
Например, подсчитать количество элементов во множестве из 4 переменных, принадлежащих множеству {2, 3}, можно так:
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, 0 <= x[i = 1:4] <= i, Int)
@variable(model, n, Int)
@objective(model, Max, sum(x))
set = Set([2, 3])
@constraint(model, [n; x] in MOI.CountBelongs(1 + length(x), set))
optimize!(model)
@assert is_solved_and_feasible(model)
value(n), value.(x)(2.0, [1.0, 2.0, 3.0, 4.0])CountDistinct
Множество MOI.CountDistinct подсчитывает количество уникальных элементов во множестве переменных.
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, 0 <= x[i = 1:4] <= i, Int)
@variable(model, n, Int)
@objective(model, Max, sum(x))
@constraint(model, [n; x] in MOI.CountDistinct(1 + length(x)))
optimize!(model)
@assert is_solved_and_feasible(model)
value(n), value.(x)(4.0, [1.0, 2.0, 3.0, 4.0])CountGreaterThan
Множество MOI.CountGreaterThan служит для наложения строгого ограничения на максимальное количество уникальных элементов во множестве переменных со значением, равным другой переменной.
Например, подсчитать количество n появлений y в векторе x можно так:
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, 0 <= x[i = 1:4] <= i, Int)
@variable(model, n, Int)
@variable(model, 3 <= y <= 4, Int)
@objective(model, Max, sum(x))
@constraint(model, [n; y; x] in MOI.CountGreaterThan(1 + 1 + length(x)))
optimize!(model)
@assert is_solved_and_feasible(model)
value(n), value(y), value.(x)(2.0, 3.0, [1.0, 2.0, 3.0, 4.0])Здесь n строго больше количества, и нет никаких ограничений на величину n. Например, n = 100 также является допустимым решением. Единственное ограничение заключается в том, что n не может быть равно количеству появлений y или меньше его.
Таблица
Множество MOI.Table служит для выбора одной строки из матрицы значений.
Например, если дана матрица:
table = Float64[1 1 0; 0 1 1; 1 0 1; 1 1 1]4×3 Matrix{Float64}:
1.0 1.0 0.0
0.0 1.0 1.0
1.0 0.0 1.0
1.0 1.0 1.0мы можем ограничить трехэлементный вектор x так, чтобы он был равен одной из строк в table:
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, x[i = 1:3], Int)
@constraint(model, x in MOI.Table(table))
optimize!(model)
@assert is_solved_and_feasible(model)
value.(x)3-element Vector{Float64}:
1.0
1.0
0.0