max_cut.solvers

MaxCut solver.

Module Contents

Classes

MaxCutSolvers

Maxcut solver for solving maxcut problem.

class max_cut.solvers.MaxCutSolvers

Bases: noisecut.max_cut.base_maxcut.BaseMaxCut

Maxcut solver for solving maxcut problem.

set_weight_1d_and_n_vertices(weight: numpy.typing.NDArray[numpy.float_] | list[float], n_vertices: int) → None

Set Number of vertices and weight of edges between vertices.

Parameters:

• weight (ndarray of shape(n_edges,)) – 1D array weight data, see Notes.

• n_vertices (int) – Number of vertices.

Notes

When n_vertices=4, the weight data can be stored in two different formats:

2D array : w_2d[node A][node B] 1D array : w_1d[index of array] = w_2d[node_A][node_B]

Index of 1D array:(node A, node B) -> 0:(0,1), 1:(0,2), 2:(0,3), 3:(1,2), 4:(1,3), 5:(2,3)

Index of arrayint

node_A * {2 * n_vertices - 3 - node_A} // 2 + node_B - 1

set_weight_2d_and_n_vertices(weight: numpy.typing.NDArray[numpy.float_] | list[float], n_vertices: int)

Set Number of vertices and weight of edges between vertices.

Parameters:

• weight (ndarray of shape(n_vertices, n_vertices)) – 2D array weight data, see Notes.

• n_vertices (int) – Number of vertices.

Notes

When n_vertices=4, the weight data can be stored in two different formats:

2D array : w_2d[node A][node B] 1D array : w_1d[index of array] = w_2d[node_A][node_B]

Index of 1D array:(node A, node B) -> 0:(0,1), 1:(0,2), 2:(0,3), 3:(1,2), 4:(1,3), 5:(2,3)

Index of arrayint

node_A * {2 * n_vertices - 3 - node_A} // 2 + node_B - 1

calc_index_of_linear_array(i: int, j: int) → int

Return index of weight array between two vertices of i and j.

Parameters:

• i (int) – Number representative of a specific vertex.

• j (int) – Number representative of a specific vertex.

Returns:

Index of weight array between two vertices of i and j.

Return type:

int

Notes

When n_vertices=4, the weight data can be stored in two different formats:

2D array : w_2d[node A][node B] 1D array : w_1d[index of array] = w_2d[node_A][node_B]

Index of 1D array:(node A, node B) -> 0:(0,1), 1:(0,2), 2:(0,3), 3:(1,2), 4:(1,3), 5:(2,3)

Index of arrayint

node_A * {2 * n_vertices - 3 - node_A} // 2 + node_B - 1

solve_maxcut() → tuple[float, numpy.typing.NDArray[numpy.bool_]]

Solve MaxCut problem by utilizing CPLEX optimization package.

Returns:

• objective (float) – Value of the maximum cut.

• solution (ndarray of bool of shape(n_vertices,)) – Label vertices to 0 or 1 to divide the set to two sets. Index of the sol array is representative of each vertex, like sol[0] represents the label for the vertex 0.