MWC_inst

Generates MaxCut (“MWC”) instances by generating random graphs.

USAGE:

python -m MWC_inst ./instances

Generates a set of MaxCut instances, saving original instance data in ./instances (or another specified directory): orig subdirectory for original instances and QUBO, respectively, for QUBOs.

Instance parameters are specified in main(), which in turn calls the core generation function, generate_MWC_instances(). This module also contains a few cross-checks, auxiliary and visualization code.

Functions

assert_MWC_MIP(orig_json, qubo_model[, ...])	Asserts if the objectives for QUBO and original MWC (MIP) coincide.
create_MWC_LBOP(G[, quiet, timeout])	Creates a linear binary problem from the underlying graph G.
create_MWC_QUBO(G)	Given the graph G, creates a QUBO formulation.
draw_IDs_grid(sel_IDs[, directory, Ncols, ...])	Draws a grid of instances by (the number part of) IDs.
draw_inst_grid(selected_files[, Ncols, ...])	Draws a grid of instances from selected_files.
draw_instance(G[, ax, node_color, ...])	Draws weighted graph G.
extract_G_from_json(js)	Helper: extracts the graph from the problem JSON.
generate_MWC_instances([K, Ns, Ps, Cmin, ...])	Core function: generates a set of MWC instances with given parameters.
generate_instance(p, N, C)	Generates a (single) graph for a MaxCut instance.
get_objective_from_sol(G, sol)	Calculates a MaxCut objective given the graph and solution bistring.
load_instance_by_ID(ID[, directory])	Loads an instance by ID and returns graph G.
load_orig_MWC_instance(filename)	Loads the instance from filename.
main()	The main function specifying instance generation parameters (see the source code).
save_orig_MWC_instance(G, inst_id, problem_name)	Saves a MaxCut instance encoded by graph G to a JSON (with metadata).

MWC_inst.generate_instance(p, N, C)

Generates a (single) graph for a MaxCut instance.

Uses Erdos-Renyi model for random graphs.

Parameters:

• p – Erdos-Renyi parameter (probability of an edge between any two given vertices),

• N – number of vertices,

• C – maximum (absolute) value of the edge weight.

Returns:

Weighted graph G.

MWC_inst.draw_instance(G, ax=<Axes: >, node_color='blue', node_size=200, with_labels=True)

Draws weighted graph G.

MWC_inst.draw_inst_grid(selected_files, Ncols=3, directory='./instances-new/QUBO', cross_check=True)

Draws a grid of instances from selected_files.

Parameters:

• selected_files (list) – list of files (*.qubo.json)

• Ncols (int) – number of columns in the grid.

• directory (str) – directory with QUBO files (*.qubo.json)

MWC_inst.draw_IDs_grid(sel_IDs, directory='./instances-new/QUBO', Ncols=3, cross_check=False)

Draws a grid of instances by (the number part of) IDs.

Parameters:

• sel_IDs (list[int]) – list of instance IDs (numbers)

• directory (str) – directory with QUBO files (*.qubo.json)

• Ncols (int) – number of columns in the grid

Returns:

selected file names.

MWC_inst.create_MWC_QUBO(G: Graph)

Given the graph G, creates a QUBO formulation.

Parameters:

G (nx.Graph) – the underlying weighted graph,

Returns:

QUBO coefficients as np.arrays

Return type:

Q, P

Notes

• We assume QUBO in the form:

  min (1/2) x’ Q x + P x

MWC_inst.create_MWC_LBOP(G, quiet=False, timeout=None)

Creates a linear binary problem from the underlying graph G.

Parameters:

• G (nx.Graph) – the underlying weighted graph,

• quiet (bool) – suppress model output (flag),

• timeout (int) – timeout for the solver (seconds)

Returns:

a tuple of m (gurobipy model), z (z-vars), x (x-vars)

MWC_inst.save_orig_MWC_instance(G, inst_id, problem_name, comment='', directory='./instances/orig/', filename=None)

Saves a MaxCut instance encoded by graph G to a JSON (with metadata).

Parameters:

• nodes – list of nodes,

• edges – list of tuples (i, j, w), where (i, j) is the edge, w is the weight

• inst_id (string) – instance ID,

• problem_name (string) – (relatively) human-readable name,

• comment – optional comment for the JSON file,

• directory – a dir to save files.

MWC_inst.extract_G_from_json(js) → Graph

Helper: extracts the graph from the problem JSON.

Assumes original JSON format (typically, in instances/orig/ folder).

MWC_inst.load_instance_by_ID(ID, directory='./instances/orig/')

Loads an instance by ID and returns graph G.

MWC_inst.load_orig_MWC_instance(filename)

Loads the instance from filename.

MWC_inst.generate_MWC_instances(K=3, Ns=[5, 10, 15], Ps=[0.1, 0.25, 0.5, 0.75, 0.9], Cmin=1, Cmax=10, seed=2023, instdir='./instances')

Core function: generates a set of MWC instances with given parameters.

Creates K * len(Ns) * len(Ps) instances, using the given random seed and the costs bounds, and saves them to directory instdir.

Parameters:

• K (int) – number of instances per set of parameters,

• Ns (list[int]) – instance sizes,

• Ps (list[float]) – p parameter for ER random graph model,

• Cmin (int) – min/max edge costs,

• Cmax (int) – min/max edge costs,

• seed (int) – random seed

• instdir (str) – directory to save instances to.

MWC_inst.get_objective_from_sol(G: Graph, sol: str) → float

Calculates a MaxCut objective given the graph and solution bistring.

Note

Assumes direct order of bits in the solution. E.g., [n0, n1, n2, ...].

MWC_inst.main()

The main function specifying instance generation parameters (see the source code).

MWC_inst.assert_MWC_MIP(orig_json, qubo_model, quiet=True, tol=0.001, timeout=None) → None

Asserts if the objectives for QUBO and original MWC (MIP) coincide.