# CGSHOP 2024 Benchmark Instances (V1)

Welcome to the CGSHOP 2024 Challenge!

## Introduction

This repository houses benchmark instances used in the [CGSHOP 2024 challenge](https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2024/). The instances were meticulously crafted to provide a comprehensive evaluation of optimization algorithms. In this README, we'll provide insights into the instance creation process and important considerations.

> Under very rare circumstances, we may extend the instances, after careful consideration. A reason for this could be that we overestimated the difficulty of the instances and need some additional tie-breakers. If this happens, we will announce it on the [CGSHOP 2024 challenge website](https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2024/). Again, we will only extend the benchmark if we deem it absolutely necessary.

Under `visualizations`, you can find renderings of the small and medium instances. The large instances are too large to render properly.

## Instance Generation Strategy

Our approach to instance generation involved several key steps:

1. **Generator Development:** We developed multiple instance generators and fine-tuned them through iterative manual inspection.

2. **Diverse Parameters:** Using these generators, we generated a large set of instances by varying parameters to achieve diversity.

3. **Similarity Metrics:** To assess instance diversity, we designed metrics to measure the similarity between instances.

4. **Subset Selection:** We carefully selected a subset of instances that maximize diversity according to our metrics.

## Instance Complexity

Balancing instance complexity is a challenging endeavor. We aimed to strike a balance between challenge and feasibility. Keep in mind that instance difficulty can vary based on the algorithms used. While we aimed for an exponential difficulty scale, the largest instances are intentionally designed to be exceptionally challenging without being impractical to solve.

## Important Constraints

**Integer Translations:** Please note that we only allow integer translations for items, meaning they must be placed on a grid. We have ensured that the scale of all instances should accommodate this restriction without causing overflow issues. While we aimed to keep the scale reasonably small, exercise caution when performing certain calculations.

We hope that these decisions make it more accessible for implementers who do not rely on specialized libraries like CGAL.

## Instance Format

Each instance consists of a simple convex container-polygon (`container`) and a list of simple packable polygon-items (`items`).  
It also contains some general information, such as the instance name (`instance_name`), the number of different items (`num_items`), and some additional information for internal analysis and evaluation (`meta`).

Polygons are encoded by their points in two lists for `x` and `y` coordinates.
These points are on a large integer grid and listed in a counter-clockwise orientation without a closing point.  
In addition to the list, each item in the list of `items` also has a individual `value` you can gain by packing it, and a `quantity` indicating how often you can use this item.

The following small example showcases how an instance could look like:

```json
{'instance\_name': 'test',
 'num\_items': 9,
 'container': {'x': \[26, 2, 0, 12, 91, 158, 180, 194, 225, 232, 225, 210, 200\],
  'y': \[250, 202, 149, 107, 0, 30, 42, 56, 131, 151, 177, 225, 243\]},
 'items': \[{'value': 601,
   'quantity': 1,
   'x': \[3, 40, 113, 134, 85, 143, 152, 157, 157, 92, 18, 12, 2, 0\],
   'y': \[31, 59, 59, 27, 6, 0, 51, 95, 139, 141, 77, 145, 152, 65\]},
  {'value': 90,
   'quantity': 1,
   'x': \[1, 6, 25, 54, 49, 39, 25, 31, 14, 0, 13\],
   'y': \[11, 10, 8, 0, 23, 28, 37, 56, 34, 39, 26\]},
  {'value': 1, 'quantity': 1, 'x': \[12, 0, 28\], 'y': \[16, 26, 0\]},
  {'value': 9, 'quantity': 1, 'x': \[8, 5, 0, 12, 13\], 'y': \[14, 19, 12, 0, 5\]},
  {'value': 133, 'quantity': 1, 'x': \[101, 61, 0\], 'y': \[0, 104, 95\]},
  {'value': 51, 'quantity': 2, 'x': \[68, 48, 0, 71\], 'y': \[45, 38, 17, 0\]},
  {'value': 25, 'quantity': 1, 'x': \[21, 28, 0, 1\], 'y': \[0, 47, 17, 0\]},
  {'value': 37,
   'quantity': 1,
   'x': \[11, 1, 17, 26, 19, 0, 9\],
   'y': \[16, 0, 16, 12, 34, 34, 26\]},
  {'value': 32, 'quantity': 1, 'x': \[58, 73, 79, 0\], 'y': \[5, 10, 39, 0\]}\],
 'type': 'cgshop2024\_instance'}
```

## Solution Format Specifications.

Solutions have to be submitted in a json-file containing a single dict. There's an example below, but these are the specified fields in the dict:\
`"type": "cgshop2024_solution"` mandatory.\
`"instance_name": str` has to match the `"instance name"`-field in the solved instance-json.\
`"num_included_items": int` amount of items included in the solution.\
`"item_indices": list(int)` list (length `num_included_items`) of included items by index in the instance. Range [0; `instance[num_items]`-1]\
`"x_translations": list(int)` **integer** translation into x-direction for each included item\
`"y_translations": list(int)` **integer** translation into y-direction for each included item\
optional: `"meta": dict` your processing information for your internal analysis


The translation- and index-lists are thus interpreted as follows:\
The item at item_indices[k] is translated by (x_translations[k], y_translations[k]) and then placed in the plane.\
If an item has a higher quantity and is used multiple times, add the same index multiple times at different translations.

```json
{
    "type": "cgshop2024_solution",
    "instance_name": "example_instance_a",
    "num_included_items": 3,
    "meta": {
        "approach": "something"
    },
    "item_indices": [
        0,
        0,
        2
    ],
    "x_translations": [
        0,
        1,
        0
    ],
    "y_translations": [
        1,
        1,
        0
    ]
}
```

## Conclusion

We appreciate your participation in the CGSHOP 2024 challenge. These benchmark instances are designed to push the boundaries of optimization algorithms, and your contributions are vital to advancing the field. If you encounter any issues or have questions, please feel free to reach out.

Happy optimizing!