modules.applications.optimization.scp.scp.SCP

class SCP

Bases: Optimization

The set cover problem (SCP) is a classical combinatorial optimization problem where the objective is to find the smallest subset of given elements that covers all required elements in a collection. This can be formulated as selecting the minimum number of sets from a collection such that the union of the selected sets contains all elements from the universe of the problem instance.

SCP has widespread applications in various fields, including sensor positioning, resource allocation, and network design. For example, in sensor positioning, SCP can help determine the fewest number of sensors required to cover a given area. Similarly, in resource allocation, SCP helps to allocate resources in an optimal way, ensuring coverage of all demand points while minimizing costs. Network design also uses SCP principles to efficiently place routers or gateways in a network to ensure full coverage with minimal redundancy.

This implementation of SCP provides configurable problem instances of different sizes, such as "Tiny," "Small," and "Large," allowing the user to explore solutions with varying complexities. We employ various quantum-inspired methods to solve SCP, including a mapping to the QUBO (Quadratic Unconstrained Binary Optimization) formulation using Qubovert. These approaches allow us to explore how different optimization algorithms and frameworks perform when applied to this challenging problem, offering insights into both classical and emerging quantum methods.

__init__()

Constructor method.

Methods

__init__()	Constructor method.
evaluate(solution)	Calculates the number of subsets that are of the solution.
generate_problem(config)	Generates predefined instances of the SCP.
get_application()	Gets the application.
get_available_submodule_options()	Gets the list of available options.
get_available_submodules(option)	If the module has submodules depending on certain options, this method should adjust the submodule_options accordingly.
get_default_submodule(option)	Returns the default submodule based on the provided option.
get_depending_parameters(option, config)	If the module has parameters depending on certain options, this method should return the parameters for the given option.
get_parameter_options()	Returns the configurable settings for this application
get_requirements()	Returns the required pip packages for this module.
get_solution_quality_unit()	Returns the unit of the evaluation.
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)	Returns list of selected subsets and the time it took to process the solution.
save(path, iter_count)	Saves the SCP instance to a file.
validate(solution)	Checks if the elements of the subsets that are part of the solution cover every element of the instance.
visualize_solution(processed_solution, path)	Creates visualizations of a processed and validated solution and writes them to disk.

class Config

Bases: TypedDict

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 number of subsets that are of the solution.

Parameters:

solution -- List containing all subsets that are part of the solution

Returns:

Number of subsets and the time it took to calculate it

generate_problem(config: Config) → tuple[set, list]

Generates predefined instances of the SCP.

Parameters:

config -- Config specifying the selected problem instances

Returns:

The union of all elements of an instance and a set of subsets, each covering a part of the union

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

If the module has submodules depending on certain options, this method should adjust the submodule_options accordingly.

Parameters:

option -- List of chosen options

Returns:

List of available submodules

get_default_submodule(option: str) → Application

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

If the module has parameters depending on certain options, this method should return the parameters for the given option.

Parameters:

• option -- The chosen option

• config -- Current config dictionary

Returns:

The parameters for the given option

get_parameter_options()

Returns the configurable settings for this application

Returns:

Dictionary containing parameter options

return {

"model_select": {

"values": list(["Tiny", "Small", "Large"]), "description": "Please select the problem size(s). Tiny: 4 elements, 3 subsets. Small: 15 elements, 8 subsets. Large: 100 elements, 100 subsets"

}

}

static get_requirements() → list

Returns the required pip packages for this module. Optionally, version requirements can be added.

Returns:

List of dictionaries

get_solution_quality_unit() → str

Returns the unit of the evaluation.

Returns:

String with the unit

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: list) → tuple[list, float]

Returns list of selected subsets and the time it took to process the solution.

Parameters:

solution -- Unprocessed solution

Returns:

Processed solution and the time it took to process it

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

Saves the SCP instance to a file.

Parameters:

• path -- Path to save the SCP instance

• iter_count -- Iteration count

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

Checks if the elements of the subsets that are part of the solution cover every element of the instance.

Parameters:

solution -- List containing all subsets that are part of the solution

Returns:

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

visualize_solution(processed_solution: any, path: str) → None

Creates visualizations of a processed and validated solution and writes them to disk. Override if applicable. Default is to do nothing.

Parameters:

• processed_solution -- A solution that was already processed by process_solution()

• path -- File path for the plot

Returns:

None