4
$\begingroup$

I want to solve the Group Closeness Centrality problem where the input is a graph $G=(V,E)$ and integer $k$ and we want to find a vertex set $S$ of size $k$ minimizing the total distance of the vertices in $V\setminus S$ to $S$. Here, the distance of a vertex $v$ to $S$ is defined as the length of a shortest path starting in $v$ and ending at some vertex of $S$.

I am using an ILP formulation with binary variables $x_{v,d}$ where $x_{v,d}=1$ if vertex $v$ has distance $d$ to $S$ and $d\in \{1,\ldots, diam(G)\}$. Here, $diam(G)$ is the diameter of $G$, the length of longest shortest path in $G$.

The objective function is

$$\sum_{v\in V}\;\sum_{d\in \{1,\ldots,diam(G)\}} d\cdot x_{v,d}.$$ The constraints are

  1. $\sum_{v\in V} x_{v,0} = k$,
  2. $\sum_{d\in \{0,\ldots,diam(G)\}} x_{v,d}=1\, \forall {v\in V}$,
  3. $x_{v,d}\le \sum_{u\in N_d(v)} x_{u,0}\, \forall {v\in V}\, \forall {d\in \{1,\ldots,diam(G)-1\}}$.

The first constraint ensures that we select $k$ vertices, the second that the distance to $S$ is well-defined. The third constraint ensures that for $v$ to have distance $d$ to $S$, we must select a vertex in the $d$-neighborhood of $v$.

I am looking at improved formulations and I want to use an approach where for every vertex we do not consider variables $x_{v,d}$ for all $d\in \{0,\ldots, diam(G)\}$ but only for values $d\in \{0,\ldots, d(v)\}$, for some value $d(v)$.

Initially, $d(v)=2$ for all $v\in V$. Now this means that if we select a vertex, then it contributes 0 to the objective, if we select a neighbor, then it contributes 1, and otherwise, we get a contribution of 2. Now if we find a solution where every vertex contributes 1 (i.e. if $G$ has a dominating set of size $k$), then we are done. Otherwise, we find a vertex $v$ that contributes $2$ and increase the $d(v)$-value for this vertex. More precisely, we add a further variable $x_{v,d(v)}$ and the corresponding constraint, and afterwards increase $d(v)$ by one.

After this long explanation, here are my questions:

  1. Is it appropriate to call this approach column generation or does it have another name?
  2. When I implement this (hopefully) improved formulation in CPLEX, is it necessary to solve the main problem from scratch after adding a variable, or is there some way of adding the variables in a lazy manner?
$\endgroup$
5
  • $\begingroup$ I'm not sure your formulation is correct. Let $v\in S$ for a solution $S$. Constraint (2) forces $x_{v,\hat{d}}=1$ for some $\hat{d}\ge 1,$ and the objective function charges a penalty $\hat{d}$ for $v$, even though the objective function allegedly is looking only at distances from $V\backslash S$ to $S.$ Also, I think there is a typo in (3): $x_{0,d}$ should be $x_{u,0}.$ $\endgroup$
    – prubin
    Jul 12, 2022 at 15:37
  • $\begingroup$ @prubin There is a typo in constraint (2): the sum should start at $d=0$, and this correction allows $d=0$ for $v\in S$. $\endgroup$
    – RobPratt
    Jul 12, 2022 at 16:19
  • $\begingroup$ @RobPratt My thoughts exactly. $\endgroup$
    – prubin
    Jul 12, 2022 at 16:23
  • $\begingroup$ Yes this is a typo, thanks for pointing this out. $\endgroup$ Jul 12, 2022 at 16:33
  • $\begingroup$ Is there some intuition for why increasing $d(v)$ for a node that uses $d=2$ in the currently optimal solution is expected to yield an improvement? Changing $x_{v,2}$ from $1$ to $0$ and then taking $x_{v,3}=1$ would make the objective value worse by one unit. Traditional column generation would instead use reduced costs to recommend new columns. $\endgroup$
    – RobPratt
    Jul 12, 2022 at 17:31

3 Answers 3

7
$\begingroup$

I would not call the approach column generation. That term is usually applied to methods where columns are constructed using information from the solution of a previous version of the problem. What you are doing is iterating over progressively larger values of a parameter (the maximum value considered for $d$). So I would characterize it as an "iterative" approach.

As far as "hot-starting" CPLEX, you can try to hand CPLEX a feasible starting solution by modifying the solution to the previous problem manually. So, for instance, if you have a vertex $v$ that contributes value 2 (the max allowed) and you increase the max to 3, you can construct a solution to the new problem by copying the solution to the previous problem and then setting $x_{v,2}$ and $x_{v,3}$ appropriately. All the APIs (as far as I know) have methods to set a candidate starting solution.

$\endgroup$
1
  • $\begingroup$ Thanks for this very helpful answer. $\endgroup$ Jul 12, 2022 at 16:37
5
$\begingroup$

Here is an alternative model that might be easier to solve (or not -- see the update at the end). Let $N(i)\subseteq V$ be the set of neighbors of $i\in V$ (nodes connected to $i$ by an edge). We introduce one binary variable $x_i$ for each node $i$ (1 if the node goes in $S$, 0 if not) and two nonnegative continuous variables $y_{i,j}$ and $y_{j,i}$ for each edge $(i,j)\in E,$ representing flows. The objective is $$\min \sum_{(i,j)\in E} \left( y_{i,j} + y_{j,i} \right),$$ which charges each unit of flow 1 for each edge it crosses. The constraints are $$\sum_{i\in V} x_i = k$$ (to get the desired size for $S$) and $$\sum_{j \in N(i)} \left( y_{i,j} - y_{j,i} \right) \ge 1 - M\cdot x_i \quad \forall i\in V.$$ The latter constraints say that the flow out of a node $i$ must be at least one greater than the flow in unless $i\in S.$ For a sufficiently large value of $M$ (I think $M = \vert V \vert - k$ will suffice), the constraint allows a node $i\in S$ to soak up any plausible amount of incoming flow without spitting out anything.

Given a solution for $x,$ the flows that minimize total arc "costs" will automatically have nodes in $S$ soak up all incoming flow and nodes not in $S$ contribute one unit of flow. The unit of flow coming out of a node $i \notin S$ will automatically take the shortest path to a node in $S$ since to do otherwise would inflate the objective value.

The model contains $\vert V \vert$ binary variables and $2\cdot \vert E \vert$ continuous variables.

Update: I tried both this model and that of question's author on a few sparse graphs, using CPLEX as the solver. The author's model beat mine handily every time.

$\endgroup$
6
  • $\begingroup$ It might also be worth replacing the third set of original constraints with $x_{i,d} \le \sum_{j \in N(i)} x_{j,d-1}$. $\endgroup$
    – RobPratt
    Jul 13, 2022 at 19:40
  • 1
    $\begingroup$ @RobPratt That seems to be faster than the original model in some cases and slower in others. $\endgroup$
    – prubin
    Jul 13, 2022 at 22:00
  • $\begingroup$ Thanks for checking. $\endgroup$
    – RobPratt
    Jul 13, 2022 at 22:08
  • $\begingroup$ I should add that I ran only a few graphs, and not to optimality (maybe a two minute time limit on each), so I can't say anything definitive. $\endgroup$
    – prubin
    Jul 13, 2022 at 22:16
  • $\begingroup$ I also tried the original model with integrality relaxed for all but the zero distance variables (i.e., $x_{v,0}\in \lbrace 0, 1 \rbrace$ but $x_{v,d}\in [0,1]$ for $d > 0.$ This might or might not be equivalent to assigning branching priority to the zero distance variables. In any case, results were again mixed. $\endgroup$
    – prubin
    Jul 13, 2022 at 22:18
3
$\begingroup$

This formulation may be helpful.

Let $d_{ij}$ as the value of the shortest path between vertices $i$ and $j$. Define

$x_j\in \{0,1\}$; where $x_j=1$ if the vertex $j$ is selected in $S$.

$y_{ij}\in \{0,1\}$; where $y_{ij}=1$ if the vertex $i$ is assigned to the selected vertex $j\in S$; i.e. $j\in S$ and minimum distance from $i$ to $S$ is $d_{ij}$.

Now, solve an ILP for minimization of $\sum_{i,j} d_{ij}y_{ij}$ subject to the constraints $\sum_j x_j=k$ and $\sum_j y_{ij}=1\ \ \forall i$ and $y_{ij}\le x_j \ \ \forall i,j$

$\endgroup$
8
  • $\begingroup$ Welcome and +1. This is a $k$-median (also known as $p$-median) formulation. $\endgroup$
    – RobPratt
    Jul 12, 2022 at 13:10
  • $\begingroup$ Thanks for the suggestion. Actually, I don't want to use this formulation as it needs a quadratic number of variables and we already know that it is slower than the simple formulation described above. $\endgroup$ Jul 12, 2022 at 13:13
  • $\begingroup$ I should add that the simple formulation in the question has also a quadratic number of variables in the worst case but for real-world social networks (which we are interested in), diam(G) is essentially a constant, thus we have essentially a linear number of variables. $\endgroup$ Jul 12, 2022 at 13:29
  • $\begingroup$ But I think this formulation is more useful. Please notify me if my idea is wrong. If yoy replace the last constraints by $\sum_i y_{ij}\le x_j\ \ \forall j$ then coefficient matrix A is totally unimodular and solving the LP relaxation produced the ILP solution. $\endgroup$ Jul 12, 2022 at 15:31
  • 2
    $\begingroup$ @MajidZohrehbandian Imposing $\sum_i y_{ij} \le x_j$ would be too strong, forcing at most one $i$ per $j$. $\endgroup$
    – RobPratt
    Jul 12, 2022 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.