GoemansWilliamsonOptimizer¶
- class GoemansWilliamsonOptimizer(num_cuts, sort_cuts=True, unique_cuts=True, seed=0)[source]¶
Bases:
OptimizationAlgorithm
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 thannum_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.