| --- |
| 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. |
|
|
|  |
