English
Languages
English
Bengali
Japanese
Spanish

# GoemansWilliamsonOptimizer¶

class GoemansWilliamsonOptimizer(num_cuts, sort_cuts=True, unique_cuts=True, seed=0)[source]

Goemans-Williamson algorithm to approximate the max-cut of a problem. The quadratic program for max-cut is given by:

max sum_{i,j<i} w[i,j]*x[i]*(1-x[j])

Therefore the quadratic term encodes the negative of the adjacency matrix of the graph.

Parameters:
• num_cuts (int) – Number of cuts to generate.

• sort_cuts (bool) – True if sort cuts by their values.

• unique_cuts (bool) – The solve method returns only unique cuts, thus there may be less cuts than `num_cuts`.

• seed (int) – A seed value for the random number generator.

Methods

 `get_compatibility_msg`(problem) Checks whether a given problem can be solved with the optimizer implementing this method. `max_cut_value`(x, adj_matrix) Compute the value of a cut from an adjacency matrix and a list of binary values. `solve`(problem) Returns a list of cuts generated according to the Goemans-Williamson algorithm.