Research map / Learning theory and algorithms / Combinatorial and search optimization
Efficient Bisection Projection to Ensure Neural-Network Solution Feasibility for Optimization over General Set
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Bisection Projection, which uses an IPNN to predict low-eccentricity (Chebyshev-center-like) interior points and then bisection along the segment from the NN prediction to the interior point to restore feasibility over general compact constraint sets.
Problem
Ensuring feasibility of neural-network solutions to input-dependent constrained optimization over general compact sets with non-empty interiors, with bounded optimality loss and low run-time.
Approach
Bisection along the segment between an infeasible NN prediction and a predicted interior point, where the interior point is produced by a dedicated IPNN trained with a robust-margin (Chebyshev-center-inspired) loss so that it has low eccentricity and is feasible across inputs.
Key results
- B-Proj achieves 100% feasibility on all six benchmarks (QP, QCQP, SOCP, SDP, AC-OPF, JCC-IM) where raw NN achieves 58.0%-94.0%.
- B-Proj post-processing takes about 0.016 s on QP and 0.0162 s on QCQP versus 5.23 s and 401 s for orthogonal projection (NN+Proj).
- B-Proj objective optimality gap is comparable to NN+Proj (e.g., 1.00% vs 0.97% solution opt. on QP), and far better than H-Proj (15.42%) on QP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply Bisection Projection to NN predictions | QP · QP | feasibility rate (%): 80.8 -> 100 | Helped |
| Apply Bisection Projection to NN predictions | QCQP · QCQP | feasibility rate (%): 92.0 -> 100 | Helped |
| Apply Bisection Projection to NN predictions | SOCP · SOCP | feasibility rate (%): 89.6 -> 100 | Helped |
| Apply Bisection Projection to NN predictions | SDP · SDP | feasibility rate (%): 58.0 -> 100 | Helped |
| Apply Bisection Projection to NN predictions | AC-OPF · AC-OPF | feasibility rate (%): 94.0 -> 100 | Helped |
| Apply Bisection Projection to NN predictions | JCC-IM · JCC-IM | feasibility rate (%): 84.5 -> 100 | Helped |
| Add robust-margin maximization (γ) to IPNN training (ablation) | Bisection Projection · QP and JCC-IM test inputs | out-of-sample feasibility rate | Helped |
| Add robust-margin maximization (γ) to IPNN training (ablation) | Bisection Projection · QP and JCC-IM projection tests | projection distance | Helped |
| Increase the number of bisection steps (ablation) | Bisection Projection · QP and JCC-IM | optimality gap | Helped |
| Increase the number of bisection steps (ablation) | Bisection Projection · QP and JCC-IM | running time | Hurt |
| Use a reduced bisection stepsize (β = 0.1 rather than β = 0.5) (ablation) | Bisection Projection · Constraint sets with multiple boundary intersections | solution quality | Helped |
| Use a reduced bisection stepsize (β = 0.1 rather than β = 0.5) (ablation) | Bisection Projection · Constraint sets with multiple boundary intersections | number of iterations | Hurt |
Surprising findings
- Homeomorphic projection (H-Proj) achieves 100% feasibility but with markedly larger optimality gaps (e.g., 33.67% on SDP) than bisection projection.
Limitations
- Extension to discrete/mixed-integer constraints left to future work
- Bisection may converge to a boundary point far from the NN prediction when the segment crosses the boundary multiple times (non-convex sets)
- Lipschitz-based feasibility guarantee for IPNN is not directly verifiable in practice
Experimental setup
Datasets: synthetic QP, QCQP, SOCP, SDP instances AC-OPF instances JCC-IM instances
Benchmarks: QP QCQP SOCP SDP AC-OPF JCC-IM
Metrics: feasibility rate optimality gap (MAPE) running time
Baselines: MOSEK PYPOWER NN+WS NN+Proj NN+D-Proj (DC3) NN+H-Proj (homeomorphic projection)
Builds on: homeomorphic projection gauge projection DC3
Closest papers by meaning
- FSNet: Feasibility-Seeking Neural Network for Constrained Optimization with Guarantees (NeurIPS 2025 · similarity 0.86)
- BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks (NeurIPS 2025 · similarity 0.85)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.84)
- Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes (NeurIPS 2024 · similarity 0.84)
- NN-Steiner: A Mixed Neural-Algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem (AAAI 2024 · similarity 0.84)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.83)
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.