modules.applications.optimization.bp.bp.BP

class BP

Bases: Optimization

The bin packing problem is a classic optimization challenge where items of varying sizes must be efficiently packed into a finite number of bins, each with a fixed capacity, aiming to minimize the number of bins utilized. This problem is computationally NP-hard, meaning that finding an exact solution in a reasonable time frame is often impractical for large datasets. Consequently, various approximation algorithms have been developed to provide near-optimal solutions within acceptable time limits.

In practical applications, bin packing is prevalent in industries such as logistics and manufacturing. For instance, it is used in loading trucks with weight capacity constraints, filling containers to maximize space utilization, and creating file backups in media storage. Additionally, it plays a role in technology mapping for FPGA semiconductor chip design, where efficient resource allocation is crucial.

To address the bin packing problem, several heuristic and approximation methods have been proposed. One common approach is the First-Fit Decreasing (FFD) algorithm, which involves sorting items in descending order by size and then placing each item into the first bin that can accommodate it. While FFD does not always yield an optimal solution, it is effective and widely used due to its simplicity and efficiency. Other advanced techniques, such as Best-Fit and Karmarkar–Karp algorithms, offer improved performance for specific scenarios by considering different strategies for item placement and bin selection. (source: https://en.wikipedia.org/wiki/Bin_packing_problem)

__init__(): Constructor method

Methods

`__init__`()	Constructor method
`create_bin_packing_instance`(...)	Generates a bin packing problem instance depending on the mode and the number of objects.
`detect_mapping_from_solution`(solution)	Detects the mapping type based on the solution format.
`evaluate`(solution)	Find the number of used bins for a given solution.
`generate_problem`(config)	Generates a bin-packing problem instance with the input configuration.
`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`()	Return requirements of this module.
`get_solution_quality_unit`()	Returns the unit of measurement for the 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 concrete problem.
`validate`(solution)	Checks if a given solution is feasible for the problem instance.
`visualize_solution`(processed_solution, path)	Creates visualizations of a processed and validated solution and writes them to disk.

class Config

Bases: TypedDict

Attributes of a valid config.

number_of_objects: int
instance_creating_mode: str

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

create_bin_packing_instance(number_of_objects: int, mode: str) → tuple[list, int, list]

Generates a bin packing problem instance depending on the mode and the number of objects.

Parameters:

number_of_objects -- How many objects should the bin packing problem instance consist of
mode -- Declares the mode with which the bin packing problem instance should be created

Returns:

Tuple with object_weights, bin_capacity, incompatible_objects

static detect_mapping_from_solution(solution: dict) → str

Detects the mapping type based on the solution format.

Parameters:: solution -- A dictionary representing the solution
Returns:: The detected mapping type

evaluate(solution: dict) → tuple[float, float]

Find the number of used bins for a given solution.

Parameters:: solution -- Dictionary containing the solution values
Returns:: Tour cost and the time it took to calculate it

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

Generates a bin-packing problem instance with the input configuration.

Parameters:: config -- Configuration dictionary with problem settings
Returns:: Tuple with object_weights, bin_capacity, incompatible_objects

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) → 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

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() → dict

Returns the configurable settings for this application.

Returns:

return {
    "number_of_objects": {
        "values": list([3,4,5,6,7,8,9,10,15,20]),
        "description": "How many objects do you want to fit inside the bins?",
        },
    "instance_creating_mode": {
        "values": list(["linear weights without incompatibilities",
                        "linear weights with incompatibilities",
                        "random weights without incompatibilities",
                        "random weights with incompatibilities"]),
        "description": "How do you want to create the object weights?"
        }
    }

static get_requirements() → list

Return requirements of this module.

Returns:: List of dict with requirements of this module

get_solution_quality_unit() → str

Returns the unit of measurement for the solution quality.

Returns:: Unit of measurement for the 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 concrete problem.

Parameters:

path -- Path of the experiment directory for this run
iter_count -- The iteration count

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

Checks if a given solution is feasible for the problem instance.

Parameters:: solution -- List containing the nodes of the solution
Returns:: Boolean whether the solution is valid, 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