Is this ILP formulation for Group Closeness Centrality a column generation approach?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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$