File size: 12,218 Bytes
a77dbc7 5668562 e2cb0ea 5668562 a77dbc7 a601984 c2657df 5668562 a601984 2d489db | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 | ---
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:
$$\min \quad c^T x$$
$$\text{s.t.} \quad A x \le b$$
$$l_i \le x_i \le u_i, \quad \forall i \in \{1, \dots, n\}$$
$$x_i \in \mathbb{Z} \quad \forall i \in \mathcal{I}, \quad x_i \in \mathbb{R} \quad \forall i \in \mathcal{C}$$
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:
1. 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)})$$
2. 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:
1. Generate a target binary solution $x^* \in \{0, 1\}^n$.
2. Generate a sparse constraint matrix $A \in \mathbb{R}^{m \times n}$.
3. 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.
4. 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.
```python
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.
```python
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.
```python
@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/loss` drop 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_mean` against `train/true_mean`. They should overlap near the $0$ axis, indicating the model's global prediction scale matches the mathematical distribution of your planning domain.
 |