1

概貌

我正在尝试实施一个程序（在本文第 5.1 节中描述）。
给定一个建模为有向无环图 (DAG) 的计算机网络，我有一些初始节点（假设是攻击者的起点）和一个称为目标节点的节点（终点，攻击者目标），我为此计算被破坏的概率（由攻击者）。

一旦我有了这个概率，给定一组可接受的目标节点后代，我想在这条路径中找到一个（或多个）改进节点的最佳位置，以使目标节点概率更低（实际上是最小化）。

所有这些都被描述为一个极小极大问题，其中内部最大化问题的结果（目标被攻击的概率）然后用于外部最小化问题。后者是一个组合问题。
整个过程是用 Java 实现的，但这里感兴趣的部分是在 MathProg 中使用 GLPK 求解器完成的。
提供了第一部分的源代码。描述了第二部分，但没有可用的代码。因此我的问题变成了：

你能帮我在 MathProg（或 GLPK 的 JAVA API）中建模组合最小化问题吗？

请参阅此问题的[最小化部分]以获得深思熟虑的解释和我的尝试。

我对 MathProg 的经验为零，对优化算法的经验也不多。我很高兴听到有关如何为求解器设置此模型的提示，最好使用用于 GLPK 的 MathProg 和/或集成这两个部分的 Java（非排他性）。

最大化部分

在这一部分中，我获得了最大化的目标节点概率，这是使用 SLP 和 GLPK 解决的最大化问题的结果（这个问题的多次迭代直到一个静止点，这是在 Java 中完成的）。

问题描述：

max_prob

f(T,x,y) 约束是某种产生您在示例中看到的约束的类型（我们现在可以省略它的描述）。

下面是这个问题的 LP 建模的 MathProg 中的一个示例，用于 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 < j_2 < ... < j_Na，节点）。定义 0-1 个变量 t_j_i for i=1,..,Na with T = (t_j_1, ...,
t_j_Na
) :
min_prob

其中 x_g 是解决方案

max_prb_2

其中 f(x,y) 包含 T。如果 T 的第 t_j 个对应元素 = 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 模型处理错误
没有值

4

0 回答 0