license: openrail
tags:
- TSP
- VRP
- 3D
- 3D_Packing
- MILP
- base_model
Lippershey-Base is a pretrained, self-supervised foundation model designed to extract highly generalizable topological and geometric representations from Mixed-Integer Linear Programs (MILPs) and discrete planning structures.
By representing arbitrary optimization problems as variable-constraint bipartite graphs, Lippershey-Base learns the underlying mathematical language of optimization, providing a powerful pretrained backbone for downstream reinforcement learning (PPO), exact solver acceleration, and primal heuristics.
1. Mathematical Background & Problem Formulation
Traditional deep learning models for combinatorial optimization (CO) are usually constrained to single, specific problems (e.g., TSP-only or Knapsack-only architectures). Lippershey-Base achieves generality by operating on the standard mathematical formulation of Mixed-Integer Linear Programming (MILP), which can represent almost all discrete planning and combinatorial optimization problems.
Bipartite Graph Representation
Any MILP can be mathematically written as:
We map this system into a sparse bipartite graph $\mathcal{G} = (\mathcal{V}_v, \mathcal{V}_c, \mathcal{E})$:
- Variable Nodes ($\mathcal{V}_v$): Representing the decision variables $x_i$. Node features $X_v \in \mathbb{R}^{n \times 5}$ encode: $$[c_i, l_i, u_i, \text{is_integer}_i, \text{is_masked}_i]$$
- Constraint Nodes ($\mathcal{V}_c$): Representing the constraints $j$. Node features $X_c \in \mathbb{R}^{m \times 5}$ encode: $$[b_j, 0, 0, 0, 0] \quad (\text{padded to match dimension})$$
- Directed Bipartite Edges ($\mathcal{E}$): Connects constraint node $j$ to variable node $i$ if $A_{ji} \neq 0$. The edge attribute $e_{ji} \in \mathbb{R}^{1}$ is the matrix coefficient $A_{ji}$.
2. Model Architecture: Bipartite Graph Transformer
Lippershey-Base utilizes an alternating message-passing Graph Transformer block to model the algebraic and primal-dual structures of MILPs.
Alternating Bipartite Attention (ABA)
Unlike standard homogeneous GNNs, each layer in Lippershey-Base consists of two asymmetrical attention steps:
Constraint-to-Variable (C2V) Update: Variables aggregate information from the constraints they participate in. This allows variables to learn their resource bottlenecks. $$h_{v_i}^{(l+1)} = \text{MultiHeadAttn}\left( \mathbf{Q}=v_i^{(l)}, \mathbf{K}=c_j^{(l)}, \mathbf{V}=c_j^{(l)}, \text{edge_attr}=e_{ji} \right)$$ $$v_i^{(l+1)} = \text{LayerNorm}\left( v_i^{(l)} + \text{GELU}(h_{v_i}^{(l+1)}) \right)$$ $$v_i^{(l+1)} = v_i^{(l+1)} + \text{FFN}(v_i^{(l+1)})$$
Variable-to-Constraint (V2C) Update: Constraints aggregate information from their constituent variables to update constraint embeddings. $$h_{c_j}^{(l+1)} = \text{MultiHeadAttn}\left( \mathbf{Q}=c_j^{(l)}, \mathbf{K}=v_i^{(l+1)}, \mathbf{V}=v_i^{(l+1)}, \text{edge_attr}=e_{ji} \right)$$ $$c_j^{(l+1)} = \text{LayerNorm}\left( c_j^{(l)} + \text{GELU}(h_{c_j}^{(l+1)}) \right)$$ $$c_j^{(l+1)} = c_j^{(l+1)} + \text{FFN}(c_j^{(l+1)})$$
3. The Self-Supervised Pre-Training Paradigm
Lippershey-Base is pre-trained using Masked Objective Reconstruction (MOR) on structurally valid MILP spaces.
Why MOR forces Geometric Understanding
In a MILP, the objective vector $c$ defines the direction of optimization, while $Ax \le b$ defines the feasible polytope. By masking $c_i$ (setting it to $0$ and marking is_masked=1), the model cannot see the optimization direction of variable $i$.
To reconstruct $c_i$, the model must analyze how variable $i$ is coupled with other variables through the constraint boundaries. It must implicitly understand the concept of slack, feasibility boundaries, and variable trade-offs, which are the fundamental pillars of mathematical optimization.
Guaranteed Feasibility via Constraint Planting
Pre-training on random infeasible linear systems leads to chaotic representations. Lippershey-Base's training data is synthesized using Constraint Planting:
- Generate a target binary solution $x^* \in {0, 1}^n$.
- Generate a sparse constraint matrix $A \in \mathbb{R}^{m \times n}$.
- Set the constraint bounds $b = Ax^* + s$, where $s \in \mathbb{R}^m_{\ge 0}$ is a positive slack vector. This guarantees that $x^*$ is always a feasible solution.
- Generate $c$ correlated with $x^*$ to ensure the planted solution behaves like an optimal or near-optimal point.
4. Downstream Fine-Tuning Scenarios (Extensive Code Guides)
Once pre-trained, the encoder parameters in LippersheyBase can be transferred to various downstream tasks. Below are three detailed, production-grade integration guides.
Scenario A: Deep Reinforcement Learning (PPO) for Sequential Planning
In routing (TSP/VRP) or scheduling (Job-Shop), decisions are made sequentially. Here, we fine-tune Lippershey-Base as the policy network backbone.
import torch
import torch.nn as nn
from torch_geometric.data import Batch
from modeling_lippershey import LippersheyBase
class LippersheyPPOAgent(nn.Module):
"""
Production-grade PPO Actor-Critic using Lippershey-Base as a pre-trained backbone.
Enforces hard constraints natively via Action Masking.
"""
def __init__(self, pretrained_safetensors_path, hidden_dim=256):
super().__init__()
# Load the pre-trained mathematical encoder
self.encoder = LippersheyBase.from_pretrained_safetensors(
pretrained_safetensors_path,
node_in_dim=5,
hidden_dim=hidden_dim
)
# Freeze backbone parameters early in fine-tuning to preserve features
# can be unfrozen later for end-to-end tuning
for param in self.encoder.parameters():
param.requires_grad = False
# Actor Head (Policy): Outputs categorical logit for each variable decision
self.actor = nn.Sequential(
nn.Linear(hidden_dim, hidden_dim // 2),
nn.GELU(),
nn.Linear(hidden_dim // 2, 1)
)
# Critic Head (Value): Predicts expected future objective value
self.critic_pooling = nn.Linear(hidden_dim, 1)
self.critic = nn.Sequential(
nn.Linear(hidden_dim, hidden_dim // 2),
nn.GELU(),
nn.Linear(hidden_dim // 2, 1)
)
def forward(self, batch: Batch, action_mask=None):
"""
Args:
batch: PyG Batch containing bipartite representations of the current step.
action_mask: Boolean tensor [num_variables_in_batch] marking legal decisions.
"""
# 1. Extract latents from pre-trained backbone
v = self.encoder.var_proj(batch.x_var)
c = self.encoder.con_proj(batch.x_con)
for layer in self.encoder.layers:
v, c = layer(v, c, batch.edge_index_c2v, batch.edge_attr)
# v shape: [total_num_variables_in_batch, hidden_dim]
# 2. Compute Policy Logits (Actor)
logits = self.actor(v).squeeze(-1) # Shape: [total_num_variables]
# Apply strict constraint masks (set invalid variable choices to -inf)
if action_mask is not None:
logits = logits.masked_fill(~action_mask, float('-inf'))
# 3. Compute State Value (Critic)
# Pool variable embeddings to represent the entire graph state
# batch.batch is PyG's indicator tensor mapping nodes to their graph index
graph_repr = torch.zeros(batch.num_graphs, v.size(-1), device=v.device)
graph_repr.index_add_(0, batch.x_var_batch, v) # Sum pooling
state_value = self.critic(graph_repr) # Shape: [num_graphs, 1]
return logits, state_value
def get_action_and_value(self, batch, action_mask=None, action=None):
logits, state_value = self.forward(batch, action_mask)
# Create a categorical distribution over variables
dist = torch.distributions.Categorical(logits=logits)
if action is None:
action = dist.sample()
return action, dist.log_prob(action), dist.entropy(), state_value
Scenario B: Accelerated Branch-and-Bound (Variable Selection)
In exact MILP solvers (such as SCIP), the most computationally expensive step is Variable Branching. We can fine-tune Lippershey-Base to imitate "Strong Branching" (expert demonstrations), turning variable selection into a fast GPU-accelerated inference task.
class LippersheyBranchingModel(nn.Module):
"""
Finetuned classifier to select fractional variables for branching in B&B trees.
"""
def __init__(self, pretrained_safetensors_path, hidden_dim=256):
super().__init__()
self.encoder = LippersheyBase.from_pretrained_safetensors(
pretrained_safetensors_path, node_in_dim=5, hidden_dim=hidden_dim
)
self.branch_head = nn.Sequential(
nn.Linear(hidden_dim, hidden_dim // 2),
nn.GELU(),
nn.Linear(hidden_dim // 2, 1) # Probability score of being the branching variable
)
def forward(self, batch, fractional_mask):
"""
fractional_mask: Boolean mask indicating which variables are currently fractional (LP relaxation).
"""
v = self.encoder.var_proj(batch.x_var)
c = self.encoder.con_proj(batch.x_con)
for layer in self.encoder.layers:
v, c = layer(v, c, batch.edge_index_c2v, batch.edge_attr)
scores = self.branch_head(v).squeeze(-1)
# Mask out variables that are already integer
scores = scores.masked_fill(~fractional_mask, float('-inf'))
return scores # Apply Softmax to select the branching target
Scenario C: Primal Heuristic Warm-Starting (Sub-MILP Generation)
For massive industrial scheduling/packing problems, solvers like Gurobi can take hours to find the first feasible solution. We can use Lippershey-Base to predict the probability of binary variables being 1 in the optimal solution, freeze high-confidence variables, and let the solver solve the remaining sub-problem in seconds.
@torch.no_grad()
def generate_warm_start_bounds(pretrained_model, batch, threshold=0.95):
"""
Predicts optimal variable values and returns indices to freeze for Gurobi.
"""
pretrained_model.eval()
preds = pretrained_model(
batch.x_var, batch.x_con, batch.edge_index_c2v, batch.edge_attr
)
# Convert logits/reconstructions to probability space via sigmoid
probabilities = torch.sigmoid(preds).cpu().numpy()
freeze_to_one = np.where(probabilities > threshold)[0]
freeze_to_zero = np.where(probabilities < (1 - threshold))[0]
return freeze_to_one, freeze_to_zero
5. Performance Metrics & Pre-Training Log Analysis
When pre-training Lippershey-Base, use the following guidelines to evaluate the quality of the learned representation:
- Validation Loss (MSE): Measures how accurately the model reconstructs the continuous coefficients. A healthy convergence on structured MILPs should see
val/lossdrop below 0.15 (L1 average absolute error $\approx 0.38$ on $[-1, 1]$ scale). - Grad Norm (L2): Should stabilize between 0.3 and 1.0. Constant clipping to 1.0 indicates learning rate is too high; an decaying gradient norm towards 0 without loss convergence indicates gradient vanishing.
- Prediction Mean Convergence: Check
train/pred_meanagainsttrain/true_mean. They should overlap near the $0$ axis, indicating the model's global prediction scale matches the mathematical distribution of your planning domain.
