modules.applications.optimization.mis.mis.MIS

class MIS

Bases: Optimization

The maximum independent set (MIS) problem is a combinatorial optimization problem that seeks to find the largest subset of vertices in a graph such that no two vertices are adjacent. MIS has numerous application in computer science, network design, resource allocation, and even in physics, where finding optimal configurations can solve fundamental problems related to stability and energy minimization.

In a graph, the maximum independent set represents a set of nodes such that no two nodes share an edge. This property makes it a key element in various optimization scenarios. Due to the problem's combinatorial nature, it becomes computationally challenging, especially for large graphs, often requiring heuristic or approximate solutions.

In the context of QUARK, we employ quantum-inspired approaches and state-of-the-art classical algorithms to tackle the problem. The graph is generated based on user-defined parameters such as size, spacing, and filling fraction, which affect the complexity and properties of the generated instance.

__init__()

Constructor method.

Methods

__init__()	Constructor method.
evaluate(solution)	Calculates the size of the solution.
generate_problem(config)	Generates a graph to solve the MIS problem for.
get_application()	Gets the application.
get_available_submodule_options()	Gets the list of available options.
get_available_submodules(option)	Changes mapping options based on selection of graphs.
get_default_submodule(option)	Returns the default submodule based on the provided option.
get_depending_parameters(option, config)	Returns parameters necessary for chosen problem option.
get_parameter_options()	Returns the configurable settings for this application.
get_requirements()	Returns requirements of this module.
get_solution_quality_unit()	Returns the unit of measurement for solution quality.
get_submodule(option)	Submodule is instantiated according to the information given in self.sub_options.
postprocess(input_data, config, **kwargs)	For optimization problems, we process the solution here, then validate and evaluate it.
preprocess(input_data, config, **kwargs)	For optimization problems, we generate the actual problem instance in the preprocess function.
process_solution(solution)	Most of the time the solution has to be processed before it can be validated and evaluated.
save(path, iter_count)	Saves the generated problem graph to a file.
validate(solution)	Checks if the solution is an independent set.
visualize_solution(processed_solution, path)	Plot the problem graph with the solution nodes highlighted

class Config

Bases: TypedDict

Configuration attributes for generating an MIS problem.

Attributes:

size (int): The number of nodes in the graph. spacing (float): The spacing between nodes in the graph. filling_fraction (float): The fraction of available places in the lattice filled with nodes

clear() → None.  Remove all items from D.

copy() → a shallow copy of D

fromkeys(value=None, /)

Create a new dictionary with keys from iterable and values set to value.

get(key, default=None, /)

Return the value for key if key is in the dictionary, else default.

items() → a set-like object providing a view on D's items

keys() → a set-like object providing a view on D's keys

pop(k[, d]) → v, remove specified key and return the corresponding value.

If the key is not found, return the default if given; otherwise, raise a KeyError.

popitem()

Remove and return a (key, value) pair as a 2-tuple.

Pairs are returned in LIFO (last-in, first-out) order. Raises KeyError if the dict is empty.

setdefault(key, default=None, /)

Insert key with a value of default if key is not in the dictionary.

Return the value for key if key is in the dictionary, else default.

update([E, ]**F) → None.  Update D from mapping/iterable E and F.

If E is present and has a .keys() method, then does: for k in E.keys(): D[k] = E[k] If E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v In either case, this is followed by: for k in F: D[k] = F[k]

values() → an object providing a view on D's values

evaluate(solution: list) → tuple[int, float]

Calculates the size of the solution.

Parameters:

solution -- List containing the nodes of the solution

Returns:

Set size, time it took to calculate the set size

generate_problem(config: Config) → Graph

Generates a graph to solve the MIS problem for.

Parameters:

config -- Config specifying the size and connectivity for the problem

Returns:

Networkx graph representing the problem

get_application() → any

Gets the application.

Returns:

self.application

get_available_submodule_options() → list

Gets the list of available options.

Returns:

List of module options

get_available_submodules(option: list) → list

Changes mapping options based on selection of graphs.

Parameters:

option -- List of chosen graph type

Returns:

List of available submodules

get_default_submodule(option: str) → Core

Returns the default submodule based on the provided option.

Parameters:

option -- Option specifying the submodule

Returns:

Instance of the corresponding submodule

Raises:

NotImplementedError -- If the option is not recognized

get_depending_parameters(option: str, config: dict) → dict

Returns parameters necessary for chosen problem option.

Parameters:

• option -- The chosen option

• config -- The current config

Returns:

The parameters for the given option

get_parameter_options() → dict

Returns the configurable settings for this application.

Returns:

Configuration dictionary for this application

return {

"size": {

"values": [1, 5, 10, 15], "custom_input": True, "allow_ranges": True, "postproc": int, "description": "How large should your graph be?"

}, "graph_type": {

"values": ["hexagonal", "erdosRenyi"], "postproc": str, "description": "Do you want a hexagonal or an Erdos-Renyi graph?", "depending_submodule": True

}

}

static get_requirements() → list[dict]

Returns requirements of this module.

Returns:

List of dict with requirements of this module

get_solution_quality_unit() → str

Returns the unit of measurement for solution quality.

Returns:

The unit of measure for solution quality

get_submodule(option: str) → Core

Submodule is instantiated according to the information given in self.sub_options. If self.sub_options is None, get_default_submodule is called as a fallback.

Parameters:

option -- String with the options

Returns:

Instance of a module

postprocess(input_data: any, config: dict, **kwargs) → tuple[any, float]

For optimization problems, we process the solution here, then validate and evaluate it.

Parameters:

• input_data -- Data which should be evaluated for this optimization problem

• config -- Config for the problem creation

• kwargs -- Optional additional arguments

Returns:

Tuple with results and the postprocessing time

preprocess(input_data: any, config: dict, **kwargs) → tuple[any, float]

For optimization problems, we generate the actual problem instance in the preprocess function.

Parameters:

• input_data -- Input data (usually not used in this method)

• config -- Config for the problem creation

• kwargs -- Optional additional arguments

Returns:

Tuple with output and the preprocessing time

process_solution(solution: any) → tuple[any, float]

Most of the time the solution has to be processed before it can be validated and evaluated. This might not be necessary in all cases, so the default is to return the original solution.

Parameters:

solution -- Proposed solution

Returns:

Tuple with processed solution and the execution time to process it

save(path: str, iter_count: int) → None

Saves the generated problem graph to a file.

Parameters:

• path -- Path to save the problem graph

• iter_count -- Iteration count for file versioning

validate(solution: list) → tuple[bool, float]

Checks if the solution is an independent set.

Parameters:

solution -- List containing the nodes of the solution

Returns:

Boolean whether the solution is valid and time it took to validate

visualize_solution(processed_solution: list[int], path: str)

Plot the problem graph with the solution nodes highlighted

Parameters:

• processed_solution -- The solution already processed by process_solution(), a list of visited node IDs in order of being visited.

• path -- File path for the plot

Returns:

None