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.

প্যারামিটার:

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)[source]#

Checks whether a given problem can be solved with the optimizer implementing this method.

প্যারামিটার:: problem (QuadraticProgram) -- The optimization problem to check compatibility.
রিটার্নস:: Returns the incompatibility message. If the message is empty no issues were found.
রিটার্ন টাইপ:: str

is_compatible(problem)#

Checks whether a given problem can be solved with the optimizer implementing this method.

প্যারামিটার:: problem (QuadraticProgram) -- The optimization problem to check compatibility.
রিটার্নস:: Returns True if the problem is compatible, False otherwise.
রিটার্ন টাইপ:: bool

static max_cut_value(x, adj_matrix)[source]#

Compute the value of a cut from an adjacency matrix and a list of binary values.

প্যারামিটার:

রিটার্নস:

value of the cut.

রিটার্ন টাইপ:

float

solve(problem)[source]#

Returns a list of cuts generated according to the Goemans-Williamson algorithm.

প্যারামিটার:: problem (QuadraticProgram) -- The quadratic problem that encodes the max-cut problem.
রিটার্নস:: A list of generated cuts.
রিটার্ন টাইপ:: cuts