Общая картина
Я пытаюсь реализовать процедуру (описанную в разделе 5.1 этой статьи ).
Учитывая компьютерную сеть, смоделированную как ориентированный ациклический граф (DAG), у меня есть несколько начальных узлов (скажем, начальных точек злоумышленника) и узел, называемый целевым узлом (конечная точка, цель злоумышленников), для которого я вычисляю вероятность взлома (атакующим).* Когда у меня есть такая вероятность, учитывая допустимый набор потомков узла цели, я хочу найти оптимальное размещение для одного (или более) узла улучшения на этом пути так, чтобы вероятность узла цели была ниже (фактически минимизированной).
Все это описывается как минимаксная задача, в которой результат задачи внутренней максимизации (вероятность цели будет атакован) затем используется в задаче внешней минимизации.Последняя проблема является комбинаторной.
Вся процедура реализована на Java, но интересующая ее часть здесь выполняется в MathProg с использованием решателя GLPK.
Предоставляется исходный код первой части.Вторая часть описана, но нет доступного кода.Таким образом, мой вопрос звучит так:
Можете ли вы помочь мне моделировать в MathProg (или JAVA API для GLPK) проблему комбинаторной минимизации?
См. [Часть минимизации] этого вопроса для вдумчивого объяснения и моей попытки.
У меня нулевой опыт работы с MathProg и не так много с алгоритмами оптимизации.Я был бы рад услышать подсказки о том, как настроить эту модель для решателя, предпочтительно с MathProg для GLPK и / или Java (не только), который объединяет две части.
Максимизация
В этой части я получаю максимальную вероятность целевого узла в результате задачи максимизации, решаемой с помощью SLP с GLPK (несколько итераций этой задачи до стационарной точки, это делается в Java).
Описание проблемы:
max_prob
Ограничение f (T, x, y) является своего рода, которое дает ограничения, которые вы видите в примере (мы можем опуститьего описание на данный момент).
Вот пример в MathProg моделирования LP для этой задачи для графика из 10 узлов:
var x1<=1;
var x2<=1;
var x3<=1;
var x4<=1;
var x7<=1;
var x8<=1;
var x9<=1;
var x10<=1;
maximize z: x1;
s.t. c1: x1 = x2;
s.t. l1: x1>=0.0001;
s.t. c2: x2=1*x3;
s.t. l2: x2>=0.0001;
s.t. c3: x3 = x4;
s.t. l3: x3>=0.0001;
s.t. c4: x4=0.68*x7;
s.t. l4: x4>=0.0001;
s.t. c7: x7 = x8;
s.t. l7: x7>=0.0001;
s.t. c8: x8=0.64*x9;
s.t. l8: x8>=0.0001;
s.t. c9: x9 = x10;
s.t. l9: x9>=0.0001;
s.t. c10: x10=0.68;
s.t. l10: x10>=0.0001;
Result:
Objective: z = 0.295936 (MAXimum)
Часть минимизации
Минимизация состоит в минимизации вероятности компрометации узла цели (той же самой, которая была максимизирована в предыдущей части) путем нахождения комбинации одного или нескольких «узлов улучшения», которые лежат в наборе потомковцелевого узла.
Пусть Na будет числом улучшаемых узлов (j_1 Единственное улучшение соответствует ограничению t_j1 + t_j2 + ... + t_j_Na = 1.
Проблема тогда:
min_prob
, где x_g - решение для
max_prb_2
, где f (x, y) содержит T. Если t_j-й соответствующий элемент T равен = 1, то j-й узел в наборе потомков целевого узла «улучшается» так, чтоВероятность компромисса узла цели снижена.
Ослабление от cond обобщает для нескольких улучшений.
Моя попытка
var x1<=1;
var x2<=1;
var x3<=1;
var x4<=1;
var x7<=1;
var x8<=1;
var x9<=1;
var x10<=1;
var t8 binary;
maximize z: x1;
s.t. c1: x1 = x2;
s.t. l1: x1>=0.0001;
s.t. c2: x2=1*x3;
s.t. l2: x2>=0.0001;
s.t. c3: x3 = x4;
s.t. l3: x3>=0.0001;
s.t. c4: x4=0.68*x7;
s.t. l4: x4>=0.0001;
s.t. c7: x7 = x8;
s.t. l7: x7>=0.0001;
s.t. c8: x8=0.64*x9;
s.t. l8: x8>=0.0001;
s.t. c9: x9 = x10;
s.t. l9: x9>=0.0001;
s.t. c10: x10=0.68;
s.t. l10: x10>=0.0001;
#x8 is an improvable node
#t8 it the t_j_8 element of T
param t8 binary= 1;
#p8 is a given parameter (it reduces the x1 prob. in the end)
param p8 = 0.3;
minimize z2: x1;
#this is the f(T,x,y) constraint: if t8 = 0 the coeff of x8 is reduced by p8, if t8 = 0, nothig happens
s.t. ct8: x8 = (p8**t8)*x8;
#s.t. lt8: x8>=0.0001;
solve;
end;
Вывод:
ОШИБКА:
test.m: 42: нет значения для t8
Ошибка обработки модели MathProg