Learning to solve the Multilevel Critical Node (MCN) Problem. Implementation of NeurIPS 2020 paper Curriculum learning for multilevel budgeted combinatorial problems .
Install the package, e.g as following
python -m pip install git+https://github.com/AdelNabli/MCN/
- numpy
- networkx
- matplotlib (only used for plotting the graphs)
- pytorch
- pytorch geometric (To use our pre-trained models, a version v1.4.x is necessary as changes in the source code of some Graph Neural Networks happened in v1.5.0)
- tensorboardX
- tqdm
- cplex (only necessary if the exact solver is used)
There are 3 main tasks supported:
- Train a neural network to produce a pool of 'expert nets' in order to solve the MCN problem on a distribution of instances
- Solve an instance of the MCN problem, either using an exact method or heuristically with the trained experts
- Evaluate the performances of the trained experts on a test set of exactly solved MCN instances
An example of how to perform each of these tasks is given in the Notebook
@inproceedings{NEURIPS2020_4eb7d41a,
author = {Nabli, Adel and Carvalho, Margarida},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {7044--7056},
publisher = {Curran Associates, Inc.},
title = {Curriculum learning for multilevel budgeted combinatorial problems},
volume = {33},
year = {2020}
}The MCN problem was introduced in A. Baggio, M. Carvalho, A. Lodi, A. Tramontani, "Multilevel Approaches for the Critical Node Problem", 2018. The exact method used here is a simple implementation of the algorithm described in this paper, with a few additions. Our implementation is based on the original code found in the following Github repository: mxmmargarida/Critical-Node-Problem