💻 computer science

FORGE: Foundational Optimization Representations from Graph Embeddings

The paper introduces Forge, a framework that pre-trains a vector-quantized graph autoencoder on diverse mixed-integer programming instances to create scalable, generalizable representations that outperform state-of-the-art methods in predicting integrality gaps and guiding search without requiring optimal solution labels.

Original authors: Zohair Shafi, Serdar Kadioglu

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zohair Shafi, Serdar Kadioglu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, complex puzzle. In the world of computer science, these puzzles are called Combinatorial Optimization problems. They are everywhere: from figuring out the most efficient route for a delivery truck to scheduling power grids or organizing a warehouse.

Traditionally, solving these puzzles requires powerful, expensive computer programs (called "solvers") that try millions of combinations. It's like trying to find a specific needle in a haystack by checking every single piece of hay one by one.

Recently, scientists tried to use Machine Learning (AI) to speed this up. But there was a big catch: to teach the AI how to solve these puzzles, you first had to use the slow, expensive solvers to solve thousands of puzzles perfectly just to create a "textbook" for the AI to study. This was a vicious cycle: you needed the slow tool to teach the fast tool, which defeated the purpose.

Enter "Forge."

The authors of this paper created a new framework called Forge. Think of Forge not as a puzzle solver, but as a universal translator or a master librarian for optimization problems.

Here is how it works, broken down into simple analogies:

1. The Problem: Every Puzzle Looks Different

Imagine you have a library of puzzles. Some are jigsaw puzzles, some are Sudoku, and some are crosswords. Previous AI models were like specialists: you had to train one AI specifically for Sudoku and a different one for crosswords. If you gave the Sudoku AI a crossword, it was lost. Also, they needed the "answer key" (the perfect solution) to learn, which was expensive to get.

2. The Solution: A "Vocabulary" for Puzzles

The authors looked at how AI handles language (like Chatbots) and images. They realized that instead of teaching an AI the answer to every puzzle, they could teach it to recognize the shape and structure of the puzzle itself.

The Bipartite Graph: They turn every math problem into a map of dots and lines (a graph). The dots are the "variables" (the things you can change) and the "constraints" (the rules you must follow).
Vector Quantization (The Magic Dictionary): This is the secret sauce. Imagine the AI has a giant dictionary with 5,000 unique words. When it looks at a puzzle, it doesn't try to memorize the whole picture. Instead, it breaks the puzzle down into small chunks and assigns each chunk a "word" from its dictionary.
- A specific type of rule might get the word "Code 12."
- A specific type of variable might get the word "Code 45."
The Result: Instead of a messy, complex math problem, the AI now sees a simple sentence made of these codes. This allows it to understand the global structure of the problem without needing to know the final answer.

3. The Training: Learning Without Answers

This is the biggest breakthrough. Forge was trained unsupervised.

Old Way: "Here is a puzzle and its perfect solution. Learn how to get from A to B."
Forge Way: "Here are 2,850 different puzzles. Just look at how they are built. Group similar-looking puzzles together. You don't need to know the solution; just learn the shape of the problem."

It's like a child learning to recognize animals. They don't need to know how to breed a dog or a cat to know that a Golden Retriever and a Poodle are both "dogs." They just learn the visual patterns. Forge learned the "visual patterns" of math problems.

4. What Can Forge Do Now?

Once Forge learned this "vocabulary," the researchers tested it in two ways:

A. Clustering (Sorting the Library)
They gave Forge a bunch of puzzles it had never seen before. Without being told what they were, Forge successfully sorted them into groups. It knew that a "Set Cover" problem looked structurally similar to other "Set Cover" problems, even if they were different sizes or difficulty levels. It did this better than previous methods that tried to average out the details.

B. Helping the Solver (The "Hint" System)
This is where it gets practical. The researchers took a top-tier commercial solver (Gurobi) and gave it a "cheat sheet" generated by Forge.

Task 1: The "Gap" Guess: Forge looked at a hard puzzle and guessed how far off the "easy" version of the problem was from the "hard" version. Based on this guess, it created a "pseudo-cut" (a rule) to tell the solver, "Hey, the answer is definitely in this range, don't waste time looking outside it." This made the solver find good answers much faster.
Task 2: The "Search" Guide: Forge looked at the puzzle and said, "These specific variables are likely to be part of the solution. Focus on them first." This guided the solver through the maze more efficiently.

The Bottom Line

No "Answer Key" Needed: Forge learned by looking at the structure of problems, not by solving them perfectly first.
One Model Fits All: A single pre-trained Forge model worked on many different types of problems (logistics, scheduling, etc.) and different sizes.
Real Results: When they added Forge's "hints" to a commercial solver, the solver found better solutions faster, improving performance by up to 85% in some cases.

In short, Forge is a foundational model that teaches AI to "read" the structure of complex math problems like a language, allowing it to give smart hints to solvers without needing to be taught the answers beforehand. The authors have even made their code and models public so others can use this "dictionary" to build better optimization tools.

Technical Summary: Forge: Foundational Optimization Representations from Graph Embeddings

1. Problem Statement

Combinatorial optimization (CO) problems, particularly Mixed-Integer Programming (MIP), are fundamental to science and engineering but remain computationally expensive to solve. While machine learning (ML) offers promising alternatives, current learning-based approaches suffer from significant scalability and generalization limitations:

Data Dependency: Training typically requires solving a large number of difficult instances to generate labeled data, incurring high computational costs and relying on the very solvers researchers aim to accelerate.
Lack of Generalization: Existing methods often train dedicated models for specific problem distributions, downstream tasks, or problem sizes. They fail to generalize across different problem domains (e.g., Set Cover vs. Combinatorial Auction) or task types (e.g., cut generation vs. search guidance).
Structural Limitations: Most CO methods rely on Graph Neural Networks (GNNs) which effectively capture local variable-constraint information but struggle to encode meaningful global instance structure due to inherent locality bias.

The paper posits a need for a foundational optimization representation: a pre-trained, general-purpose model capable of generating MIP embeddings that generalize across tasks, problems, and sizes, trained in an unsupervised manner without requiring optimal solutions.

2. Methodology: The Forge Framework

Forge (Foundational Optimization Representations from Graph Embeddings) is a framework that pre-trains a vector-quantized graph autoencoder on a diverse collection of MIP instances. It draws inspiration from Natural Language Processing (NLP) and Computer Vision (CV) foundational models.

Core Architecture

The framework operates through the following stages (Figure 1):

MIP-to-BP (Bipartite Representation): MIP instances are represented as bipartite graphs where nodes are variables and constraints.
- Node Features: Unlike prior works that rely on solver-generated features (e.g., from branch-and-bound trees), Forge uses only basic input properties: constraint sense (>, <, =) and RHS values for constraints; variable type, bounds, and objective coefficients for variables. This ensures the model does not depend on solving the instance.
BP-to-GNN: A GraphSAGE-based GNN (two layers) processes the bipartite graph to generate continuous embeddings for each node.
Vector Quantized Codebook (The "Vocabulary"): To address the GNN's inability to capture global structure, the continuous embeddings are passed through a vector quantizer. This maps each node to a discrete code from a learnable codebook of size $k$ $k$ (acting as a vocabulary).
- This step preserves global structural information by creating a distribution of discrete codes across the instance, analogous to token distributions in language models.
Reconstruction (Autoencoder): The discrete codes are mapped back to codewords and passed through decoders to reconstruct the original node features and edge weights.
Loss Function: The model is trained unsupervisedly to minimize:
- Reconstruction loss (node features and edges).
- Codebook loss (moving codewords toward embeddings).
- Commitment loss (moving embeddings toward codewords).

Representations

Once trained, Forge produces two levels of representations:

Local: Discrete codewords for individual variables and constraints.
Global: An instance-level embedding derived from the frequency distribution of the assigned codes across the entire graph. The embedding dimension equals the vocabulary size ($|codebook|$).

3. Key Contributions

The paper outlines five primary contributions:

Foundational Model Step: Introduction of Forge, a single pre-trained model generating MIP embeddings at both instance and fine-grained (variable/constraint) levels without supervision.
Unsupervised Generalization: Demonstration that Forge embeddings can cluster unseen instances across diverse problem domains and difficulty levels with high accuracy, outperforming static features and standard GNN readouts.
Supervised Adaptability: Proof that the same pre-trained model can be fine-tuned with minimal, cheaply labeled data for radically different downstream tasks (integrality gap prediction and search guidance) across varied problem sizes.
Solver Integration: Successful integration of Forge predictions into Gurobi, a commercial solver, demonstrating consistent improvements in primal gaps across multiple problem types.
ML Augmentation: Enhancement of state-of-the-art (SOTA) learning-based methods (specifically Li et al., 2025 and PS-Gurobi) by concatenating Forge embeddings, yielding significant performance gains on unseen instances.

4. Experimental Results

Unsupervised Clustering

Setup: Trained on 1,800 MIPLIB instances; tested on 1,000 unseen instances from D-MIPLIB and strIPlib covering 21 domain-difficulty pairs.
Metric: Normalized Mutual Information (NMI) for clustering accuracy.
Performance: Forge achieved an NMI of 0.953, significantly outperforming Mean Readout (0.726) and Label Propagation (0.790). Visualizations (PaCMAP) showed distinct clusters for each problem type and a clear gradient from easy to hard problems, despite the model never seeing these specific instances during training.

Task I: Integrality Gap Prediction (Pseudo-Cut Generation)

Goal: Predict the integrality gap to generate a pseudo-cut for the root node, tightening the LP relaxation bound.
Training: Fine-tuned on 450 instances (CA, SC, GIS) with labels generated by Gurobi (120s timeout), avoiding full optimality.
Results:
- On "very-hard" test instances (including MVC, which was unseen in fine-tuning), Forge achieved mean absolute deviations of 12–19% across problem types.
- Solver Impact: Integrating Forge pseudo-cuts into Gurobi reduced the primal gap by up to 85% (e.g., 84.52% gain on Generalized Independent Set) compared to Gurobi alone.
- Comparison: Outperformed the SOTA method by Li et al. (2025) (18.63% deviation vs. 20.14%) on 17,500 unseen instances without additional training.

Task II: Search Guidance

Goal: Predict which variables are likely to be in the optimal solution to guide the branch-and-bound search.
Training: Fine-tuned on 700 instances using a combination of Binary Cross-Entropy (BCE) and Triplet Loss. Labels were derived from feasible solutions found within 5 minutes (no optimality required).
Results:
- Solver Impact: Gurobi with Forge search guidance achieved up to 48.75% improvement in primal gap and up to 35% speed-up in convergence time on medium instances.
- ML Augmentation: When used to augment PS-Gurobi (a SOTA learning-based search guidance method), Forge embeddings reduced the primal gap by over 40% (Combinatorial Auction) and 50% (Generalized Independent Set).

5. Significance and Claims

The paper claims that Forge represents a significant step toward foundational models for optimization. Its significance lies in:

Breaking the Solver Dependency: It learns structural representations without requiring access to optimal solutions or internal solver states during pre-training, addressing the "chicken-and-egg" problem of needing solvers to train solvers.
Universal Representation: It demonstrates that a single model can generalize across disparate problem types (e.g., Set Cover, Combinatorial Auction, Vertex Cover) and task types (gap prediction, search guidance), a capability previously limited to problem-specific or task-specific models.
Practical Utility: The framework is not merely theoretical; it integrates directly with commercial solvers and improves upon existing ML pipelines, offering immediate, measurable gains in solving efficiency.
Open Science: The authors release training code, pre-trained weights, and embeddings to foster further research in representation learning for optimization.

The authors remain modest regarding limitations, noting the current scale (3.25M parameters) is small compared to other foundational models, the semantics of the learned "vocabulary" are unexplored, and current integrations are "one-shot" rather than iterative throughout the branch-and-bound tree. They suggest future work could extend these principles to Constraint Satisfaction Problems (CSP) and SAT.