Квадратично ограниченный MIQP с юлией и гуроби

Это попытка ответить на следующий вопрос: https://matheducators.stackexchange.com/questions/11757/small-data-sets-with-integral-sample-standard-devitions

Таким образом, цель следующего кода - найти примеры небольших наборов данных с целым стандартным отклонением. Это можно сформулировать как смешанную целочисленную квадратичную программу с квадратичными ограничениями, поэтому я пытаюсь использовать Гуробина из Джулии. Вот мой код:

using JuMP  
using Gurobi

m = Model(solver = GurobiSolver() )
@variable(m,  0<= x[1:20] <= 100,  Int)
@variable(m,  Gj,  Int)
@constraint(m,  Gj == sum(x[1:20])/20 )
@variable(m,  Var,  Int)
@constraint(m,  Var == sum( (x[1:20]-Gj).^2/19) )
@variable(m,  sd,  Int)
@constraint(m, sd * sd == Var)
### We need some restrictions to avoid all equal, < or zero,  solutions:
@constraint(m,  sd >= 5)
@objective(m, Min, sd)

print(m)

status = solve(m)

println("Objective value: ", getobjectivevalue(m) )

x = getvalue(x)

Выполнение этого приводит к:

ERROR: Gurobi.GurobiError(10021, "Quadratic equality constraints")
Stacktrace:
 [1] optimize(::Gurobi.Model) at /home/kjetil/.julia/v0.6/Gurobi/src/grb_solve.jl:7
 [2] optimize!(::Gurobi.GurobiMathProgModel) at /home/kjetil/.julia/v0.6/Gurobi/src/GurobiSolverInterface.jl:294
 [3] #solve#101(::Bool, ::Bool, ::Bool, ::Array{Any,1}, ::Function, ::JuMP.Model) at /home/kjetil/.julia/v0.6/JuMP/src/solvers.jl:173
 [4] solve(::JuMP.Model) at /home/kjetil/.julia/v0.6/JuMP/src/solvers.jl:148

Любые идеи?


julia gurobi julia-jump
person kjetil b halvorsen    schedule 04.03.2017    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

person Greg Glockner    schedule 06.03.2017
comment
Я не понимаю: здесь кажется, что это возможно , но я получаю ту же ошибку. Что я скучаю? См. Также The optional sense string defines the sense of the quadratic constrint. Allowed values are '<', '=' or '>'. If not present, the default sense is '<'. It is stored in model$quadcon[[i]]$sense. (Без аргумента смысла мой код проходит ...) - person Christoph; 20.03.2020

arrow_upward
0
arrow_downward

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

Начиная с Gurobi 9, вы можете решать невыпуклые билинейные задачи, в частности те, которые имеют ограничения квадратичного равенства. Вам просто нужно добавить правильный параметр. С Gurobi.jl, если m - ваша модель JuMP, вы можете сделать это:

set_optimizer_attribute(m, "NonConvex", 2)
person dourouc05    schedule 11.10.2020