Rmaxcut finds an approximate solution to a weighted max-cut problem via random perturbation. Each line in an input file consists of the first nodeID, the second nodeID and an integer weight. The output gives
N nodeID spin w++ w+- w-+ w--
E nodeID1 nodeID2 weight spin1 spin2
where spin
is either 1 or -1, indicating the partition of nodeID
. On an
N-line, w++
is the sum of positive weights of neighbors with positive spins;
other w**
numbers are similar. These numbers are mostly for debugging
purposes.
To try rmaxcut, you may acquire x-all.txt.gz
from the download
page and run
rmaxcut -r20000 x-all.txt.gz > test.out 2> test.err
It will take a couple of minutes on a single thread. Increasing option -r
,
the number of iterations, often leads to a better solution for the largest few
connected components. Rmaxcut emits good enough solutions to problems at my
hand. I haven't compared it to other more sophisticated max-cut solvers. Use
with caution.
The weighted max-cut problem is to find a bipartition in an undirected graph such that the sum of edge weights between the two partitions are maximized. Max-cut is NP-complete. In physics, solving max-cut is equivalent to finding optimal states in an Ising model without external fields. We often take ideas in physics to find approximate solutions to large-scale max-cut problems. This repo provides such an implementation. It uses a fairly naive algorithm:
- Find connected component. Do the following in each component.
- Randomly partition nodes, or equivalently, randomly assign a spin {-1,1} to each node.
- For each node, flip its spin if doing that increases the weight. Repeat until the total weight can't be improved this way. This is a local maximum.
- Randomly flip 10% of spins, or flip the spins of nodes within a certain distance from a random node (done by BFS). Do step 3 again. If the new local maximum is better, do step 4 on the new state; otherwise, do step 4 on the old state.
- Repeat 3-4 for many times. Then move to the next component.
The algorithm is akin to simulated annealing but without proper annealing. When I have time, I need to try more sophisticated procedures in vein of Monte Carlo methods. This may speed up heuristic search.