Machine Learning for Combinatorial Optimization

Important dates (anywhere on earth time zone):

• Jul 1st '21 - competition start, release of the training datasets
• Oct 21st '21 - registration deadline, no new team is accepted past this date
• Oct 28th '21 - submission deadline, no submission is accepted past this date
• Nov 21st '21 - final result announcement and declaration of the winners
• Dec 9th '21 - virtual event at NeurIPS with poster session for all participants
• February '22 - official report with winner contributions, to be published in PMLR

Primal task - Finding feasible solutions

The primal task deals with finding good primal solutions at the root node of the branch-and-bound tree. To that end, the environment (SCIP solver) will not perform any branching but will enter an infinite loop at the root node, which will collect the agent's solutions, evaluate their feasibility, and update the overall best solution reached so far, thus lowering the current primal bound (upper bound). The metric of interest for this task is the primal integral, which takes into account the speed at which the primal bound decreases over time. To model a realistic scenario, each problem instance will have been preprocessed by SCIP (problem reduction, cutting planes etc.), and the root linear program (LP) relaxation will have been solved before the participants are asked to produce feasible solutions. To prevent SCIP from searching for primal solutions by itself, all primal heuristics will be deactivated. In order to compute this metric unambiguously, even when no solution has been found yet, we provide an initial primal bound (trivial solution value) for each instance, which is to be given to SCIP at the beginning of the solving process in the form of a user objective limit.

Environment

The solver is stopped at the root node after the root LP has been solved and enters an infinite loop. At each transition, the environment evaluates the given solution candidate and updates the primal bound. Nothing else happens. The solver remains in the SOLVING stage until the episode terminates (time limit reached, or when the problem is solved).

Action

A solution candidate for the current problem (variable assignment values, x).

Metric

Primal integral.

Time limit

\(T=5\) minutes.

Relevant literature:

• Learning Combinatorial Optimization Algorithms over Graphs , Dai et al., NeurIPS'17
• Reinforcement Learning for Solving the Vehicle Routing Problem , Nazari et al., NeurIPS'18
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search , Li et al., NeurIPS'18
• Solving Mixed Integer Programs Using Neural Networks , Nair et al., 2020

Dual task - Branching

The dual task deals with obtaining tight optimality guarantees (dual bounds) via branching. Making good branching decisions is regarded as a critical component of modern branch-and-bound solvers, yet has received little theoretical understanding to this day (see Lodi et al., 2017). In this task, the environment will run a full-fledged branch-and-cut algorithm with SCIP, and the participants will only control the solver's branching decisions. The metric of interest is the dual integral, which considers the speed at which the dual bound increases over time. Also, all primal heuristics will be deactivated, so that the focus is only on proving optimality via branching.

Environment

Traditional branch-and-bound algorithm. The solver stops after each node is processed (LP solved), receives a branching decision, performs branching, and selects the next open node to process. The solver remains in the SOLVING stage until the episode terminates (time limit reached, or when the problem is solved).

Action

One of the current node's branching candidates (non-fixed integer variables). Only single-variable branching is allowed.

Metric

Dual integral.

Time limit

\(T=15\) minutes.

Relevant literature:

• Learning to Branch in Mixed Integer Programming , Khalil et al., AAAI'16
• On Learning and Branching: a Survey , Lodi et al., TOP, 2017
• Learning to Branch , Balcan et al., ICML'18
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks , Gasse et al., NeurIPS'19
• Hybrid Models for Learning to Branch , Gupta et al., NeurIPS'20
• Solving Mixed Integer Programs Using Neural Networks , Nair et al., 2020

Configuration task - Choosing solver parameters

The configuration task deals with deciding on a good parameterization of the solver for a given problem instance. The environment required for this task is more straightforward than for the two previous ones since it involves only a single decision for the agents (i.e., contextual bandit problem). Participants are allowed to tune any of the existing parameters of SCIP (except parameters regarding the computation of time). They can choose between providing a fixed set of parameters that work well on average for each problem benchmark or producing instance-specific parameterizations based on each instance's characteristics. The metric of interest for this task is the primal-dual gap integral, which combines both improvements from the dual and from the primal side over time. In order to compute this metric unambiguously, even when no primal or dual bound exists, we provide both an initial primal bound (trivial solution value) and an initial dual bound (pre-computed root LP solution value) for each instance.

Environment

The solver loads a problem instance and immediately stops. It then receives a parameterization, applies it, and pursues with the solving process until it terminates (time limit reached, or when the problem is solved). During the first and only transition, the solver is in the PROBLEM stage. As such, participants will not be able to extract advanced features from the solver, such as those relying on the LP being solved.

Action

A set of SCIP parameters, in the form of a key/value dictionary.

Metric

Primal-dual gap integral.

Time limit

\(T=15\) minutes.

Relevant literature

• Sequential model-based optimization for general algorithm configuration , Hutter et al., LION'11

Each of the three challenges, the primal task, the dual task and the configuration task, is associated with a specific evaluation metric that reflects a different objective. Here we describe how each metric is computed over a single problem instance, while the final goal of the participants is to optimize this metric in expectation over a hidden collection of test instances.

Because our evaluation metrics are time-dependent, all evaluations will be run on the same hardware setup, including one CPU core and one GPU card, which will be communicated at the start of the competition. For practical reasons, for each task, a maximum time budget \(T\) is given to process each test instance (5, 15 and 15 minutes respectively for the primal, dual and configuration tasks), after which the environment necessarily terminates. Participants should therefore focus on taking both good and fast decisions.

In the following we consider instances of mixed-integer linear programs (MILPs) expressed as follows: \[ \begin{eqnarray} \underset{\mathbf{x}}{\operatorname{arg\,min}} \quad \mathbf{c}^\top\mathbf{x} && \\ \text{subject to} \quad \mathbf{A}^\top\mathbf{x} & \leq & \mathbf{b} \text{,} \\ \mathbf{x} & \in & \mathbb{Z}^p \times \mathbb{R}^{n-p} \text{,} \end{eqnarray} \] where \(\mathbf{c} \in \mathbb{R}^n\) denotes the coefficients of the linear objective, \(\mathbf{A} \in \mathbb{R}^{m \times n}\) and \(\mathbf{b} \in \mathbb{R}^m\) respectively denote the coefficients and upper bounds of the linear constraints, while \(n\) is the total number of variables, \(p \leq n\) is the number of integer-constrained variables, and \(m\) the number of linear constraints.

For each individual challenge, participants will be evaluated on three problem benchmarks from diverse application areas. Participants can provide a different decision-making code (algorithmic solution or trained ML model) for each of the benchmarks, or a single code that works for all benchmarks.

A problem benchmark consists in a collection of mixed-integer linear program (MILP) instances in the standard MPS file format. Each benchmark is split into a training and a test set, originating from the same problem distribution. While the training instances are made public at the beginning of the competition for participants to train their models, the test instances will be kept hidden for evaluation purposes and will only be revealed at the end of the competition.

Note: for each problem benchmark we suggest a pre-established split of the training instances into two distinct collections: train and valid. This is only a suggestion, and all instance files in both those collections can be likely considered as training instances. There is no restriction regarding how participants should use the provided instances during training.

The first two problem benchmarks are inspired by real-life applications of large-scale systems at Google, while the third benchmark is an anonymous problem inspired by a real-world, large-scale industrial application.

Problem benchmark 1: Balanced Item Placement

This problem deals with spreading items (e.g., files or processes) across containers (e.g., disks or machines) utilizing them evenly. Items can have multiple copies, but at most, one copy can be placed in a single bin. The number of items that can be moved is constrained, modeling the real-life situation of a live system for which some placement already exists. Each problem instance is modeled as a MILP, using a multi-dimensional multi-knapsack formulation. This dataset contains 10000 training instances (pre-split into 9900 train and 100 valid instances).

Problem benchmark 2: Workload Apportionment

This problem deals with apportioning workloads (e.g., data streams) across as few workers (e.g., servers) as possible. The apportionment is required to be robust to any one worker's failure. Each instance problem is modeled as a MILP, using a bin-packing with apportionment formulation. This dataset contains 10000 training instances (pre-split into 9900 train and 100 valid instances).

Problem benchmark 3: Anonymous Problem

The MILP instances corresponding to this benchmark are assembled from a public dataset, whose origin is kept secret to prevent cheating. Reverse-engineering for the purpose of recovering the test set is explicitly forbidden (see rules). This dataset contains 118 training instances (pre-split into 98 train and 20 valid instances).

The spirit of the competition is as follows:

• we encourage contributions from both the OR and ML communities by explicitly allowing non-ML submissions;
• we encourage student participation with a dedicated student leaderboard;
• we encourage original contributions by specifically making the use of highly-engineered commercial solvers prohibited.

Participants must adhere to the following rules:

Eligibility

1. Participants can work in teams.
2. Participants can submit codes based on a machine learning model, a human-designed algorithm, or any combination of the two.
3. Participants are not allowed to use commercial software in their code. The use of solvers such as CPLEX, Gurobi, or FICO XPress is explicitly forbidden.
4. Student-only teams are eligible to a separate student leaderboard, in addition to the main leaderboard of the competition. A graduated PhD is not considered a student.

Data

1. The use of supplementary existing open-source datasets, e.g., for pre-training, is permitted provided they are credited.
2. The use of private, proprietary datasets is not permitted.
3. In order to prevent cheating, the evaluation data sets will be kept hidden to the participants during the competition.
4. Participants are free and encouraged to extract original features from the solver for training and evaluation, though the Python interface of SCIP, PySCIPOpt.

Submission

1. The submitted codes must be written in Python, and must run in the evaluation environment which we provide.
2. Parallel implementations using multiple processes or multiple threads are allowed, although the hardware on which the codes will be evaluated is single-core.
3. The evaluation environment does not have access to any external network, to prevent any information leak.
4. Users may make use of open source libraries given proper attribution. At the end of the competition, we encourage all code to be open-sourced so the results can be reproduced.
5. The evaluation environment will provide a basic ML ecosystem (Tensorflow, Pytorch, Scikit-learn). Additional libraries will be added to the evaluation environment upon reasonable requests.
6. At the end of the competition, the winners are expected to provide a description of the method they used.

Cheating prevention

1. Participants are forbidden to interact with the SCIP solver in any other way than the one intended, that is, extracting information or providing a control decision related to the task at hand. Any interaction with SCIP that results in changes of the solver's internal state will be considered cheating.
2. Some datasets have been anonymized, as they rely on publicly accessible data. Any attempt at reverse-engineering for the purpose of recovering information about the test set is forbidden.
3. Any instance of cheating, defined as violation of the rules above or any other attempt to circumvent the spirit and intent of the competition, as determined by the organizers, will result in the invalidation of all of the offending team’s submissions and a disqualification from the competition.

For each task, the winners will be declared as follows:

Ranking rules

• Each team will be evaluated separately on each of the three benchmark datasets according the task's metric, i.e., primal integral, dual integral, or primal-dual integral. This metric will be averaged across all instances in the test dataset, resulting in an individual ranking for each dataset. For example, for the primal task, team A might obtain ranks 3, 8, 1 respectively in the three problem benchmark, while team B obtains ranks 2, 2, 15.
• Then, for each team those three ranks will be multiplied together to obtain the overall score of the team. For example, team A will obtain a score of 3x8x1=24 while team B obtains 2x2x15=60.
• The team with the lowest overall score wins.

Registration form: register your team and subscribe to the competition's mailing list.

GitHub repository: get started and access the datasets, starter packages, and technical documentation.

Those are the final results of the competition !

• Detailed evaluation results per instance for each team
• Hidden evaluation instances (test set)
  Note: the partial evaluations were using the first 20 instances (10000 to 10019) x 1 random seed for the item_placement and load_balancing benchmarks, and the first 4 instances (119 to 122) x 5 random seeds for the anonymous benchmark.

Note: for each challenge and each benchmark, we report two performance measures:

• the average evaluation metric (primal integral, dual integral, or primal-dual integral) obtained over the test instances, which is to be minimized. This measure is described in detail in the metrics section, and corresponds to the negated cumulated reward computed by our evaluation script, plus a constant term (\(T\mathbf{c}^\top\mathbf{x}^\star\), \(-T\mathbf{c}^\top\mathbf{x}^\star\) or \(0\)) that depends on the optimal solution value of each instance. Because for some instances it is hard to obtain the optimal solution value, and because this constant term is the same for every participant and does not impact the rankings, we compute an adequate estimate to substitute \(\mathbf{c}^\top\mathbf{x}^\star\) when the optimal solution value is not available, based on the best primal and dual bounds obtained after some time limit.
• the average cumulated reward (cum. reward) obtained over the test instances, which is to be maximized. We report this measure for information purposes, as it is exactly the one computed by our evaluation script. This measure can be interpreted as the negated and unshifted version of the evaluation metric (it does not depend on \(\mathbf{c}^\top\mathbf{x}^\star\)), and it produces the exact same ranking.

Main paper (with winner contributions)

(Please cite this when refering to the competition)

The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights
Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M. Kazachkov, Elias Khalil, Pawel Lichocki, Andrea Lodi, Miles Lubin, Chris J. Maddison, Morris Christopher, Dimitri J. Papageorgiou, Augustin Parjadis, Sebastian Pokutta, Antoine Prouvost, Lara Scavuzzo, Giulia Zarpellon, Linxin Yang, Sha Lai, Akang Wang, Xiaodong Luo, Xiang Zhou, Haohan Huang, Shengcheng Shao, Yuanming Zhu, Dong Zhang, Tao Quan, Zixuan Cao, Yang Xu, Zhewei Huang, Shuchang Zhou, Chen Binbin, He Minggui, Hao Hao, Zhang Zhiyu, An Zhiwu, Mao Kun
Proceedings of the NeurIPS 2021 Competitions and Demonstrations Track, PMLR 176:220-231, 2022.

Contributed papers

• Confidence Threshold Neural Diving by Taehyun Yoon.
• Efficient Primal Heuristics for Mixed-Integer Linear Programs by Akang Wang, Linxin Yang, Sha Lai, Xiaodong Luo, Xiang Zhou, Haohan Huang, Shengcheng Shao, Yuanming Zhu, Dong Zhang, Tao Quan.
• Instance-wise algorithm configuration with graph neural networks by Romeo Valentin, Claudio Ferrari, Jérémy Scheurer, Andisheh Amrollahi, Chris Wendler, Max B. Paulus.
• MDO’s Method for NeurIPS 2021 ML4CO’s Configuration Task by Mengyuan Zhang.
• ML4CO: Is GCNN All You Need? Graph Convolutional Neural Networks Produce Strong Baselines For Combinatorial Optimization Problems, If Tuned and Trained Properly, on Appropriate Data by Amin Banitalebi-Dehkordi, Yong Zhang.
• ML4CO submission EFPP by Edward Lam, Frits de Nijs, Pierre Le Bodic, Peter J. Stuckey.
• ML4CO-KIDA: Knowledge Inheritance in Dataset Aggregation by Zixuan Cao, Yang Xu, Zhewei Huang, Shuchang Zhou.
• Strong Regularization is All You Need: Toward ML4CO Challenge by Seungjoon Park, Minu Kim, Minchan Jeong, Yejin Cho, Mingyu Kim.
• YORDLE: An Efficient Imitation Learning for Branch and Bound by Qingyu Qu, Xijun Li, Yunfan Zhou.

List of participants

Primal task

• CUHKSZ_ATD
  • Xiaodong Luo, Shenzhen Research Institute of Big Data
  • Akang Wang, Shenzhen Research Institute of Big Data
  • Zhang Dong, Huawei GTS
  • Sha Lai, Shenzhen Research Institute of Big Data
  • Tao Quan, Huawei GTS
  • Shengcheng Shao, Huawei GTS
  • Xiang Zhou, Huawei GTS
  • Yuanming Zhu, Huawei GTS
  • Linxin Yang, Shenzhen Research Institute of Big Data
  • Haohan Huang, Huawei GTS
• dt
  • Ding Tong, Huawei Technologies Co., Ltd.
  • Zhang Zhiyu, Huawei Technologies Co., Ltd.
• EasyML
  • Zhendong Zhang, Xidian University
• EI-OROAS
  • Wang pan, Huawei Cloud Computing Technologies Co., Ltd.
  • Chen Zihan, Huawei Cloud Computing Technologies Co., Ltd.
  • Zhang Zhiyu, Huawei Cloud Computing Technologies Co., Ltd.
  • He Minggui, Huawei Cloud Computing Technologies Co., Ltd.
  • Hou Zongfu, University of Chinese Academy of Sciences
  • Chen Binbin, TsingHua University
• ethz-scuba
  • Daniel Paleka, ETH Zurich
  • Carla Rieger, ETH Zurich
  • Max Paulus, ETH Zurich
• generaleyes
  • Kushal Tirumala, Caltech
  • Anirudh Rangaswamy, Caltech
  • Jialin Song, Caltech
• MDO
  • Mou Sun, Alibaba DAMO Academy
  • Lei Zhou, Tongji University
  • Jialin Liu, Alibaba DAMO Academy
• MILPandCookies
  • Natalia Summerville, SAS Institute
  • Rob Pratt, SAS
  • Matt Galati, SAS
  • Jorge Silva, SAS
  • Laci Ladanyi, SAS
  • Phillip Christophel, SAS
• MixedInspiringLamePuns
  • Carla Rieger, ETH Zurich
  • Federico Gossi, ETH Zurich
  • Max B. Paulus, ETH Zurich
• Mr_Tree
  • Jianshu Li, Huawei Co.
• nf-lzg
  • Fei Ni, Tianjin University
  • Zhigang Li, Tianjin University
• Nuri
  • Zixuan Cao, Peking University
  • Yang Xu, Peking University
  • Zhewei Huang, Megvii
  • Shuchang Zhou, Megvii
• UNIST-LIM-Lab
  • Taehyun Yoon, Ulsan National Institute of Science and Techonology

Dual task

• ark
  • Ark Zhu, Soochow University
• blueterrier
  • Pooja Pandey, 1QB Information Technologies, Inc
  • Kyle Mills, 1QB Information Technologies, Inc
• Columbia_Combinators
  • Wentao Zhao, Columbia University
  • Abhi Gupta, Columbia University
  • Yunhao Tang, Columbia University
  • Sian Lee, Columbia University
  • Amey Pasarkar, Columbia University
  • Luocen Wang, Columbia University
• comeon
  • Jingbo Sun, Beijing Institute of Technology
  • Zhiqiang He, Northeastern University
• CUHKSZ_ATD
  • Xiaodong Luo, Shenzhen Research Institute of Big Data
  • Akang Wang, Shenzhen Research Institute of Big Data
  • Linxin Yang, Shenzhen Research Institute of Big Data
  • Sha Lai, Shenzhen Research Institute of Big Data
  • Zhang Dong (张栋), Huawei GTS
  • Quan Tao (权涛)
  • Chen Juan (陈娟)
  • Shao Shengcheng (邵晟程), Huawei GTS
  • Xiang Zhou (周祥), Huawei GTS
  • Huang Hiroshi (黄浩瀚)
  • Wang Haomao (王浩茂)
  • Zhu Yuanming (朱元明), Huawei GTS
• DaShun
  • Zhi Wang, Ant Group
• EasyML
  • Zhendong Zhang, Xidian University
• EI-OROAS
  • Amin Banitalebi-Dehkordi, Huawei Technologies Canada Co., Ltd.
  • Yusi Ye, Huawei Technologies
  • Tianyu Zhang, Huawei Technologies Canada Co., Ltd.
  • Zirui Zhou, Huawei Technologies Canada Co., Ltd.
  • Yong Zhang, Huawei Technologies Canada Co., Ltd.
• gentlemenML4CO
  • Wenqing Zheng, UT Austin
  • Haoyu Wang, Purdue
  • Peihao Wang, UT Austin
  • Tianlong Chen, UT Austin
  • Xiaohan Chen, UT Austin
  • Zhangyang Wang, UT Austin
  • Pan Li, Purdue
• KAIST_OSI
  • Seungjoon Park, KAIST
  • Mingyu Kim, KAIST
  • Minchan Jeong, KAIST
  • Minu Kim, KAIST
  • Yejin Cho, KAIST
• KEP-UNIST
  • Jinwon Choi, Kakaoenterprise
  • Hyunho Lee, Kakaoenterprise
  • Kyushik Min, Kakaoenterprise
  • Minsub Lee, UNIST
  • Keehun Park, UNIST
  • Hanbum Ko, UNIST
• lxj24
  • Xijun Li, University of Science and Technology of China
• Monkey
  • Jingbo Sun
  • Zhiqiang He
  • Xiaomin Yuan
• nf-lzg
  • Fei Ni, Tianjin University
  • Zhigang Li, Tianjin University
• null_
  • Jiaxuan He, Tsinghua University
• Nuri
  • Zixuan Cao, Peking University
  • Yang Xu, Peking University
  • Zhewei Huang, Megvii
  • Shuchang Zhou, Megvii
• qqy
  • Qingyu Qu, Beihang University
• shg
  • Rang Jun, GuiZhou University
• Superfly
  • Yafei Zhang
• sylvia
• THUML-RL
  • Jincheng Zhong, Tsinghua University
  • Jialong Wu, Tsinghua University
  • Haoyu Ma, Tsinghua University
• uofx
• wanghaha
  • Wang Haha

Configuration task

• Cho
  • Hyunsoo Cho, Pusan National University
• DaShun
  • Zhi Wang, Ant Group
  • Qi Zhang, Ant Group
• EasyML
  • Zhendong Zhang, Xidian University
• ECNUNoah001
  • Hao Hao, East China Normal University
• EFPP
  • Edward Lam, Monash University
  • Frits de Nijs, Monash University
  • Pierre Le Bodic, Monash University
  • Peter Stuckey, Monash University
• EI-OROAS
  • Chen Binbin, TsingHua University
  • He Minggui, Huawei Cloud Computing Technologies Co., Ltd.
  • Hao Hao, Huawei Noah's ark lab
  • Zhang Zhiyu, Huawei Cloud Computing Technologies Co., Ltd.
  • An Zhiwu, Huawei Cloud Computing Technologies Co., Ltd.
  • Mao Kun, Huawei Cloud Computing Technologies Co., Ltd.
• KAIST_OSI
  • Seungjoon Park, KAIST
  • Mingyu Kim, KAIST
  • Minchan Jeong, KAIST
  • Minu Kim, KAIST
  • Yejin Cho, KAIST
• KEP-UNIST
  • Jinwon Choi, Kakaoenterprise
  • Hyunho Lee, Kakaoenterprise
  • Kyushik Min, Kakaoenterprise
  • Minsub Lee, UNIST
  • Keehun Park, UNIST
  • Hanbum Ko, UNIST
• MDO
  • Mengyuan Zhang, Alibaba DAMO Academy
• MixedInspiringLamePuns
  • Romeo Valentin, ETH Zurich
  • Claudio Ferrari, ETH Zurich
  • Jeremy Scheuer, ETH Zurich
  • Andisheh Amrollahi, ETH Zurich
  • Chris Wendler, ETH Zurich
  • Max B. Paulus, ETH Zurich
• MOEA
  • Wang Shuai, East China Normal University
• nf-lzg
  • Fei Ni, Tianjin University
  • Zhigang Li, Tianjin University
• null_
  • Jiaxuan He, Tsinghua University
• Nuri
  • Zixuan Cao, Peking University
  • Yang Xu, Peking University
  • Zhewei Huang, Megvii
  • Shuchang Zhou, Megvii
• shg
  • Rang Jun, GuiZhou University
• THUML-RL
  • Jincheng Zhong, Tsinghua University
  • Jialong Wu, Tsinghua University
  • Haoyu Ma, Tsinghua University