Skip to main content

Minimum Spanning Tree with a Maximum Degree Constraint

We show how to solve the minimum spanning tree problem with a maximum degree constraint using JijZept and JijModeling. This problem is also mentioned in 8.1. Minimal Spanning Tree with a Maximal Degree Constraint on Lucas, 2014, "Ising formulations of many NP problems".

What is Minimum Spanning Tree with a Maximum Degree Constraint?

The minimum spanning tree problem is defined as follows. Given an undirected graph G=(V,E)G = (V, E), where each edge (uv)E(uv) \in E is associated with a cost cuvc_{uv}, construct the spanning tree (a tree that contains all vertices) TGT \subseteq G such that the cost of TT

c(T)=(uv)ETcuvc(T) = \sum_{(uv) \in E_T} c_{uv}

is minimized if such a tree exists. One can add a degree constraint that forces each degree of vertex in TT to be Δ\leq \Delta. In other words, given a graph, the minimum spanning tree is the tree that connects all the nodes with the minimum total edge weight, and the maximum degree constraint ensures that no vertex in the tree has a degree that is greater than specified value.

Example

Let us consider a simple graph shown below. Suppose we want to find the minimum spanning tree of the left graph subject to a maximum degree constraint 3. The solution to this problem is given in the right; the edges in this tree have a total weight 8, which is the minimum possible, and the maximum degree constraint is obviously satisfied.

Mathematical model

We first place a binary variable xuvx_{uv} on each edge to show whether or not the edge is included in TT; i.e. xuv=1x_{uv} = 1 means that the edge e=(uv)e = (uv) is included in our minimum spanning tree TT.

Constraint1: Each vertex can have at most Δ\Delta edges

The degree of any vertex in the graph cannot exceed Δ\Delta. Note that we have also a lower bound condition for the degree of each vertex, because, in a spanning tree, each vertex must have at least one edge.

1(uv),(vu)ExuvΔuV.\quad 1 \leq \sum_{(uv),(vu) \in E} x_{uv} \leq \Delta \quad \forall u \in V.

Note that the notation in the summation is meant to include both xuvx_{uv} and xvux_{vu}.

Constraint2: The tree is spanning

We promise that the selected edges form a tree with all vertices included; if the number of edges in TT is less than V1|V|-1, TT does not include all vertices, and if the number of edges in TT is greater than V1|V|-1, TT is not a tree (there are loops in such cases).

(uv)Exuv=V1.\quad \sum_{(uv) \in E} x_{uv} = |V|-1.

Constraint3: Cut constraint

This constraint ensures that the solution is connected and acyclic.

(uv)E(S)xuvS1SG,\quad \sum_{(uv) \in E(S)} x_{uv} \leq |S| - 1 \quad \forall S \subset G,

where SS represents a subgraph of the given GG, and where E(S)E(S) represents the set of edges that are contained in SS.

Objective function

We set the objective function so that the total weight of TT is minimized.

minuvEcuvxuv.\quad \min \sum_{uv \in E} c_{uv}x_{uv}.

Modeling by JijModeling

Next, we show how to implement above equations using JijModeling. We first define the variables in the mathematical model described above.

import jijmodeling as jm

#define variables
V = jm.Placeholder('V') # number of vertices
E = jm.Placeholder('E', ndim=2) # set of edges
num_E = E.shape[0]
C = jm.Placeholder('C', ndim=2) # cost between each vertex
D = jm.Placeholder('D') # number of degrees
S = jm.Placeholder('S', ndim=3) # list of set of subgraph edges
num_S = S.shape[0]
S_nodes = jm.Placeholder('S_nodes', ndim=1) # list of number of subgraphs vertices

x = jm.BinaryVar('x', shape=(num_E,))

v = jm.Element('v', V) # subscripts for verteces
e = jm.Element('e', num_E) # subscripts for edges
i_s = jm.Element('i_s', num_S)
e_s = jm.Element('e_s', S[i_s].shape[0]) # subscripts of edges in S

The constraints and the objective function are written as:

problem = jm.Problem("minimum spanning tree with a maximum degree constraint")
problem += jm.Constraint('const1-1', jm.sum((e, (E[e][0]==v)|(E[e][1]==v)), x[e]) >= 1, forall=v)
problem += jm.Constraint('const1-2', jm.sum((e, (E[e][0]==v)|(E[e][1]==v)), x[e]) <= D, forall=v)
problem += jm.Constraint('const2', x[:].sum() == V-1)
problem += jm.Constraint('const3',jm.sum(e_s, x[e_s]) <= S_nodes[i_s] - 1, forall = i_s)
problem += jm.sum(e, C[E[e][0]][E[e][1]]*x[e])

On Jupyter Notebook, one can check the problem statement in a human-readable way by hitting

problem 

Problem:minimum spanning tree with a maximum degree constraintmine=0len(E,0)1CEe,0,Ee,1xes.t.const1-1e=0Ee,0=vEe,1=vlen(E,0)1xe1v{0,,V1}const1-2e=0Ee,0=vEe,1=vlen(E,0)1xeDv{0,,V1}const20=0len(E,0)1x0=V1const3es=0len(Sis,0)1xesSnodesis1is{0,,len(S,0)1}wherex1-dim binary variable\begin{array}{cccc}\text{Problem:} & \text{minimum spanning tree with a maximum degree constraint} & & \\& & \min \quad \displaystyle \sum_{e = 0}^{\mathrm{len}\left(E, 0\right) - 1} C_{E_{e, 0}, E_{e, 1}} \cdot x_{e} & \\\text{{s.t.}} & & & \\ & \text{const1-1} & \displaystyle \sum_{\substack{e = 0\\E_{e, 0} = v \lor E_{e, 1} = v}}^{\mathrm{len}\left(E, 0\right) - 1} x_{e} \geq 1 & \forall v \in \left\{0,\ldots,V - 1\right\} \\ & \text{const1-2} & \displaystyle \sum_{\substack{e = 0\\E_{e, 0} = v \lor E_{e, 1} = v}}^{\mathrm{len}\left(E, 0\right) - 1} x_{e} \leq D & \forall v \in \left\{0,\ldots,V - 1\right\} \\ & \text{const2} & \displaystyle \sum_{\ast_{0} = 0}^{\mathrm{len}\left(E, 0\right) - 1} x_{\ast_{0}} = V - 1 & \\ & \text{const3} & \displaystyle \sum_{e_s = 0}^{\mathrm{len}\left(S_{i_s}, 0\right) - 1} x_{e_s} \leq S_nodes_{i_s} - 1 & \forall i_s \in \left\{0,\ldots,\mathrm{len}\left(S, 0\right) - 1\right\} \\\text{{where}} & & & \\& x & 1\text{-dim binary variable}\\\end{array}

Prepare an instance

We prepare a graph using NetworkX. As an example, we create a random complete graph (a graph where all vertices are connected to each other).

import itertools
import networkx as nx
import numpy as np

np.random.seed(seed=0)

# set the number of vertices
inst_V = 5
# set the number of degree
inst_D = 2

# set the probability of rewiring edges
p_rewire = 0.2
# set the number of nearest neighbors
k_neighbors = 4
# create a connected graph
inst_G = nx.connected_watts_strogatz_graph(inst_V, k_neighbors, p_rewire)
# add random costs to the edges
for u, v in inst_G.edges():
inst_G[u][v]['weight'] = np.random.randint(1, 10)

# create a 2D array for the costs
inst_C = np.zeros((inst_V, inst_V))
for u, v in inst_G.edges():
inst_C[u][v] = inst_G[u][v]['weight']
inst_C[v][u] = inst_G[u][v]['weight']
# set diagonal elements to infinity
np.fill_diagonal(inst_C, np.inf)

# get information of edges
inst_E = [list(edge) for edge in inst_G.edges]

# get subgraphs and their edges
sub_nodes = []
sub_edges = []
# get connected subgraphs that have at least 2 nodes and have less nodes than the original graph
for num_nodes in range(2, inst_G.number_of_nodes()):
for comb in (inst_G.subgraph(selected_nodes) for selected_nodes in itertools.combinations(inst_G, num_nodes)):
if nx.is_connected(comb):
sub_edges.append(comb.edges)
sub_nodes.append(comb.nodes)
inst_S = [list(edgeview) for edgeview in sub_edges]
inst_S = [[list(t) for t in inner_list] for inner_list in inst_S] # convert tuples into lists
# get the number of vertices in each subgraph
inst_S_nodes = [len(x) for x in sub_nodes]

instance_data = {'V': inst_V, 'D': inst_D, 'E': inst_E, 'C': inst_C, 'S': inst_S, 'S_nodes': inst_S_nodes}

This graph is shown below.

import matplotlib.pyplot as plt

pos = nx.spring_layout(inst_G)
nx.draw_networkx(inst_G, pos, with_labels=True)
edge_labels = nx.get_edge_attributes(inst_G, 'weight')
nx.draw_networkx_edge_labels(inst_G, pos, edge_labels=edge_labels, font_color='red')

plt.show()

png

Solve by JijZept's SA

We solve this problem using JijSASampler. We also turn on a parameter search function by setting search=True.

import jijzept as jz

# set sampler
sampler = jz.JijSASampler(config="../../../config.toml")
# solve problem
response = sampler.sample_model(problem, instance_data, multipliers={"const1-1": 0.5, "const1-2": 0.5, "const2": 0.5, "const3": 0.5}, search=True, num_reads=100)

Visualize the solution

The optimized solution can be seen as below.

# get sampleset
sampleset = response.get_sampleset()
# extract feasible samples
feasible_samples = sampleset.feasibles()
# get the values of feasible objectives
feasible_objectives = [sample.eval.objective for sample in feasible_samples]
if len(feasible_objectives) == 0:
print("No feasible samples found ...")
else:
# get the index of the lowest feasible objective
lowest_index = np.argmin(feasible_objectives)
# get the lowest feasible solution
lowest_solution = feasible_samples[lowest_index].var_values["x"].values
# get the indices of x == 1
x_indices = [key[0] for key in lowest_solution.keys()]
# set edge color list (x==1: black, x==0: white)
inst_E = np.array(inst_E)
mask = inst_E[:, 0] > inst_E[:, 1]
inst_E[mask] = inst_E[mask][: , : :-1]
edge_colors = np.where(np.isin(np.arange(len(inst_E)), x_indices), 'black', 'white').tolist()
# draw figure
plt.subplot(121)
plt.axis('off')
nx.draw(inst_G, pos, with_labels=True, font_weight='bold')
nx.draw_networkx_edge_labels(inst_G, pos, edge_labels=edge_labels, font_color='red')
plt.subplot(122)
plt.axis('off')
inst_H = inst_G.copy()
for i in range(len(inst_H.edges)):
if edge_colors[i] == 'white':
inst_H.remove_edge(*list(inst_G.edges)[i])
nx.draw(inst_H, pos, with_labels=True, font_weight='bold')
nx.draw_networkx_edge_labels(inst_H, pos, edge_labels=nx.get_edge_attributes(inst_H, 'weight'), font_color='red')

png

As expected, we have obtained the minimum spanning tree that satisfies the maximum degree constraint.

The Steiner tree problem, a similar problem to the one described in this page, would be an advanced practice. The problem statement is as follows. Given costs cuvc_{uv}, find the minimum spanning tree for a subset of the vertices UVU \subset V, where the usage of nodes that are not contained in UU is one's option. To solve this problem, one can use the same Hamiltonian as for the minimum spanning tree problem except for additional binary variables yvy_v for vUv \notin U, which show whether or not a node vv is included in the resulting tree.