# Weighted Maximum Independent Set

Solving Weighted Maximum Independent Set using D-Wave BlackBox

Contents

Section 1

• 1.1 - Problem Definition
• 1.2 - Using D-Wave BlackBox to solve WMIS
• 1.5 - A function for computing WMIS
• Section 2

• 2.1 - Trying it out!
• Aim, audience and required background

This material was developed to help those interested in the physics of the D-Wave OneTM System to perform some simple experiments and explore some of the interesting science behind the processor technology. This tutorial series is designed to introduce you to quantum computer programming using a practical, hands-on approach.

All of the software necessary for developers to begin learning how to program D-Wave quantum computing systems can be downloaded from the DOWNLOAD DEVKITS page. As the developer portal is currently in BETA test stage, you will need to have a D-Wave developer account to download these packs. To follow this tutorial it may be helpful to have read two of the previous installments: Quantum Computing and Energy Programming Primer and Getting Started: Installing the D-Wave developer pack and an introductory 'hello multiverse' tutorial.

The high level programming language used in the included examples and source code is Python 2.6. Some experience of using the Python programming language is helpful but not required.

What you will learn

By following through the material in this white paper, you will learn:

• What the Weighted Maximum Independent Set (WMIS) problem is and why it is hard
• How to write WMIS in a form that the D-Wave hardware can understand
• How to use the BlackBox compiler to solve problems of this type
• Software requirements

In order to proceed you should install several free software packages.

• Python - The material here assumes you are using Python 2.6. You can download Python from http://www.Python.org. If you need a programming development environment, Pycharm from Jetbrains http://www.jetbrains.com/pycharm/ is excellent. There is a small license fee to use it.
• NumPy - This is a scientific computing library. It is at http://numpy.scipy.org/
• NetworkX - This is a Python graphing library. It is at http://networkx.lanl.gov/index.html
• SECTION 1

1.1 - Problem Definition

Imagine you have a collection of objects. Each is labeled with a positive number, which we'll call its weight. Furthermore, some of these objects (but not all) are connected to each other. The Weighted Maximum Independent Set (WMIS) problem asks for the "heaviest" set of objects (the set whose labels sum to the largest number) where no two objects in this set are connected by an edge.

If all of the weights are equal, this problem reduces to Maximum Independent Set.

Here is a simple example. Imagine you are given the graph shown in Figure 1 below. This graph has five objects (we'll refer to these as vertices from now on ? they are the "dots" in the graph) with weights as shown in the Figure, connected by a total of five edges (the lines connecting the dots) in a particular pattern.

Figure 1. A graph with five vertices and five edges. The labeling convention is vertex number, vertex weight, so vertex 0 has weight 0.45. An independent set in a graph is a subset of its vertices where no two members of this subset are connected by an edge. For example, the subsets {0,4} and {2,4} are independent sets, but {0,3,4} is not (because 3 and 4 are connected by an edge). The WMIS problem asks for the independent set of the graph whose weights of the elements of the set sum to the largest number. For example, the independent set {0,4} has weight 0.45 + 0.24 = 0.69, while {2,4} has weight 0.64 + 0.24 = 0.88. Because {2,4} is "heavier", it's "better" than {0,4}. For this graph, the WMIS solution is shown in cyan ? there is no independent set in this graph heavier than {2,3} = 0.64 + 0.53 = 1.17.

1.2 - Using D-Wave BlackBox to solve WMIS

We are going to use the networkx python module, available from http://networkx.lanl.gov/index.html, to store and manipulate the graphs in this example. Networkx is very useful for working with graphs, and will save you a lot of time in developing, manipulating and and visualizing graph-based representations of problems - it is highly recommended! Before we proceed, you should download and install it.

The networkx package allows you to easily define many different kinds of graphs. One example that's interesting for MIS are Erdos-Renyi (ER) graphs. An ER graph is one where you first fix the number of vertices, and then randomly draw an edge between each pair of vertices with a fixed probability that you provide. These types of graphs are interesting for MIS because the typical size of the MIS for large graphs is known, and there's a separation between the size of an Independent Set that's easy to find (these have size log 1/(1-p) N, where N is the number of vertices and p is the edge probability), and the size of the MIS which is twice this ( 2 log 1/(1-p) N). No-one has been able to find a polynomial (in N) time algorithm that finds an Independent Set of size (1+c) log 1/(1-p) N for any c>0.

Generating an ER graph is really easy with networkx. Here is a code snippet showing you how to do it.

Code Snippet: Generating an ER graph

```from networkx.generators.random_graphs import erdos_renyi_graph

number_of_vertices = 5
edge_probability = 0.5
G = erdos_renyi_graph(number_of_vertices, edge_probability)
```

This loads up an ER graph with 5 vertices and 50% probability of drawing an edge between any two vertices into G. Adding vertex weights to the graph is really easy. Here is how you do it if you want to assign random weights to each vertex:

Code Snippet: Assigning random weights to vertices

```import random

for i in range(number_of_vertices):
G.node[i]['weight'] = random.random()

```

A common format for storing and distributing graphs is the DIMACS format. Here is a code snippet for reading in a DIMACS file and converting it to an unweighted networkx graph (if you want to add vertex weights you can do this separately).

Code Snippet: Reading in DIMACS file and converting it to a graph

```import networkx as nx

##############################################################################
#

G = nx.Graph()

for k in range(N_v):

for k in range(N_e):
G.add_edge(int(split_line[1])-1, int(split_line[2])-1) # subtract 1 because of zero indexing!

return G

##############################################################################

```

One source of interesting graphs in DIMACS format is here: http://www2.research.att.com/~njas/doc/graphs.html, which contains a bunch of graphs arising in developing error correcting codes, where to find the best codes you need to solve MIS problems. Many commonly used benchmark instances are referenced here: http://www.ict.griffith.edu.au/~s994853/papers/wmis2.pdf.

1.5 - A function for computing WMIS

This function computes the WMIS of a graph G. If solver_flag = 0 we use exact enumeration; if solver_flag = 1 we use D-Wave BlackBox. What is going on in this function is that we are recasting the WMIS problem as an Ising model problem, and then solving the Ising model problem using either exact enumeration or D-Wave BlackBox. The translation between WMIS and Ising is very simple and is found in http://arxiv.org/pdf/1004.2226.pdf directly below equation (3) - this is what we implement in the code here.

Code Snippet: Converting from WMIS to Ising

```from dwave_sapi import local_connection, BlackBoxSolver
from numpy import zeros
import numpy
import time

##############################################################################
#
# Function for computing the weighted maximum independent set of a networkx graph
# G. solver_flag = 0 means use exact enumeration; solver_flag = 1 means use D-Wave
# BlackBox.

def weighted_maximum_independent_set(G, solver_flag):

solver = local_connection.get_solver("c4-sw_sample")

normJ = 1.1
blackbox_parameter = 1; cluster_number_parameter = 2 # cluster_number_parameter needs to be even!!!!
number_of_vertices = G.number_of_nodes()
biggest_independent_set_found = []
h = zeros((1,number_of_vertices), dtype = numpy.float)
for i in range(number_of_vertices):
h[0,i] = (normJ*G.degree(i)-2*G.node[i]['weight'])

J = zeros((number_of_vertices, number_of_vertices), dtype = numpy.float)
for i in range(number_of_vertices):
for k in range(i):
if G.has_edge(i,k):
J[k,i]=normJ
if solver_flag:
obj = BB_solve_ising(h[0], J)
blackbox_solver = BlackBoxSolver(solver)
start_time = time.time()
answer = blackbox_solver.solve(obj, number_of_vertices, cluster_num = cluster_number_parameter,
min_iter_inner = blackbox_parameter, max_iter_outer= blackbox_parameter,
unchanged_threshold=blackbox_parameter, max_unchanged_objective_outer=blackbox_parameter,
max_unchanged_objective_inner = blackbox_parameter,
unchanged_best_threshold = blackbox_parameter, verbose=0)

time_to_return = time.time() - start_time
else:
start_time = time.time()
time_to_return = time.time() - start_time

for i in range(number_of_vertices):
biggest_independent_set_found.append(i)

return time_to_return, biggest_independent_set_found

##############################################################################
```

The solver functions called here are (first for exact enumeration)

Code Snippet: Solving the problem using enumeration

```from numpy import ones, dot
import numpy
from copy import deepcopy

##########################################################################################################
#
# These functions are for solving the optimization by exact enumeration.

def int2bin(nn, N):
"""returns the binary of integer nn, using N number of digits"""
return "".join([str((nn >> y) & 1) for y in range(N-1, -1, -1)])

def enumeration_solve_ising(h, J):

numvars=len(h[0])
w = -ones((1,numvars), dtype=numpy.int)

energy_list=[] # this is going to store all 2^K energies and w values.
for m in range(2**numvars): # cycle over all possibilities
bin_m=int2bin(m,numvars)
for mm in range(numvars):
w[0,mm]=2*int(bin_m[mm])-1 # value of w (+1/-1) for this value of m
result = dot(h[0], w[0])+dot(w[0],dot(J,w[0]))
energy_list.append([result,deepcopy(w)]) # add the result for this m.
sorted_energy_list = sorted(energy_list, key=lambda outp:outp[0]) # sort results, lowest..highest energy
return sorted_energy_list[0][1][0] # return value of w corresponding to lowest energy

##########################################################################################################

```

And for D-Wave BlackBox:

Code Snippet: Solving the problem using BlackBox

```from numpy import array, dot

##########################################################################################################
#
# This class defines a function object for solving Ising models of the form G(s) = h.s + s.J.s using
# BlackBox. Here both h and J are numpy float arrays of size N and NxN respectively. An example for N=3:
#
# h = [-0.9  0.2 -0.9]
# J = [[ 0.   1.1  0. ]
#      [ 0.   0.   1.1]
#      [ 0.   0.   0. ]]

class BB_solve_ising(object):

def __init__(self, h, J):
self.h = h
self.J = J

def __call__(self, states, numStates):

stateLen = len(states)/numStates
ret = []
for state_number in range(numStates):
w = array(states[state_number*stateLen:(state_number+1)*stateLen])
result = dot(self.h, w)+dot(w,dot(self.J,w))
ret.append(result)

return tuple(ret)

##########################################################################################################

```

SECTION 2

2.1 - Trying it out!

Now we have everything we need to try it out. As a test, we solved some of the smaller challenge problems at http://www2.research.att.com/~njas/doc/graphs.html using D Wave BlackBox. Shown in Table 1 are the results. We ran each problem with the fastest parameters (blackbox_parameter = bb_p = 1 and cluster_number_parameter = c_n_p = 2) and then incremented each of these, beginning with blackbox_parameter, until BlackBox returned an Independent Set of the size of the known MIS or both parameters reached values of 10 (we could have kept going, but seeing as this is a tutorial that's probably good enough). We recorded the parameter settings used, and the time it took the solver to find the MIS.

Here is a simple code snippet used to run these experiments:

Code Snippet: Challenge problems

```G = load_dimacs_file_into_networkx_graph('1dc.64.txt')

print "The graph has", G.number_of_nodes(), "vertices and", G.number_of_edges(), "edges."
elapsed_time, BB_IS = weighted_maximum_independent_set(G, 1)
print "The largest weight independent set found by D-Wave BlackBox is", BB_IS, \
"its size is", len(BB_IS), "and it took", elapsed_time, "seconds to find it."

```

Note that `blackbox_parameter` and `cluster_number_parameter` are changed within the `weighted_maximum_independent_set(G, 1)` function call.

Table 1. Some results of running the WMIS code on small MIS challenge problems at http://www2.research.att.com/~njas/doc/graphs.html. bb_p is short for blackbox_parameter and c_n_p is short for cluster_number_parameter).

In this exercise you will build an application of WMIS and implement it using the code here.

WMIS arises naturally in situations where you need to select a subset of some group, but there are reasons why you can't select certain pairs. As an example, maybe you'd like to choose events from a group to accomplish a task, but for some reason certain pairs of events can't both happen at the same time.

Here is an example. Let's say you are the athletics coordinator at a university, and it's the beginning of the school year. You are holding a sports day for the new students, and need to schedule a game for each of the sports your university has programs in. As an example, you might have wrestling, football, baseball, basketball, fencing, judo, water polo and volleyball.

Each new student can sign up for one or more of the sports. The games can run simultaneously, as long as each game doesn't have so many shared participants that both couldn't run simultaneously. For example, if everyone signed up for both wrestling and volleyball, we couldn't run those both at the same time as there wouldn't be enough players to do both.

Now let's say there is a special event planned for parents in the afternoon of the sports day, and you have been asked to schedule as many simultaneous games as possible for that event.

To model this problem as WMIS, you can do this: create a vertex for each sport, and we'll weight the vertices according to how important the sport is to the school - higher weights mean the school views them as being more important to showcase. We draw edges between vertices if the number of students that have signed up for each is greater than a threshold meaning that both couldn't run at the same time.

Here's an example DIMACS file, and a small modification to the code included here that adds weights to the nodes in your graph. The nodes are labeled as follows: (1) wrestling; (2) football; (3) baseball; (4) basketball; (5) fencing; (6) judo; (7) water polo and (8) volleyball. Remember that the DIMACS file is 1-indexed while the networkx convention is 0-indexed (so when you add weights in the code snippet below, the numbering starts at zero, not one). If you look at the weights you'll see that the school really likes volleyball and water polo, while fencing is lowest on the list.

Figure 2. A graph representing our sports events example

DIMACS file for this example:

p edge 8 7
e 1 5
e 3 7
e 4 7
e 5 6
e 5 8
e 6 7
e 7 8

Code modifications for this example:

Modify the function `load_dimacs_file_into_networkx_graph(file_name)` to allow weights to be added to the nodes, i.e. change the lines:
```for k in range(N_v):
```

to the following:

```G.add_node(0, weight = 0.31)