Exact Combinatorial Optimization with Graph Convolutional Neural Network

[wonsutak-ysz]

https://arxiv.org/pdf/1906.01629

@misc{gasse2019exactcombinatorialoptimizationgraph,
      title={Exact Combinatorial Optimization with Graph Convolutional Neural Networks}, 
      author={Maxime Gasse and Didier Chételat and Nicola Ferroni and Laurent Charlin and Andrea Lodi},
      year={2019},
      eprint={1906.01629},
      archivePrefix={arXiv},
      primaryClass={cs.LG},
      url={https://arxiv.org/abs/1906.01629}, 
}

[wonsutak-ysz]

Exact Combinatorial Optimization with Graph Convolutional Neural Network

Abstract

Combinatorial optimization problems are typically solved using branch-and-bound methods. This paper presents a new graph convolutional neural network model for learning branch-and-bound variable selection strategies, which utilizes the natural variable-constraint bipartite representation of mixed-integer linear programming. The model is trained through imitation learning from strong branching rules and demonstrates improved performance over previous machine learning branching methods across a range of difficult problems, while generalizing to larger instances. Additionally, it achieves the first improvement over expert-designed branching rules implemented in state-of-the-art solvers for large problems.

Main Contributions

(1) Proposes encoding branching strategies into a graph convolutional neural network (GCNN) using the natural bipartite representation of MILP problems, thereby reducing manual feature engineering.
(2) Uses cross-entropy loss to imitate strong branching decisions, which is a more challenging task than predicting strong branching scores or rankings.

Main Content

Strong branching is achieved by calculating expected bounds for each candidate variable before branching, typically producing the smallest B&B trees. The network is trained using known function families and their strong branching solutions to learn decomposition strategies for combinatorial optimization functions, ultimately aiming to quickly determine the function variable solving order. First, a training set is instantiated, and a solver is used to find expert solutions D, then our strategy is learned by minimizing cross-entropy loss.


The B&B framework is introduced, and the branching problem is modeled as a Markov decision process. The B&B process state at time t is encoded as a bipartite graph with node and edge features, as shown in Figure 2 (left), where one side consists of nodes corresponding to MILP constraints (each row in the current node's LP relaxation), and the other side consists of nodes for variables corresponding to each LP column in the MILP.

Along these graph convolutional layers, a bipartite graph with the same topology as the input but potentially different node features is obtained, with each node now containing information from its neighbors. By discarding constraint nodes and applying a final 2-layer perceptron with softmax activation on variable nodes, a probability distribution over candidate branching variables is produced, yielding the final strategy.

[wonsutak-ysz]

Experiments

Compared with three machine learning methods and SCIP's default branching rules, evaluated using solving time, number of solved instances, and B&B node count. Comparative experiments show GCNN significantly outperforms competitors in both prediction accuracy and solving time. The model generalizes well to larger instances than those used in training and performs better than SCIP's default RPB branching rule. It can serve as an additional tool to accelerate mixed-integer linear programming solvers.


Ablation Studies:

Comparing three variants: mean instead of sum convolution (MEAN), sum convolution without prenorm layers (SUM), and sum convolution with prenorm layers (GCNN), the variants performed significantly worse in solving time and node count on large instances, especially on difficult cases. This indicates that prenorm layers help stabilize training and improve generalization ability.

Conclusion

This paper describes the branch-and-bound method for solving mixed-integer linear programming as a Markov decision process. In this context, it proposes and evaluates a new approach to handling branching problems by representing the branch-and-bound process state as a bipartite graph, reducing the need for feature engineering by leveraging the variable-constraint structure of MILP problems, and allowing branching strategies to be encoded as graph convolutional neural networks. It demonstrates on four NP-hard problems that GCNN-learned strategies using a simple imitation learning scheme outperform existing machine learning branching methods and SCIP solver's default branching strategy. Most importantly, it proves that learned strategies can generalize to larger instance sizes than seen during training. Strong branching decisions can be computed for large instances due to the collection method.

[2nazero]

1. Can you give a brief summary of what MILP problem is?

(1) Proposes encoding branching strategies into a graph convolutional neural network (GCNN) using the natural bipartite representation of MILP problems, thereby reducing manual feature engineering.

Can you explain more precisely how using the natural bipartite representation of MILP problems helps GCNN automatically gets trained features?