Mip Solution Prediction Eval

---
name: mip-solution-prediction-eval
description: Evaluates a graph neural network's ability to predict binary variable values in mixed-integer programming (MIP) instances. It also measures how these predictions accelerate primal solution finding and reduce optimality gaps in a Branch-and-Bound solver. Use when the user wants to benchmark on MIP Instances (8 types), or asks about evaluating this task. Reports average precision (AP).
metadata:
  skill_kind: dataset_eval
  source_arxiv: 1906.09575
  bibtex_key: ding2019accelerating
  confidence: high
---

# mip-solution-prediction-eval

> Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction — Ding et al. (2019) (arXiv:1906.09575, 2019)

## What this evaluates

Evaluates a graph neural network's ability to predict binary variable values in mixed-integer programming (MIP) instances. It also measures how these predictions accelerate primal solution finding and reduce optimality gaps in a Branch-and-Bound solver.

## Datasets

- **MIP Instances (8 types)** — total 1600; splits: train (1120), val (160), test (320)

## Metrics

- `average precision (AP)` **(primary)** — range: [0, 1]
  - AP = sum_{k=1}^n P(k)Delta r(k), where P(k) is precision at cut-off k, and Delta r(k) is the difference in recall from k-1 to k. Designed for imbalanced binary classification.
- `primal gap` — range: percent
  - gamma = |c^T x_tilde - c^T x*_| / (max(|c^T x_tilde|, |c^T x*_|) + epsilon) * 100%. Measures relative objective gap of a feasible solution to the best-known solution.
- `optimality gap` — range: percent
  - zeta = |c^T x_tilde - LB| / (|c^T x_tilde| + epsilon) * 100%. Measures relative gap between primal solution and best lower bound.

## Input / output format

**Input**: Tripartite graph representation of the MIP at the root node, containing variable features, constraint features, and edge features extracted after presolving, root LP relaxation, and root cutting plane.

**Output**: Prediction probability z_j that each binary variable x_j takes value 1, or a set of stable variables S for branching cuts.

## Scoring recipe

```python
def compute_ap(probs, labels):
    pairs = sorted(zip(probs, labels), key=lambda x: -x[0])
    tp, fp, ap = 0, 0, 0.0
    for p, y in pairs:
        if y == 1:
            tp += 1
            ap += tp / (tp + fp)
        else:
            fp += 1
    return ap / max(1, tp)

def compute_primal_gap(pred_obj, best_obj, eps=1e-10):
    return abs(pred_obj - best_obj) / (max(abs(pred_obj), abs(best_obj)) + eps) * 100
```

## Common pitfalls

- The ground truth for gap metrics uses the 'best-known' solution across all methods rather than the true optimum, since many instances are unsolved within the 10000s time limit.
- Feature extraction is strictly confined to the root node after presolving and LP relaxation; extracting features from deeper search tree nodes violates the protocol.
- Standard accuracy is inappropriate due to highly imbalanced binary variable values; Average Precision (AP) must be used instead.

## Evidence (verbatim from paper)

> Noting that solution values of binary variables are usually highly imbalanced, we use the average precision (AP) metric [?] to evaluate the performance of the classifiers. In particular, the AP value is defined as: AP = sum_{k=1}^n P(k)Delta r(k), where k is the rank in the sequence of predicted variables, P(k) is the precision at cut-off k in the list, and Delta r(k) is the difference in recall from k-1 to k.

## Citation

```bibtex
@misc{ding2019accelerating,
  title={Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction},
  author={Ding et al. (2019)},
  year={2019},
  note={arXiv:1906.09575}
}
```

- arXiv: 1906.09575