Bipartite Graph Neural Networks for Mathematical Programming Solvers

This direction is merged into another direction: bipartite graph representation. Its last version stays readable and citable here.

Version 1 of 113 papers15 conceptsfrozen 2026-10-04

Traditional mathematical programming solvers like Gurobi or SCIP rely on hand-crafted heuristics to navigate the search space of NP-hard problems. While effective, these heuristics often fail to exploit the specific structure of a problem instance. A recent surge in research, pioneered by Maxime Gasse, Andrea Lodi, and others, suggests that we can replace these heuristics with learned policies. The key to making this work is representing optimization problems as bipartite graphs.

The Challenge of Arbitrary Ordering

In a standard Linear Program (LP) or Mixed-Integer Linear Program (MILP), the problem is defined by a constraint matrix $A$, a cost vector $c$, and a right-hand side $b$. If you were to feed these matrices directly into a standard neural network, you would run into a fundamental issue: the ordering of variables (columns) and constraints (rows) is arbitrary.

If a solver swaps the first and second constraints, the underlying mathematical problem remains identical, but the input matrix looks completely different to a typical neural network. To learn effectively, a model must be permutation invariant—it must produce the same decision regardless of how the rows and columns are indexed.

The Bipartite Graph Solution

To achieve this invariance, researchers like Jialin Liu and Wotao Yin have converged on a specific structural representation: the bipartite graph.

In this framework, an optimization problem is mapped to a graph with two distinct sets of nodes:

  1. Variable Nodes: Representing each decision variable $x_j$.
  2. Constraint Nodes: Representing each constraint $i$.

An edge exists between a variable node and a constraint node if and only if that variable has a non-zero coefficient in that constraint. The edge weight is the coefficient $A_{ij}$ itself. As noted in A Survey for Solving Mixed Integer Programming via Machine Learning, this encoding captures the entire structure of the problem while ensuring that the learned features remain invariant to the specific ordering of variables or constraints.

Why It Works: Structural Generalization

By using Graph Convolutional Neural Networks (GCNNs) on this bipartite structure, models can learn the "shape" of a problem. This leads to a critical advantage: generalization.

Maxime Gasse and colleagues demonstrated in Exact Combinatorial Optimization with Graph Convolutional Neural Networks that a model trained on small, easy-to-solve instances can effectively generalize to much larger, unseen problem instances. Because the GNN operates on local neighborhoods of variables and constraints, it learns patterns of interaction that are independent of the total problem size.

Applications Across the Solver Pipeline

This bipartite GNN approach has been successfully applied to almost every critical decision point within a solver:

  • Branching: In the branch-and-bound tree, the solver must choose which variable to split on. Gasse et al. showed that GNNs can mimic "Strong Branching"—a highly accurate but computationally expensive rule—at a fraction of the time.
  • Pivoting: For the simplex method, Shanwen Pu and Yinyu Ye developed "Pivot Experts" in Learning to Pivot as a Smart Expert, using GNNs to predict the best entering variable to find shorter paths to the optimum.
  • Cutting Planes: Solvers use "cuts" to tighten the search space. Sammy Khalife and Andrea Lodi have explored the theoretical complexity of learning to cut, finding that GNNs can effectively use the "gap closed" metric as a proxy for reducing the overall search tree size.
  • Initial Basis Selection: Before the simplex method even starts, Zhenan Fan and Yong Zhang use GNNs to predict a near-optimal starting point, significantly reducing the number of iterations required to reach a solution.

By treating optimization problems as graphs rather than matrices, this research direction provides a mathematically rigorous way to apply deep learning to exact solvers, combining the pattern-recognition power of neural networks with the global optimality guarantees of classical algorithms.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_bipartite_graph_neural_networks_for_math_2af69b7c,
  title = {Bipartite Graph Neural Networks for Mathematical Programming Solvers},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bipartite-graph-neural-networks-for-mathematical-programming-solvers/rdr_2af69b7c61d246489d1851ba1df305eb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_bipartite_graph_neural_networks_for_math_2af69b7c_v1,
  title = {Bipartite Graph Neural Networks for Mathematical Programming Solvers},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bipartite-graph-neural-networks-for-mathematical-programming-solvers/rdr_2af69b7c61d246489d1851ba1df305eb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}