1
$\begingroup$

I'm working on an optimization problem which is kind of finding the minimum dominating set (MDS) or the minimum vertex set (MVS) in an undirected graph. given the MILP formulation for both problems, I was wondering is there a way to state a constraint to find the (minimum) of (the minimum set). In other words, given the set C is the solution of MDS with some edges, I am looking for a constraint that relates this set C using a new decision variable/s to find a new set P which is the MDS of the set C. The problem is like finding the root (or multiple roots) of an undirected graph in two linked stages. I can imagine that the problem will go like this, given:

   x_v is the decision variable for the node to be selected in C (first level or child)
   y_v is the decision variable for the node to be selected in P (second level or parent (root))
   z(u,v) is the decision variable about the edges of the graph resulting from solving the first level

hence, the constraint that relates those variables are:

     y_v <- x_v # to ensure that the parent node will be selected from the set of child nodes
     y_v <- z(u,v) # to ensure that the parent node will be selected from the resulting edges

I can not figure out another constraint that forces the solver to select the set from the resulting set. As an example, consider the set C is {1,2,5,7}, Is there a way to promote node 7 as a root if I have the edges [(7,5),(7,2),(7,1)]. Please be noted that I meant by the root here is the node that at least connected to each child with one link.

Any guidance will be very appreciated?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.