Reputation: 21
I'm trying to implement a procedure (described in Sec. 5.1 of this paper).
Given a computer network modeled as a directed acyclic graph (DAG), I have some initial nodes (let's say starting points of an attacker) and a node called goal node (finishing point, attackers objective) for which I compute a probability to be compromised (by the attacker).
Once I have this probability, given an admissible set of goal's node descendants, I want to find optimal placement for one (or more) improvement-node in this path such that the goal node probability is lower (actually minimized).
All this is described as a minimax problem where the result of the inner maximization problem (the goal's probability to be attacked) is then used in the outer minimization problem. The latter is a combinatorial problem.
The whole procedure is implemented in Java, but the part of interest here is done in MathProg using the GLPK solver.
The source code of the first part is provided. The second part is described, but there is no available code. Thus my question becomes:
Can you help me to model in MathProg (or JAVA API to GLPK) the combinatorial minimization problem?
Refer to the [Minimization part] of this question for a thoughtful explanation and my attempt.
I have zero experience with MathProg and not much with optimization algorithms. I'd be glad to hear hints on how to set-up this model for a solver, preferably with MathProg for GLPK and/or the Java (not exclusively) that integrates the two parts.
In this part, I obtain the maximized goal node probability as the result of a maximization problem solved using SLP with GLPK (several iterations of this problem till a stationary point, this is done in Java).
Problem description:
max_prob
The f(T,x,y) constraint is of some sort that yields the constraints you see in the example (we can omit its desc. for now).
Here is an example in MathProg of the LP modeling for this problem for a graph of 10 nodes:
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)
The minimization consists in minimizing the goal's node compromise probability (the same that was maximized within the previous part) by finding a combination of one or more "improvement nodes" that lay in the descendants set of the goal node.
Let Na be the number of improvable nodes (j_1 < j_2 < ... < j_Na, the nodes). Define 0-1 variables t_j_i for i=1,..,Na with T = (t_j_1, ..., t_j_Na)
A single improvement corresponds to the constraint t_j1 + t_j2 + ...+ t_j_Na = 1.
The problem is then:
min_prob
where x_g is the solution to
where f(x,y) comprises T. If the t_j-th corresponding element of T is = 1 then the j-th node in the descendants set of the goal node is "improved" such that the goal's node probability of compromise is lowered.
Relaxing from cond generalizes for multiple improvements.
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;
Output:
ERROR:
test.m:42: no value for t8
MathProg model processing error
Upvotes: 1
Views: 132