DATA.md

Data description

Training datasets

The public instances can been downloaded here, and are to placed inside the instances folder. The folder structure after the datasets are set up looks as follows

instances/
  1_item_placement/
    train/           -> 9900 instances
    valid/           -> 100 instances
  2_load_balancing/
    train/           -> 9900 instances
    valid/           -> 100 instances
  3_anonymous/
    train/           -> 98 instances
    valid/           -> 20 instances

Important note: for each benchmark we propose a pre-defined split of the public instances into a training set (train) and a validation set (valid). Participants do not have to respect this arbitrary choice, and are free to use all the provided instances in whichever way they like without any restriction. All the instances included in train and valid can be considered training instances.

Test datasets

The test instances used to evaluate the submissions will be kept hidden until the end of the competition.

instances/
  1_item_placement/
    test/           -> 100 instances
  2_load_balancing/
    test/           -> 100 instances
  3_anonymous/
    test/           -> 20 instances

File formats

Each problem instance is composed of two files which follows the same naming pattern, for instance,

item_placement_147.mps.gz  -> the MILP instance file in compressed MPS format
item_placement_147.json    -> a JSON file with pre-computed information about the instance

In the JSON files we store a pre-computed initial primal bound and initial dual bound for each instance, which are used in the computation of our evaluation metrics. The JSON content look as follows:

{"dual_bound": 4.063450550000058, "primal_bound": 671.5409895199994}

Those initial bounds were obtained as follows:

• primal bound: the value of the first feasible solution found by the SCIP solver
• dual bound: the value of the first LP relaxation solved by the SCIP solver

Problem benchmarks

Here we give a short description of each problem benchmark. In particular, we describe how each problem instance is modeled as a Mixed-Integer Linear Program (MILP).

Benchmark 1: Balanced Item Placement

There are items, bins, and resource types. Each item has a fixed resource requirement, for each resource type . Each bin has a fixed capacity, for each resource type . The goal is to place all items in bins, while minimizing the imbalance of the resources used across all bins.

Constants

the amount of resource available in bin .

the amount of resource required by item .

Decision variables

place_$i_$b: a binary variable indicating whether to place item in bin .

Implicit decision variables

deficit_$b_$r: a continuous variable between 0 and 1 tracking the normalized imbalance of resource in bin .

max_deficit_$r: a continuous variable between 0 and 1 tracking the max normalized imbalance of resource across all bins.

Constraints

copies_ct_$i: all items must be placed once.

supply_ct_$b_$r: bin capacities must be respected.

deficit_ct_$b_$r: normalized imbalance of resources is tracked for each bin and resource.

max_deficit_ct_$r: max normalized imbalance of resources across all bins is tracked for each resource.

Objective

Minimize the imbalance of resources used across all bins.

Benchmark 2: Workload Apportionment

There are workers and workloads. Each worker has a fixed capacity and activation cost. Each workload has a fixed amount of work required and a set of allowed workers. The goal is to minimize the total cost for processing all workloads, under the constraint that any one worker is allowed to fail (robust apportionment).

Constants

the capacity of worker .

the activation cost of worker .

the amount of work required to process workload .

the set of workers allowed to process workload .

Decision variables

reserved_capacity_$i_$j: a non-negative continuous variable indicating the amount of work reserved on worker for workload .

worker_used_$i: a binary variable indicating whether worker must be activated.

Constraints

(encoded as variable upper bound for reserved_capacity_$i_$j): only allowed workers can process workloads.

worker_capacity_ct_$i: worker capacity must be respected.

worker_used_ct_$i_$j: activation indicator is tracked for each worker.

workload_ct_$j_failure_$i: there must be sufficient capacity for each workload in the scenario where any one of the workers is unavailable.

Objective

Minimize the total cost for processing all workloads.

Benchmark 3: Anonymous Problem

The third problem benchmark is anonymous, and thus we do not provide a description of the problem instances.