MIS_inst

Generates Unit Disc Max Independent Set (UDMIS) instances.

Creates each instance from a generated random collection of points on a 2D plane.

USAGE:

python -m MIS_inst –dataset small ./instances

python -m MIS_inst –dataset large ./instances

Generates a set of UDMIS instances, saving original instance data in ./instances (or another specified directory): orig subdirectory for original instances and QUBO, respectively, for QUBOs. Can create either small dataset (9 instances with suffix TG in the name, for manual inspection), or a large one (the main dataset with EXT suffix in the name).

The instance generation parameters are specified in generate_main_dataset() and generate_TG_inst(), respectively, for main and small subsets of instances. Both functions rely on the core generation code in generate_UDMIS_instances(). This module also contains a few cross-checks, auxiliary and visualization code.

Functions

assert_UDMIS_MIP(orig_filename, qubo_model, ...)	Asserts whether QUBO and original OP solutions coincide.
check_QuEra_geometry(orig_files[, verbose])	Checks the geometric constraints for QuEra.
create_MIS_QUBO(G)	Takes a graph and returns QUBO coefficients for a MIS.
create_UDMIS_name(N, wwidth, wheight, R)	Helper: creates an instance name string (UD-MIS).
create_grid_points(N, wwidth, wheight[, seed])	Generates a random (broken) grid of points.
create_orig_MIS_IP(G)	Generates a MIP for the MIS instance given by G.
create_random_points(N, wwidth, wheight[, seed])	Generates a set of random (int-coordinate) points.
draw_IDs_grid(sel_IDs[, directory, Ncols])	Draws a grid of instances by (the unique part of) IDs.
draw_inst_grid(selected_files[, Ncols, ...])	Draws a grid of instances from selected_files.
extract_G_from_json(js)	Helper: Extracts the graph from JSON js.
generate_TG_inst(instdir)	Generates grid instances (TG suffix).
generate_UDMIS_instances([Ns, K, ...])	Main instance generation code for UDMIS instances.
generate_main_dataset(instdir)	Generates the main UD-MIS dataset (EXT suffix).
is_IS(G, solution)	Tests if the solution is an independent set.
load_instance_by_ID(ID[, directory])	Loads an instance by ID and returns graph G.
load_orig_MIS(filename)	Loads an original MIS instance from JSON file.
main()	The main function specifying instance generation parameters (see the source code).
points_to_graph(points, R)	Generate an nx.Graph out of a set of points.
save_orig_UDMIS(N, wwidth, wheight, R, ...)	Saves the original UD-WIS instance in JSON format.
visualize_graph(G[, R, pts, ax, z, ...])	Draws the graph (node labels as coordinates), with node color z.

MIS_inst.create_UDMIS_name(N, wwidth, wheight, R)

Helper: creates an instance name string (UD-MIS).

MIS_inst.create_grid_points(N, wwidth, wheight, seed=2023)

Generates a random (broken) grid of points.

Generates a full grid of (wwidth x wheight) points, and then randomly removes them one by one, until the necessary number of points N is reached.

Returns:

a list of points, each specified by an integer coordinates tuple

Return type:

list[tuple[int, int]]

MIS_inst.create_random_points(N, wwidth, wheight, seed=2023)

Generates a set of random (int-coordinate) points.

Point coordinates generated uniformly random from [0,1) x [0,1), scaled to [0, wwidth) x [0, wheight) and then rounded. If we happen to get duplicate coordinates, we just re-generate the point until we have N unique points.

Parameters:

• N (int) – number of points

• wwidth (int) – width and height of the square to generate points in

• wheight (int) – width and height of the square to generate points in

• seed (int) – random seed for random

Returns:

A list of tuples, each representing integer coordinates (x,y), where 0 <= x <= wwidth and 0 <= y <= wheight.

MIS_inst.points_to_graph(points: tuple, R: float) → Graph

Generate an nx.Graph out of a set of points.

A node is created for each point, and an edge is created whenever the Euclidean distance between two corresponding points is no more than R.

MIS_inst.save_orig_UDMIS(N, wwidth, wheight, R, instance_id, points, G, directory='./instances/orig')

Saves the original UD-WIS instance in JSON format.

Parameters:

• N (int) – number of vertices (points)

• wwidth (float), wheight(float) – coordinate “window”

• R (float) – radius for points generation,

• instance_id (str) – a unique instance ID

• points (list) – coordinates of points,

• G (nx.Graph) – resulting graph,

• directory (str) – dir to save the instance to

Returns:

filename (with the path) for the created file.

File format:

• js[“nodes”]: list of nodes,

• js[“edges”]: list of edges, tuples (i,j) with i < j.

• js[“description”]: info concerning instance generation.

  UDMIS-specific subfields are: - points: dict of point coordinates: {i: (x,y)} - wwidth, wheight: max values for coordinates (window parameters) - R: radius value used

MIS_inst.extract_G_from_json(js) → Graph

Helper: Extracts the graph from JSON js.

MIS_inst.load_orig_MIS(filename) → tuple[Graph, dict]

Loads an original MIS instance from JSON file.

MIS_inst.create_MIS_QUBO(G: Graph) → tuple[array, array]

Takes a graph and returns QUBO coefficients for a MIS.

Returns:

Two np.array-s,

• Q (quadratic coefficients matrix), and

• P (linear coefficients vector).

MIS_inst.generate_UDMIS_instances(Ns=[5, 10, 15], K=1, pts_windows=[(100, 100), (100, 100), (100, 100)], Rs=[25, 25, 25], id_suffix='', id_offset=0, digits=None, seed=2023, each_seed=None, points_generator=<function create_random_points>, instdir='./instances')

Main instance generation code for UDMIS instances.

Creates len(Ns) * K instances, each stemming from a set of points from a 2D window scaled to wwidth x wheight (integer coordinates) specified in pts_windows, and “blockade” radius being one of the values specified by Rs. Points generation is delegated to a separate function given by points_generator (create_random_points() by default).

Lists Ns, Rs, and pts_windows are assumed to have the same length, so that (Ns[i], Rs[i], pts_windows[i]) would specify a single set of parameters.

Parameters:

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

• id_offset (int) – number to offset the ID numbering by (default: 0)

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

• pts_windows (list[tuple]) – a list of tuples of the form (wwidth, wheight) to generate points in.

• Rs (list) – a list of “blockade” radiuses to generate the graph.

• id_suffix (str) – suffix to append to the instance ID (after the number),

• digits (int) – max number of digits in the ID

• seed (int) – random seed for random,

• each_seed (int) – random seed to be used for each instance (if not None)

• instdir (str) – directory to save the generated instances to

MIS_inst.is_IS(G: Graph, solution: list[int]) → bool

Tests if the solution is an independent set.

Parameters:

• G (nx.Graph) – original graph,

• solution (list[int]) – candidate solution

Notes

solution must be in the direct order of nodes

(i.e., [n0, n1, n2, ...])

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

Loads an instance by ID and returns graph G.

MIS_inst.visualize_graph(G: ~networkx.classes.graph.Graph, R=None, pts=None, ax=<Axes: >, z='blue', with_labels=True, node_size=200)

Draws the graph (node labels as coordinates), with node color z.

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

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)

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

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

Example

draw_IDs_grid(['1EXT','3EXT','5TG']) will draw a grid with UMDIS001EXT, UDMIS003EXT, and UDMIS5TG.

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.

MIS_inst.create_orig_MIS_IP(G: Graph) → tuple[Model, dict[int, Var]]

Generates a MIP for the MIS instance given by G.

Returns:

A gurobipy.Model and a dict of variables (x).

MIS_inst.assert_UDMIS_MIP(orig_filename, qubo_model, qubo_x, quiet=True, timeout=None)

Asserts whether QUBO and original OP solutions coincide.

Note

qubo_x argument is unused but kept for compatibility with the testing framework.

MIS_inst.check_QuEra_geometry(orig_files, verbose=True)

Checks the geometric constraints for QuEra.

Parameters:

• orig_files (list[str]) – list of filenames (original instances)

• verbose (bool) – technical output flag.

Returns:

true iff the constraints are satisfied; prints progress on the screen if verbose

MIS_inst.generate_TG_inst(instdir)

Generates grid instances (TG suffix).

See the source code for specific parameter values. Relies on generate_UDMIS_instances() for actual instance generation, with create_grid_points() for points generation.

MIS_inst.generate_main_dataset(instdir)

Generates the main UD-MIS dataset (EXT suffix).

See the source code for specific parameter values. Relies on generate_UDMIS_instances() for actual instance generation, with create_grid_points() for points generation.

MIS_inst.main()

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