---
license: openrail
tags:
- TSP
- VRP
- 3D
- 3D_Packing
- MILP
- base_model
---

![](https://huggingface.co/Chunjiang-Intelligence/Lippershey-Base/resolve/main/banner.png)

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.

![](https://huggingface.co/Chunjiang-Intelligence/Lippershey-Base/resolve/main/train.jpg)