Load Balancing

The Load Balancing (LB) problem, called Workload Apportionment in the ML4CO competition [Gasse22], apportions the workloads of a set of tasks (e.g., data streams) across as few machines (workers, e.g., servers) as possible. Each task can only use a subset of the machines, each machine has a limited capacity, and the apportionment must be robust to the failure of any single machine: for every task, the machines other than any one of its accessible machines must still be able to carry the task's full workload. The problem is a bin-packing problem with an apportionment formulation; 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: load_balancing/load_balancing.py in the ML4CO-hidden repository).

Notation

• \(M\): set of tasks (\(|M| = 60\)); \(N\): set of machines (\(|N| = 1000\)).
• \(N^i \subseteq N\): machines accessible to task \(i\).
• \(a_i\): workload of task \(i\).
• \(b_j\): capacity of machine \(j\).
• \(M_{ij} = \max(a_i, b_j)\): big-M constant of the linking constraint. With the parameters below every workload exceeds every capacity, so \(M_{ij} = a_i\) in all instances.
• \(y_j \in \{0,1\}\): 1 if machine \(j\) is used.
• \(x_{ij} \geq 0\): amount of capacity of machine \(j\) reserved for task \(i\). The instances contain \(x_{ij}\) for every pair \((i,j)\); for \(j \notin N^i\) its upper bound is 0.

MILP formulation [Gasse22]

\begin{align} \min_{x,y} \quad & \sum_{j \in N} y_j \\ \text{s.t.} \quad & x_{ij} \leq M_{ij}\, y_j && \forall i \in M,\ \forall j \in N \quad \text{(only used machines carry load)} \\ & \sum_{i \in M} x_{ij} \leq b_j && \forall j \in N \quad \text{(machine capacity)} \\ & \sum_{j \in N^i \setminus \{j'\}} x_{ij} \geq a_i && \forall i \in M,\ \forall j' \in N^i \quad \text{(robustness to failure of } j'\text{)} \\ & 0 \leq x_{ij} \leq b_j && \forall i \in M,\ \forall j \in N^i \\ & x_{ij} = 0 && \forall i \in M,\ \forall j \in N \setminus N^i \\ & y_j \in \{0,1\} && \forall j \in N \end{align}

An instance has \(|N|\) binary variables, \(|M||N|\) continuous variables, and \(|M||N| + |N| + \sum_{i \in M} |N^i|\) constraints.

Generator settings. The instances were generated with the parameter file load_balancing/params.text_pb2 of the ML4CO-hidden repository (confirmed on the instances):

• Machines: 500 of class 1 with capacity \(b_j \sim U[0.3, 0.5]\) and 500 of class 2 with \(b_j \sim U[0.1, 0.3]\); every machine has cost 1.
• Tasks: 50 of class 1 with workload \(a_i \sim U[1, 5]\) and 10 of class 2 with \(a_i \sim U[5, 10]\).
• Accessibility: each machine is accessible to a class-1 task independently with probability 0.1 (class-1 machines) or 0.01 (class-2 machines), and to a class-2 task with probability 0.01 or 0.1, so \(|N^i|\) is 55 in expectation (41 to 71 in the instances checked).

@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}
}
}