Maximum-Cut

Maximum-Cut is the problem of maximizing the weights of edges between different groups when partitioning into two subsets in a given vertex set of graph.

Simple Example

First, let’s we solve the maximum-cut of following simple graph.

data = """5 6
1 2 1
1 4 1
2 3 1
2 4 1
3 5 1
4 5 1
"""

import networkx
import matplotlib.pyplot as plt

# create networkx graph
G = networkx.Graph()
f = iter(data.split("\n"))
N, E = map(int, next(f).split())  # N is the number of vartexes, and E is the number of edges
for e in range(E):
    i, j, w = map(int, next(f).split())
    G.add_edge(i, j, weight=w)

# plot the graph
fig, ax = plt.subplots()
pos = {1: (0, 1), 2: (1, 2), 3: (2, 2), 4: (1, 0), 5: (2, 0)}
networkx.draw_networkx(G, pos, with_labels=True, node_color="white", edgecolors="black")
ax.set_title("Example simple Graph")

We divide these five vertexes into two groups, \(S\) and \(T\). We create and assign a spin variable \(s_i\) to the vertex \(i\) of the graph, where spin variable only takes +1 or -1. \(s_i = +1\) represents vertex \(i\) is in group \(S\), and \(s_i = -1\) represents vertex \(i\) is in group \(T\). This gives us that \((1 - s_i s_j)\) takes 0 only if vertex \(i\) and \(j\) are belong to same group, and takes 1 only if these vertexes are belongs to different groups. Hence, the maximum cut problem is formulated as \(\max \sum_{i < j} w_{i, j} (1 - s_i s_j)\), where \(w_{i, j}\) is the weight of edge \((i, j)\).

from flopt import *

G = networkx.Graph()
f = iter(data.split("\n"))
N, E = map(int, next(f).split()) # N is the number of vartexes, and E is the number of edges

# create spin variables
s = Variable.array("s", N, cat="Spin", ini_value=1)

# create objective function
obj = 0
for e in range(E):
    i, j, w = map(int, next(f).split())
    obj += w * (1 - s[i-1] * s[j-1])

# create problem
prob = Problem(sense=Maximize)
prob += obj

# solve
staus, log = prob.solve(solver="Random", timelimit=1)

print("result = ", Value(s))
>>> [-1 1 -1 -1 1]

Plot the result partitioning.

# plot the graph
nodelist = [i+1 for i in range(N) if s[i].value() == 1]
networkx.draw_networkx_nodes(G, pos, nodelist=nodelist, node_color="black", ax=ax)
ax.set_title("Result")

Gset Benchmark

Gset is the benchmark the maximize cut problem. We can download the Gset benchmark as follows.

mkdir Gset && cd Gset; for i in {1..81}; do wget http://web.stanford.edu/~yyye/yyye/Gset/G$1; done

# select problem
file = "./Gset/G11"

from flopt import *

def loader(f, n):
    for i in range(n):
        yield map(int, next(f).split())

# load problem, and create spin variables and objective function
with open(file, "r") as f:
    N, E = map(int, next(f).split())
    s = Variable.array("s", N, cat="Spin")
    obj = 0.5 * Sum(w * (1 - s[i-1] * s[j-1]) for i, j, w in loader(f, E))

# create Problem
prob = Problem(sense=Maximize)
prob += obj

# select algorithm to search and solve
status, log = prob.solve(solver="Random", timelimit=10, msg=True)

Convert another formulations

We can obtain the data for the another formulation using flopt.convert, for example ising structure.

\(\min - x^T J x - h^T x + C\)

import flopt.convert

ising = flopt.convert.IsingStructure.fromFlopt(prob)
print(ising.J)
print(ising.h)
print(ising.x)

When you have the solution by your algorithm or other applications, you can input the value to the spin variable of flopt.

values = [...]  # solution; list of values
for var, value in zip(ising.x, values):
    var.setValue(value)