AI Paper Atlas

Research map / Optimization / Optimizers

Local Minima in Quadratic-Penalty Relaxations of Binary Linear Programs

Cheng-Han Huang, Yongliang Sun, Chaoyan Huang, Ismail Alkhouri, Rongrong Wang

ICML 2026 · Optimization › Optimizers · approach: Differentiating through embedded optimization · 0 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
use ancestor penalty instead of naive parent penalty for precedence constraints (ablation)Open-pit mining relaxed QUBO with PGD · MineLib raw block modelsfeasibility rate: 0% (0/20) -> 100% (20/20)Improved
use ancestor penalty instead of naive parent penalty (ablation)Open-pit mining relaxed QUBO with PGD · MineLib raw block modelsbinarity rate: 60% (12/20) -> 100% (20/20)Improved
use diagonal-cancelled (binary-equivalent) penalty instead of raw squared residual (ablation)0-1 knapsack relaxed QUBO with projected Adam · kplib instancesbinarity rate: 0% (0/20) -> 100% (20/20)Improved
increase penalty weight 1000x (gamma_small to gamma_large) for naive knapsack QUBO (ablation)naive knapsack QUBO · kplib instancesbinarity rate: 0% (0/20) -> 0% (0/20)No clear effect
use square-free (diagonal-cancelled) assignment penalty instead of naive penalty (ablation)time-indexed TSP relaxed QUBO with PGD · TSPLIB instances, gamma_smallfeasibility rate: 0% (0/20) -> 100% (20/20)Improved
increase penalty weight 1000x for naive TSP QUBO (ablation)naive time-indexed TSP QUBO · TSPLIB instancesbinarity rate: 0% (0/20) -> 5% (1/20)No clear effect
use PGD on relaxed QUBO instead of Gurobi for MIS under 5-minute budgetMIS on Erdos-Renyi graphs · n 2000 to 40000, p 0.3/0.5/0.7average independent set size: 27 vs 21.875 (n=2000, p=0.3)Improved
compare PGD with SLS and GRASP heuristics at 5 minutesPGD for MIS · Erdos-Renyi representative subsetaverage independent set size: 16 vs 16.125 (SLS) vs 17 (GRASP), n=4000, p=0.5No clear effect
add batched parallel restarts on one GPUPGD for MIS · Erdos-Renyi, 30 s budgetaverage independent set size: 191.5 -> 200.75 (n=3000, p=1/30)Improved
increase penalty weight alone for naive open-pit parent penaltyOpen-pit parent QUBO · theory (Lemma 3.3)feasibility of local minimaNo clear effect

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy