Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Linear Programming Problems
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.
Learns a permutation-equivariant neural network that generates instance-specific projection matrices to reduce LP size, trained end-to-end by maximizing expected projected objective via implicit differentiation.
Problem
Solving high-dimensional linear programs efficiently while keeping solutions feasible; existing data-driven projection methods share one projection matrix across heterogeneous LPs and perform poorly on differing instances.
Approach
A neural model with PELP layers (permutation equivariant in variables, invariant in constraints) maps LP parameters (c, A, b) to an instance-specific projection matrix; training differentiates the optimal projected objective via the implicit function theorem using only primal and dual LP solutions, with a generalization bound from pseudo-dimension.
Key results
- On packing problems with K=50, Ours achieves 0.924 average objective ratio versus 0.230 for Rand and 0.066 for PCA, at 0.055 s versus 23.5 s for Full on 100,000-variable LPs (Table 1).
- Direct violated constraints in 10% to 48% of test LPs, whereas the projection-based method always satisfies constraints.
- Cross-type transfer is poor: a model trained on Packing scores 0.187 on MaxFlow, while training on Mix data gives 0.954 on MaxFlow.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Generate an instance-specific projection with the proposed method instead of using FCNN projections | Packing with 100,000 variables · Packing, 100,000 variables | objective ratio: 0.257 -> 0.924 | Helped |
| Reduce dimensionality using the proposed projection method instead of solving the original LP | Packing with 100,000 variables · Packing, 100,000 variables | time: 23.487 -> 0.055 | Helped |
| Use the proposed projection method instead of random variable selection | Packing with 100,000 variables · Packing, 100,000 variables | objective ratio: 0.230 -> 0.924 | Helped |
| Train on LPs of the same type as the test LPs rather than on different LP types | Ours · Packing, MaxFlow, and MinCostFlow | objective ratio: Packing: 0.187 ± 0.072 -> 0.985 ± 0.032; MaxFlow: 0.142 ± 0.083 -> 0.994 ± 0.014; MinCostFlow: 0.029 ± 0.083 -> 0.894 ± | Helped |
| Train on mixed LP types instead of only a different LP type | Ours · Packing, MaxFlow, and MinCostFlow | objective ratio: Packing: 0.187 ± 0.072 -> 0.981 ± 0.023; MaxFlow: 0.142 ± 0.083 -> 0.954 ± 0.058; MinCostFlow: 0.029 ± 0.083 -> 0.787 ± | Helped |
| Train on varied-size LPs instead of fixed-size LPs (ablation) | Ours · Packing, MaxFlow, and MinCostFlow with varied test sizes | objective ratio | Helped |
| Vary the number of training LPs (ablation) | Ours · Packing, MaxFlow, and MinCostFlow | objective ratio | Helped |
| Remove training (ablation) | Ours · Packing, MaxFlow, and MinCostFlow | objective ratio | Hurt |
| Increase the reduced dimension K (ablation) | Ours · Packing, MaxFlow, and MinCostFlow | objective ratio | Helped |
Surprising findings
- Direct (directly predicting solutions) achieves 0.014 objective ratio on 100,000-variable packing LPs, far below the projection approach, and it violates constraints often.
- Without training, the generated-projection method performs poorly (Figure 9).
Limitations
- Only tested on synthetic LPs and one Netlib instance; generalization across LP types is weak without mixed training.
- Theoretical bound is for fully connected networks, not the permutation-equivariant model actually used.
- Restricted to LPs with a known feasible point; equality constraints handled by transformation; not applicable directly to MILPs.
Experimental setup
Datasets: synthetic Packing LPs synthetic MaxFlow LPs synthetic MinCostFlow LPs GROW7 (Netlib)
Benchmarks: synthetic Packing synthetic MaxFlow synthetic MinCostFlow GROW7
Metrics: average objective ratio computational time in seconds constraint violation rate
Baselines: Rand PCA SharedP FCNN Direct Full
Builds on: Sakaue & Oki 2024 data-driven projections random projection for LP (Vu et al. 2018, Akchen & Mišić 2024) Cheng et al. 2024 neural network data-driven algorithm design
Closest papers by meaning
- Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming (NeurIPS 2024 · similarity 0.90)
- Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.87)
- Learning Generalized Linear Programming Value Functions (NeurIPS 2024 · similarity 0.86)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.86)
- PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming (ICML 2024 · similarity 0.85)
- Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 2025 · 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.