Item Placement

Item Placement (IP), called Balanced Item Placement in the ML4CO competition [Gasse22], involves spreading items, e.g., files or processes, across containers, e.g., disks or machines, so that the containers are utilized evenly. Each item has a fixed, multi-dimensional resource requirement, and each container has a fixed capacity in every dimension. Every item must be placed in exactly one container. The objective penalizes, in every resource dimension, how far each container's load falls below the average load, with an extra penalty on the worst such shortfall. The problem is a multi-dimensional multiple-knapsack problem; it was inspired by large-scale systems at Google, and the instances were released for the ML4CO competition (the generator was released after the competition: knapsack/knapsack.py in the ML4CO-hidden repository). In the competition description the number of items that can be moved from an existing placement is also limited, but neither the generator nor the released instances contain such a constraint. The generator can require several copies of an item; the instances use a single copy of every item.

Notation

• \(I\): set of items (\(|I| = 105\)); \(J\): set of containers (\(|J| = 10\)); \(K\): set of resource dimensions (\(|K| = 3\)).
• \(a_{ik} \geq 0\): requirement of item \(i\) in dimension \(k\). The generator draws 100 small items with \(a_{ik} \sim U[0, 0.1]\) and 5 large items with \(a_{ik} \sim U[0.9, 1]\), independently in every dimension.
• \(T_k = \frac{1}{|J|}\sum_{i \in I} a_{ik}\): average (target) load per container in dimension \(k\).
• \(b_k = 2\,T_k\): capacity of every container in dimension \(k\) (the same for all containers).
• \(d_{ik} = a_{ik} / T_k\): requirement of item \(i\) normalized by the target load.
• \(\alpha_k = 1\), \(\beta_k = 10\,|J|\,|K| = 300\): objective weights of the per-container deficits and of the maximum deficit (the generator weights the maximum deficit so that it always dominates).
• \(x_{ij} \in \{0,1\}\): 1 if item \(i\) is placed in container \(j\).
• \(y_{jk} \in [0,1]\): deficit of container \(j\) in dimension \(k\), i.e. the shortfall of its load below the target, as a fraction of \(T_k\).
• \(z_k \in [0,1]\): largest deficit over all containers in dimension \(k\).

MILP formulation [Gasse22]

\begin{align} \min_{x,y,z} \quad & \sum_{j \in J}\sum_{k \in K} \alpha_k\, y_{jk} + \sum_{k \in K} \beta_k\, z_k \\ \text{s.t.} \quad & \sum_{j \in J} x_{ij} = 1 && \forall i \in I \quad \text{(each item placed once)} \\ & \sum_{i \in I} a_{ik}\, x_{ij} \leq b_k && \forall j \in J,\ \forall k \in K \quad \text{(capacity)} \\ & \sum_{i \in I} d_{ik}\, x_{ij} + y_{jk} \geq 1 && \forall j \in J,\ \forall k \in K \quad \text{(deficit)} \\ & y_{jk} \leq z_k && \forall j \in J,\ \forall k \in K \quad \text{(maximum deficit)} \\ & x_{ij} \in \{0,1\} && \forall i \in I,\ \forall j \in J \\ & 0 \leq y_{jk} \leq 1 && \forall j \in J,\ \forall k \in K \\ & 0 \leq z_k \leq 1 && \forall k \in K \end{align}

The deficit constraint says \(y_{jk} \geq 1 - \frac{1}{T_k}\sum_{i} a_{ik} x_{ij}\), so at the optimum \(y_{jk}\) is the relative shortfall of container \(j\)'s load below the average load in dimension \(k\) (zero if the container is at or above average), and \(z_k\) is the largest shortfall in dimension \(k\). An instance has \(|I||J| = 1050\) binary variables, \(|J||K| + |K| = 33\) continuous variables, and \(|I| + 3|J||K| = 195\) constraints.

Generator settings. The instances were generated with the parameter file knapsack/params.text_pb2 of the ML4CO-hidden repository (confirmed on the instances): 10 containers, 3 resource dimensions, 100 small and 5 large items with one copy each, and container capacities equal to \(f = 2\) times the average load in every dimension.

@misc{huang2024distributional,
      title={Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods}, 
      author={Weimin Huang and Taoan Huang and Aaron M Ferber and Bistra Dilkina},
      year={2024},
      eprint={2406.06954},
      archivePrefix={arXiv},
      primaryClass={cs.LG}
}

@inproceedings{gasse2022machine,
  title={The machine learning for combinatorial optimization competition (ml4co): Results and insights},
  author={Gasse, Maxime and Bowly, Simon and Cappart, Quentin and Charfreitag, Jonas and Charlin, Laurent and Ch{\'e}telat, Didier and Chmiela, Antonia and Dumouchelle, Justin and Gleixner, Ambros and Kazachkov, Aleksandr M and others},
  booktitle={NeurIPS 2021 competitions and demonstrations track},
  pages={220--231},
  year={2022},
  organization={PMLR}
}
}