moptipyapps.binpacking2d.instgen package

Tools for generating 2d bin packing instances.

We want to generate instances of the two-dimensional bin packing problem. These instances should have some pre-defined characteristics, e.g., width and height of the bins, number of items to pack, lower bound/optimal number of bins required by any solution, and so on.

At the same time, the instances should be hard.

We treat this whole thing as an optimization problem. Here, given are the pre-defined instance characteristics and the goal is to find instances that are hard to solve.

Important work on this code has been contributed by Mr. Rui ZHAO (赵睿), <zr1329142665@163.com> a Master’s student at the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授).

Submodules

moptipyapps.binpacking2d.instgen.errors module

An objective function counting deviations from the instance definition.

This objective function will be the smaller, the closer the structure of an instance is to the original instance. Due to our encoding, we create instances whose bin width, bin height, and the number of items is the same as in an existing instance. The lower bound for the required number of bins is also the same.

This objective function here also incorporates some additional features, such as:

1. Is the number of different items similar to those in the original instance? In an existing instance, some items of same width and height could be grouped together. We may have 10 items to pack, but only 3 different item sizes exist. We here compare the number of different item sizes of a generated instance with the number in the instance definition.

2. In a given instance, we can observe the minimum and maximum width and height of any item. If an item in the generated instance is smaller than the minimum or larger than the maximum permitted value in one dimension, this will increase the error count.

3. Additionally, we want the actual minimum and maximum width and height of any item in the generated instance is the same as in the original instance.

4. Finally, we want that the total area covered by all items is the same in the generated instance as in the original instance.

All of these potential violations are counted and added up. Using this objective function should drive the search towards generating instances that are structurally similar to an existing instance, at least in some parameters.

We could push this arbitrarily further, trying to emulate the exact distribution of the item sizes, etc. But this may just lead to the reproduction of the original instance by the search and not add anything interesting.

>>> orig = Instance.from_resource("a04")
>>> space = InstanceSpace(orig)
>>> print(f"{space.inst_name!r} with {space.n_different_items}/"
...       f"{space.n_items} items with area {space.total_item_area} "
...       f"in {space.min_bins} bins of "
...       f"size {space.bin_width}*{space.bin_height}.")
'a04n' with 2/16 items with area 7305688 in 3 bins of size 2750*1220.

>>> from moptipyapps.binpacking2d.instgen.inst_decoding import InstanceDecoder
>>> decoder = InstanceDecoder(space)
>>> import numpy as np
>>> x = np.array([ 0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, ])
>>> y = space.create()
>>> decoder.decode(x, y)
>>> space.validate(y)
>>> res: Instance = y[0]
>>> print(f"{res.name!r} with {res.n_different_items}/"
...       f"{res.n_items} items with area {res.total_item_area} "
...       f"in {res.lower_bound_bins} bins of "
...       f"size {res.bin_width}*{res.bin_height}.")
'a04n' with 15/16 items with area 10065000 in 3 bins of size 2750*1220.
>>> print(space.to_str(y))
a04n;15;2750;1220;1101,1098;2750,244;2750,98;1101,171;1649,171;2750,976;441,122;1649,122;2750,10;2750,1,2;2750,3;1649,1098;2750,878;2750,58;660,122

>>> errors = Errors(space)
>>> errors.lower_bound()
0.0
>>> errors.upper_bound()
1.0
>>> errors.evaluate(y)
0.3778740795710009

>>> y[0] = orig
>>> errors.evaluate(y)
0.0

class moptipyapps.binpacking2d.instgen.errors.Errors(space)

Bases: Objective

Compute the deviation of an instance from the definition.

evaluate(x)

Compute the deviations from the instance definition.

Parameters:

x (list[Instance] | Instance) – the instance

Return type:

float

Returns:

the number of deviations divided by the maximum of the deviations

is_always_integer()

Return True because there are only integer errors.

Retval False:

always

Return type:

bool

log_parameters_to(logger)

Log the parameters of this instance.

Parameters:

logger (KeyValueLogSection) – the logger

Return type:

None

lower_bound()

Get the lower bound of the instance template deviations.

Returs 0.0:

always

Return type:

float

space: Final[InstanceSpace]

the instance description

upper_bound()

Get the upper bound of the number of deviations.

Returs 1.0:

always

Return type:

float

moptipyapps.binpacking2d.instgen.errors_and_hardness module

A combination of the errors and the hardness objective.

>>> orig = Instance.from_resource("a04")
>>> space = InstanceSpace(orig)
>>> print(f"{space.inst_name!r} with {space.n_different_items}/"
...       f"{space.n_items} items with area {space.total_item_area} "
...       f"in {space.min_bins} bins of "
...       f"size {space.bin_width}*{space.bin_height}.")
'a04n' with 2/16 items with area 7305688 in 3 bins of size 2750*1220.

>>> from moptipyapps.binpacking2d.instgen.inst_decoding import InstanceDecoder
>>> decoder = InstanceDecoder(space)
>>> import numpy as np
>>> x = np.array([ 0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, ])
>>> y = space.create()
>>> decoder.decode(x, y)
>>> space.validate(y)
>>> res: Instance = y[0]
>>> print(f"{res.name!r} with {res.n_different_items}/"
...       f"{res.n_items} items with area {res.total_item_area} "
...       f"in {res.lower_bound_bins} bins of "
...       f"size {res.bin_width}*{res.bin_height}.")
'a04n' with 15/16 items with area 10065000 in 3 bins of size 2750*1220.
>>> print(space.to_str(y))
a04n;15;2750;1220;1101,1098;2750,244;2750,98;1101,171;1649,171;2750,976;441,122;1649,122;2750,10;2750,1,2;2750,3;1649,1098;2750,878;2750,58;660,122

>>> obj = ErrorsAndHardness(space, max_fes=100)
>>> obj.lower_bound()
0.0
>>> obj.upper_bound()
1.0
>>> obj.evaluate(y)
0.8776461858988774

>>> obj.evaluate(orig)
0.9866528870384179

class moptipyapps.binpacking2d.instgen.errors_and_hardness.ErrorsAndHardness(space, max_fes=1000000, n_runs=3, executors=(<function setup_rs_f1>, <function setup_rls_f1>, <function setup_rls_f7>))

Bases: Objective

Compute the errors and hardness.

errors: Final[Errors]

the errors objective

evaluate(x)

Compute the combination of hardness and errors.

Parameters:

x (list[Instance] | Instance) – the instance

Return type:

float

Returns:

the hardness and errors

hardness: Final[Hardness]

the hardness objective function

is_always_integer()

Return False because the hardness function returns float.

Retval False:

always

Return type:

bool

log_parameters_to(logger)

Log the parameters of this instance.

Parameters:

logger (KeyValueLogSection) – the logger

Return type:

None

lower_bound()

Get the lower bound of the instance error and hardness.

Returns 0.0:

always

Return type:

float

upper_bound()

Get the upper bound of the instance error and hardness.

Returns 1.0:

always

Return type:

float

moptipyapps.binpacking2d.instgen.experiment module

An example experiment for generating bin packing instances.

moptipyapps.binpacking2d.instgen.experiment.INNER_MAX_FES: Final[int] = 100000

the maximum number of FEs in for the algorithm runs inside the objective

moptipyapps.binpacking2d.instgen.experiment.INNER_RUNS: Final[int] = 3

the numbe rof runs of the algorithms inside the objective

moptipyapps.binpacking2d.instgen.experiment.MAX_FES: Final[int] = 10000

the maximum number of FEs

moptipyapps.binpacking2d.instgen.experiment.cmaes(problem)

Create the basic BiPop-CMA-ES setup.

Parameters:

problem (Problem) – the problem to solve

Return type:

Execution

Returns:

the execution

moptipyapps.binpacking2d.instgen.experiment.run(base_dir)

Run the experiment.

Parameters:

base_dir (str) – the base directory

Return type:

None

moptipyapps.binpacking2d.instgen.hardness module

An objective function assessing the hardness of an instance.

>>> from moptipyapps.binpacking2d.instgen.instance_space import InstanceSpace
>>> orig = Instance.from_resource("a04")
>>> space = InstanceSpace(orig)
>>> print(f"{space.inst_name!r} with {space.n_different_items}/"
...       f"{space.n_items} items with area {space.total_item_area} "
...       f"in {space.min_bins} bins of "
...       f"size {space.bin_width}*{space.bin_height}.")
'a04n' with 2/16 items with area 7305688 in 3 bins of size 2750*1220.

>>> from moptipyapps.binpacking2d.instgen.inst_decoding import InstanceDecoder
>>> decoder = InstanceDecoder(space)
>>> import numpy as np
>>> x = np.array([ 0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, ])
>>> y = space.create()
>>> decoder.decode(x, y)
>>> space.validate(y)
>>> res: Instance = y[0]
>>> print(f"{res.name!r} with {res.n_different_items}/"
...       f"{res.n_items} items with area {res.total_item_area} "
...       f"in {res.lower_bound_bins} bins of "
...       f"size {res.bin_width}*{res.bin_height}.")
'a04n' with 15/16 items with area 10065000 in 3 bins of size 2750*1220.
>>> print(space.to_str(y))
a04n;15;2750;1220;1101,1098;2750,244;2750,98;1101,171;1649,171;2750,976;441,122;1649,122;2750,10;2750,1,2;2750,3;1649,1098;2750,878;2750,58;660,122

>>> hardness = Hardness(max_fes=100)
>>> hardness.lower_bound()
0.0
>>> hardness.upper_bound()
1.0
>>> hardness.evaluate(y)
0.8781459580052053

>>> y[0] = orig
>>> hardness.evaluate(y)
0.9876395399254564

>>> z = Instance.from_compact_str(
...     "cl04_020_01n;19;100;100;1,10;2,38;2,62;1,4,2;3,38;1,7;27,93;1,62;1,"
...     "3;13,38;1,38;1,17;1,45;36,62;39,3;1,2;20,10;3,24;12,4")
>>> hardness.evaluate(z)
0.9995959203471327

moptipyapps.binpacking2d.instgen.hardness.DEFAULT_EXECUTORS: Final[tuple[Callable[[Instance], tuple[Execution, Objective]], ...]] = (<function setup_rs_f1>, <function setup_rls_f1>, <function setup_rls_f7>)

the default executors

class moptipyapps.binpacking2d.instgen.hardness.Hardness(max_fes=1000000, n_runs=3, executors=(<function setup_rs_f1>, <function setup_rls_f1>, <function setup_rls_f7>))

Bases: Objective

Compute the hardness of an instance.

evaluate(x)

Compute the hardness of an instance.

Parameters:

x (list[Instance] | Instance) – the instance

Return type:

float

Returns:

the hardness

executors: Final[tuple[Callable[[Instance], tuple[Execution, Objective]], ...]]

the executors

is_always_integer()

Return False because the hardness function returns float.

Retval False:

always

Return type:

bool

log_parameters_to(logger)

Log the parameters of this instance.

Parameters:

logger (KeyValueLogSection) – the logger

Return type:

None

lower_bound()

Get the lower bound of the instance hardness.

Return type:

float

Returns:

the lower bound for the instance hardness

Returns 0.0:

always

max_fes: Final[int]

the maximum FEs per setup.

n_runs: Final[int]

the maximum FEs per setup.

upper_bound()

Get the upper bound of the instance hardness.

Return type:

float

Returns:

the upper bound for the instance hardness

Returns 1.0:

always

moptipyapps.binpacking2d.instgen.hardness.setup_rls_f1(instance)

Set up the randomized local search for an instance.

Parameters:

instance (Instance) – the instance

Return type:

tuple[Execution, Objective]

Returns:

the execution

moptipyapps.binpacking2d.instgen.hardness.setup_rls_f7(instance)

Set up the randomized local search for an instance.

Parameters:

instance (Instance) – the instance

Return type:

tuple[Execution, Objective]

Returns:

the execution and upper bound of the objective

moptipyapps.binpacking2d.instgen.hardness.setup_rs_f1(instance)

Set up the randomized sampling for an instance.

Parameters:

instance (Instance) – the instance

Return type:

tuple[Execution, Objective]

Returns:

the execution

moptipyapps.binpacking2d.instgen.inst_decoding module

A decoder for 2D BPP instances.

The goal of developing this decoding procedure is that we need a deterministic mapping of some easy-to-process data structure to an instance of the two-dimensional bin packing problem. The instance produced by the mapping should use a pre-defined bin width, bin height, and number of items. It should also have a pre-defined lower bound for the number of bins required and it must be ensured that this lower bound can also be reached, i.e., that at least one solution exists that can indeed pack all items into this number of bins.

As source data structure to be mapped, we choose the real vectors of a fixed length (discussed later on).

The idea is that we take the bin width, bin height, and lower bound of the number of bins (let’s call it lb) from a template instance. We also take the number items (let’s call it n) from that instance.

Now we begin with lb items, each of which exactly of the size and dimensions of a bin. At the end, we want to have n items. To get there, in each step of our decoding, we split one existing item into two items. This means that each step will create one additional item for the instance (while making one existing item smaller). This, in turn, means that we have to do n - lb decoding steps, as we start with lb items and, after n - lb steps, will have lb + n - lb = n items.

So far so good. But how do we split?

Each split that we want to perform be defined by four features:

1. the index of the item that we are going to split,

2. whether we split it horizontally or vertically,

3. where we are going to split it,

4. and how to continue if the proposed split is not possible, e.g., because it would lead to a zero-width or zero-height item.

Now we can encode this in two real numbers selector and cutter from the interval [-1,1].

First, we multiply the absolute value of the selector with the current number of items that we have. This is initially 2, will then be 3 in the next iteration, then 4, and so on. Converted to an int, the result of this multiplication gives us the index of the item to split.

Then, if cutter >= 0, we will cut the item horizontally. Otherwise, i.e., if cutter < 0, we cut vertically. Where to cut is then decided by multiplying the absolute value of cutter with the length of the item in the selected cutting dimension.

If that is not possible, we move to the next item and try again. If selector < 0, we move towards smaller indices and wrap after 0. Otherwise, we move towards higher indices and wrap at the end of the item list. If we arrive back at the first object, this means that the split was not possible for any of the existing items. We now rotate the split by 90°, i.e., if we tried horizontal splits, we now try vertical ones and vice versa.

It is easy to see that it must always be possible to split at least one item in at least one direction. Since we took the bin dimensions and numbers of items from an existing instance of the benchmark set, it must be possible to divide the bins into n items in one way or another. Therefore, the loop will eventually terminate and yield the right amount of items.

This means that with 2 * (n - lb) floating point numbers, we can describe an instance whose result is a perfect packing, without any wasted space.

Now the benchmark instances are not just instances that can only be solved by perfect packings. Instead, they have some wasted space.

We now want to add some wasted space to our instance. So far, our items occupy exactly lb * bin_width * bin_height space units. We can cut at most bin_width * bin_height - 1 of these units without changing the required bins of the packing: We would end up with (lb - 1) * bin_width * bin_height + 1 space units required by our items, which is 1 too large to fit into lb - 1 bins.

So we just do the same thing again: We again use two real numbers to describe each split. Like before, we loop through these numbers, pick the object to split, and compute where to split it. Just now we throw away the piece that was cut off. (Of course, we compute the split positions such that we never dip under the area requirement discussed above).

This allows us to use additional real variables to define how the space should be reduced. 2 * (n - lb) variables, we get instances requiring perfect packing. With every additional pair of variables, we cut some more space. If we would use 2 * (n - lb) + 10 variables, then we would try to select five items from which we can cut off a bit. This number of additional variables can be chosen by the user.

Finally, we merge all items that have the same dimension into groups, as is the case in some of the original instances. We then shuffle these groups randomly, to give the instances a bit of a more unordered texture. The random shuffling is seeded with the binary representation of the input vectors.

In the end, we have translated a real vector to a two-dimensional bin packing instance. Hurray.

>>> space = InstanceSpace(Instance.from_resource("a04"))
>>> print(f"{space.inst_name!r} with {space.n_different_items}/"
...       f"{space.n_items} items with area {space.total_item_area} "
...       f"in {space.min_bins} bins of "
...       f"size {space.bin_width}*{space.bin_height}.")
'a04n' with 2/16 items with area 7305688 in 3 bins of size 2750*1220.

>>> decoder = InstanceDecoder(space)
>>> import numpy as np
>>> x = np.array([ 0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, -0.1,  0.3,  0.5, -0.6, -0.7,  0.9,
...                0.0,  0.2, ])
>>> y = space.create()
>>> decoder.decode(x, y)
>>> space.validate(y)
>>> res: Instance = y[0]
>>> print(f"{res.name!r} with {res.n_different_items}/"
...       f"{res.n_items} items with area {res.total_item_area} "
...       f"in {res.lower_bound_bins} bins of "
...       f"size {res.bin_width}*{res.bin_height}.")
'a04n' with 15/16 items with area 10065000 in 3 bins of size 2750*1220.
>>> print(space.to_str(y))
a04n;15;2750;1220;1101,1098;2750,244;2750,98;1101,171;1649,171;2750,976;441,122;1649,122;2750,10;2750,1,2;2750,3;1649,1098;2750,878;2750,58;660,122

>>> x = np.array([ 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, ])
>>> y = space.create()
>>> decoder.decode(x, y)
>>> space.validate(y)
>>> res: Instance = y[0]
>>> print(f"{res.name!r} with {res.n_different_items}/"
...       f"{res.n_items} items with area {res.total_item_area} "
...       f"in {res.lower_bound_bins} bins of "
...       f"size {res.bin_width}*{res.bin_height}.")
'a04n' with 3/16 items with area 10065000 in 3 bins of size 2750*1220.
>>> print(space.to_str(y))
a04n;3;2750;1220;2750,1216,2;2750,1,13;2750,1215

>>> from math import nextafter
>>> a1 = nextafter(1.0, -10)
>>> x = np.array([ a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, ])
>>> y = space.create()
>>> decoder.decode(x, y)
>>> space.validate(y)
>>> res: Instance = y[0]
>>> print(f"{res.name!r} with {res.n_different_items}/"
...       f"{res.n_items} items with area {res.total_item_area} "
...       f"in {res.lower_bound_bins} bins of "
...       f"size {res.bin_width}*{res.bin_height}.")
'a04n' with 4/16 items with area 10065000 in 3 bins of size 2750*1220.
>>> print(space.to_str(y))
a04n;4;2750;1220;2750,1208;2750,1219;2750,1220;2750,1,13

>>> from math import nextafter
>>> a1 = nextafter(-1.0, 10)
>>> x = np.array([ a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, ])
>>> y = space.create()
>>> decoder.decode(x, y)
>>> space.validate(y)
>>> res: Instance = y[0]
>>> print(f"{res.name!r} with {res.n_different_items}/"
...       f"{res.n_items} items with area {res.total_item_area} "
...       f"in {res.lower_bound_bins} bins of "
...       f"size {res.bin_width}*{res.bin_height}.")
'a04n' with 5/16 items with area 10065000 in 3 bins of size 2750*1220.
>>> print(space.to_str(y))
a04n;5;2750;1220;2750,1220;2730,1220;2748,1220;1,1220,4;2,1220,9

>>> from math import nextafter
>>> a1 = nextafter(-1.0, 10)
>>> x = np.array([ a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, 0.3, 0.7 ])
>>> y = space.create()
>>> decoder.decode(x, y)
>>> space.validate(y)
>>> res: Instance = y[0]
>>> print(f"{res.name!r} with {res.n_different_items}/"
...       f"{res.n_items} items with area {res.total_item_area} "
...       f"in {res.lower_bound_bins} bins of "
...       f"size {res.bin_width}*{res.bin_height}.")
'a04n' with 6/16 items with area 10064146 in 3 bins of size 2750*1220.
>>> print(space.to_str(y))
a04n;6;2750;1220;2,1220,9;1,1220,3;2748,1220;1,366;2750,1220;2730,1220

>>> from math import nextafter
>>> a1 = nextafter(-1.0, 10)
>>> x = np.array([ a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, a1, a1, a1, a1, a1, a1,
...                a1, a1, 0.3, 0.7, -0.2, -0.3,
...                0.5, -0.3])
>>> y = space.create()
>>> decoder.decode(x, y)
>>> space.validate(y)
>>> res: Instance = y[0]
>>> print(f"{res.name!r} with {res.n_different_items}/"
...       f"{res.n_items} items with area {res.total_item_area} "
...       f"in {res.lower_bound_bins} bins of "
...       f"size {res.bin_width}*{res.bin_height}.")
'a04n' with 6/16 items with area 10061706 in 3 bins of size 2750*1220.
>>> print(space.to_str(y))
a04n;6;2750;1220;2,1220,7;2750,1220;2730,1220;1,1220,5;1,366;2748,1220

>>> x = np.array([ 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
...                1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
...                1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
...                1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
...                1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
...                1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
...                1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
...                1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
...                0.0, 0.0, ])
>>> y = space.create()
>>> decoder.decode(x, y)
>>> space.validate(y)
>>> res: Instance = y[0]
>>> print(f"{res.name!r} with {res.n_different_items}/"
...       f"{res.n_items} items with area {res.total_item_area} "
...       f"in {res.lower_bound_bins} bins of "
...       f"size {res.bin_width}*{res.bin_height}.")
'a04n' with 5/16 items with area 9910948 in 3 bins of size 2750*1220.
>>> print(space.to_str(y))
a04n;5;2750;1220;2698,1;2750,1,12;2750,1216;2750,1215;2750,1160

class moptipyapps.binpacking2d.instgen.inst_decoding.InstanceDecoder(space)

Bases: Encoding

Decode a string of n real values in [0,1] to an instance.

decode(x, y)

Decode the real-valued array to a 2D BPP instance.

Parameters:

• x (ndarray) – an array with values in [-1, 1]

• y (list[Instance]) – the instance receiver

Return type:

None

get_x_dim(slack=0)

Get the minimum dimension that a real vector must have.

Parameters:

slack (float | int, default: 0) – a parameter denoting the amount of slack for reducing the item size

Return type:

int

Returns:

the minimum dimension

space: Final[InstanceSpace]

the instance description

moptipyapps.binpacking2d.instgen.instance_space module

An encoding that is inspired by a given instance.

class moptipyapps.binpacking2d.instgen.instance_space.InstanceSpace(source)

Bases: Space

An space structure for the instance generation problem and space.

bin_height: Final[int]

the bin height

bin_width: Final[int]

the bin width

copy(dest, source)

Copy the instance list.

Parameters:

• dest (list[Instance]) – the destination instance list

• source (list[Instance]) – the source instance list

Return type:

None

create()

Generate a list for receiving an instance.

Return type:

list[Instance]

Returns:

the new instance list

from_str(text)

Convert an instance string to a list with an instance.

Parameters:

text (str) – the input string

Return type:

list[Instance]

Returns:

the element in the space corresponding to text

inst_name: Final[str]

the instance name

is_equal(x1, x2)

Check if the contents of two instances of the data structure are equal.

Parameters:

• x1 (list[Instance]) – the first instance

• x2 (list[Instance]) – the second instance

Return type:

bool

Returns:

True if the contents are equal, False otherwise

item_height_max: Final[int]

the maximum item height

item_height_min: Final[int]

the minimum item height

item_width_max: Final[int]

the maximum item width

item_width_min: Final[int]

the minimum item width

log_parameters_to(logger)

Log the parameters of this instance.

Parameters:

logger (KeyValueLogSection) – the logger

Return type:

None

min_bins: Final[int]

the minimum number of bins that this instance requires

n_different_items: Final[int]

the target number of unique items

n_items: Final[int]

the target number of items (including repetitions)

n_points()

Get the approximate number of different elements in the space.

Return type:

int

Returns:

the approximate scale of the space

to_str(x)

Convert an instance list to a string.

Parameters:

x (list[Instance]) – the instance list

Return type:

str

Returns:

the string representation of x

total_item_area: Final[int]

the total item area

validate(x)

Check whether a given point in the space is valid.

Parameters:

x (list[Instance]) – the point

Raises:

• TypeError – if the point x (or one of its elements, if applicable) has the wrong data type

• ValueError – if the point x is invalid and/or simply is not an element of this space

Return type:

None

moptipyapps.binpacking2d.instgen.problem module

An instance of the instance generation problem.

class moptipyapps.binpacking2d.instgen.problem.Problem(name, slack)

Bases: Component

An instance of the 2D Bin Packing Instance Generation Problem.

encoding: Final[InstanceDecoder]

the internal decoding

search_space: Final[VectorSpace]

the search space

solution_space: Final[InstanceSpace]

the instance to be used as template