Mip Solution Prediction Eval

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

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

@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