A Landscape Classification Framework for NP-Hard Problems: From Reconnaissance to Algorithm Selection
Fuente:
Zenodo
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Recurso digital |
| Lingua: | inglese |
| Pubblicazione: |
Zenodo
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866901877503819776 |
|---|---|
| author | Rao, Huiying |
| author_facet | Rao, Huiying |
| contents | <p>We propose a unified classification framework for NP-hard problems based on loss landscape topology. The framework classifies 95% of known NP problems into seven boxes (combinatorial optimisation, graph theory, logical satisfaction, path/network, permutation/assignment, sequential decision, miscellaneous), further divided into 24 sub-boxes each with formal objective functions. A three-tier reconnaissance system (aerial survey, scout sampling, mass sampling) analyses landscape topology before algorithm selection. A five-cut decision tree maps landscape properties to optimal solvers and parameter configurations. All 22 sub-boxes are exhaustively enumerated with default algorithms, scout-based adjustments, and landscape-based parameter settings. Box 6 (sequential decision) is fully validated using MCCO as proof of concept, demonstrating 3.56× speedup via landscape-guided deployment. The framework draws an analogy to database normalisation: just as complex data can be decomposed through finite normal forms, complex NP problems can be classified through finite landscape cuts. ORCID: 0009-0002-9497-1336.</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>v2 (2026-04-11):</strong> Expanded Related Work with six existing frameworks (Garey & Johnson 1979, FLA/ELA, Algorithm Selection, No Free Lunch, Parameterized Complexity, Learning-Augmented); added cross-framework comparison table; references expanded from 12 to 16.</p> <p><strong>v3 (2026-04-11): Added Scout-Based Algorithm Adjustment and Landscape-Based Parameter Configuration (22 sub-boxes exhaustively enumerated with reconnaissance-based overrides and full parameter lookup tables); Landscape Transformation section (8 transformation methods, 4 difficulty scores, 4-layer stopping conditions with marginal benefit and ROI analysis, precision recovery); Statistical Foundations of Reconnaissance (Type I/II error rates, Power Analysis for scout count, Bonferroni correction, effect size estimation, GP uncertainty propagation); AI-Executable Protocol discussion; three-layer acceleration conclusion (reconnaissance × transformation × AI execution); TSP worked example with three-way comparison (brute force vs blind default vs framework-guided, 0.006s solve time); Scaling test (10/20/50 cities) with "How Close to P?" comparison table (framework at 10⁶ vs brute force at 10⁶⁴); Limitations expanded to 8 items.</strong></p> <p> </p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]">v4 (2026-04-12):</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>Three new chapters:</strong></p> <ul class="[li_&]:mb-0 [li_&]:mt-1 [li_&]:gap-1 [&:not(:last-child)_ul]:pb-1 [&:not(:last-child)_ol]:pb-1 list-disc flex flex-col gap-1 pl-8 mb-3"> <li class="whitespace-normal break-words pl-2">Landscape Cutting (Decomposition): cutting principles, five cutting tools, six-box cuttability table, transform-first-then-cut ordering, parallel deployment pipeline with global refinement, five cutting considerations.</li> <li class="whitespace-normal break-words pl-2">The Evaluation Matrix: 9 transformations × 4 cuts = 36-cell exhaustive evaluation; empirical validation on 100-city TSP (12 cells in 3.37s); cutting quality check with exhaustibility guarantee.</li> <li class="whitespace-normal break-words pl-2">Algorithm Adequacy Scoring: scale × difficulty → four-tier minimum tool level.</li> </ul> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>Cross-box empirical validation (six boxes, all new):</strong></p> <ul class="[li_&]:mb-0 [li_&]:mt-1 [li_&]:gap-1 [&:not(:last-child)_ul]:pb-1 [&:not(:last-child)_ol]:pb-1 list-disc flex flex-col gap-1 pl-8 mb-3"> <li class="whitespace-normal break-words pl-2">Box 1b TSP: TSPLIB standard benchmarks (eil51/berlin52/kroA100), equal-time-budget fair comparison, framework wins by 4–8% gap reduction.</li> <li class="whitespace-normal break-words pl-2">Box 1a MKP: Multidimensional knapsack (50–500 items, 3–10 constraints), framework wins by 1.4–6.9%, Chu & Beasley (1998) reference added.</li> <li class="whitespace-normal break-words pl-2">Box 2a Graph Coloring: 50–200 nodes, density 0.1–0.5, framework saves 14–30% colors via DSatur + Tabu Search.</li> <li class="whitespace-normal break-words pl-2">Box 3a 3-SAT: tested across phase transition (α = 2.0–5.0), framework selects CDCL for hard instances, solves instances that blind WalkSAT cannot, 15.1× speedup at α = 4.2.</li> <li class="whitespace-normal break-words pl-2">Box 4b VRP: 20–100 customers, framework serves +44 additional customers (coverage 56% → 100%), natural application of cutting mechanism.</li> <li class="whitespace-normal break-words pl-2">Box 5a Scheduling: 20–200 jobs, framework wins by 7–27%, 200-job instance within 0.1% of lower bound.</li> </ul> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>How Close to P cross-box comparison table:</strong> five of eight test cases at or near P, three within 1–2 orders of magnitude, zero large gaps.</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>Improvement acceleration data:</strong> 9% at 20 cities → 66% at 50 cities → 80% at 100 cities.</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>Conclusion upgraded:</strong> three-layer → four-layer acceleration (reconnaissance × transformation × cutting × AI execution); TSPLIB scaling evidence added.</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>References:</strong> 16 → 18 (added Reinelt 1991 TSPLIB, Chu & Beasley 1998 MKP).</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_19546748 |
| institution | Zenodo |
| language | eng |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | A Landscape Classification Framework for NP-Hard Problems: From Reconnaissance to Algorithm Selection Rao, Huiying NP-hard loss landscape algorithm selection fitness landscape analysis combinatorial optimisation meta-algorithm landscape classification reconnaissance MCCO <p>We propose a unified classification framework for NP-hard problems based on loss landscape topology. The framework classifies 95% of known NP problems into seven boxes (combinatorial optimisation, graph theory, logical satisfaction, path/network, permutation/assignment, sequential decision, miscellaneous), further divided into 24 sub-boxes each with formal objective functions. A three-tier reconnaissance system (aerial survey, scout sampling, mass sampling) analyses landscape topology before algorithm selection. A five-cut decision tree maps landscape properties to optimal solvers and parameter configurations. All 22 sub-boxes are exhaustively enumerated with default algorithms, scout-based adjustments, and landscape-based parameter settings. Box 6 (sequential decision) is fully validated using MCCO as proof of concept, demonstrating 3.56× speedup via landscape-guided deployment. The framework draws an analogy to database normalisation: just as complex data can be decomposed through finite normal forms, complex NP problems can be classified through finite landscape cuts. ORCID: 0009-0002-9497-1336.</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>v2 (2026-04-11):</strong> Expanded Related Work with six existing frameworks (Garey & Johnson 1979, FLA/ELA, Algorithm Selection, No Free Lunch, Parameterized Complexity, Learning-Augmented); added cross-framework comparison table; references expanded from 12 to 16.</p> <p><strong>v3 (2026-04-11): Added Scout-Based Algorithm Adjustment and Landscape-Based Parameter Configuration (22 sub-boxes exhaustively enumerated with reconnaissance-based overrides and full parameter lookup tables); Landscape Transformation section (8 transformation methods, 4 difficulty scores, 4-layer stopping conditions with marginal benefit and ROI analysis, precision recovery); Statistical Foundations of Reconnaissance (Type I/II error rates, Power Analysis for scout count, Bonferroni correction, effect size estimation, GP uncertainty propagation); AI-Executable Protocol discussion; three-layer acceleration conclusion (reconnaissance × transformation × AI execution); TSP worked example with three-way comparison (brute force vs blind default vs framework-guided, 0.006s solve time); Scaling test (10/20/50 cities) with "How Close to P?" comparison table (framework at 10⁶ vs brute force at 10⁶⁴); Limitations expanded to 8 items.</strong></p> <p> </p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]">v4 (2026-04-12):</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>Three new chapters:</strong></p> <ul class="[li_&]:mb-0 [li_&]:mt-1 [li_&]:gap-1 [&:not(:last-child)_ul]:pb-1 [&:not(:last-child)_ol]:pb-1 list-disc flex flex-col gap-1 pl-8 mb-3"> <li class="whitespace-normal break-words pl-2">Landscape Cutting (Decomposition): cutting principles, five cutting tools, six-box cuttability table, transform-first-then-cut ordering, parallel deployment pipeline with global refinement, five cutting considerations.</li> <li class="whitespace-normal break-words pl-2">The Evaluation Matrix: 9 transformations × 4 cuts = 36-cell exhaustive evaluation; empirical validation on 100-city TSP (12 cells in 3.37s); cutting quality check with exhaustibility guarantee.</li> <li class="whitespace-normal break-words pl-2">Algorithm Adequacy Scoring: scale × difficulty → four-tier minimum tool level.</li> </ul> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>Cross-box empirical validation (six boxes, all new):</strong></p> <ul class="[li_&]:mb-0 [li_&]:mt-1 [li_&]:gap-1 [&:not(:last-child)_ul]:pb-1 [&:not(:last-child)_ol]:pb-1 list-disc flex flex-col gap-1 pl-8 mb-3"> <li class="whitespace-normal break-words pl-2">Box 1b TSP: TSPLIB standard benchmarks (eil51/berlin52/kroA100), equal-time-budget fair comparison, framework wins by 4–8% gap reduction.</li> <li class="whitespace-normal break-words pl-2">Box 1a MKP: Multidimensional knapsack (50–500 items, 3–10 constraints), framework wins by 1.4–6.9%, Chu & Beasley (1998) reference added.</li> <li class="whitespace-normal break-words pl-2">Box 2a Graph Coloring: 50–200 nodes, density 0.1–0.5, framework saves 14–30% colors via DSatur + Tabu Search.</li> <li class="whitespace-normal break-words pl-2">Box 3a 3-SAT: tested across phase transition (α = 2.0–5.0), framework selects CDCL for hard instances, solves instances that blind WalkSAT cannot, 15.1× speedup at α = 4.2.</li> <li class="whitespace-normal break-words pl-2">Box 4b VRP: 20–100 customers, framework serves +44 additional customers (coverage 56% → 100%), natural application of cutting mechanism.</li> <li class="whitespace-normal break-words pl-2">Box 5a Scheduling: 20–200 jobs, framework wins by 7–27%, 200-job instance within 0.1% of lower bound.</li> </ul> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>How Close to P cross-box comparison table:</strong> five of eight test cases at or near P, three within 1–2 orders of magnitude, zero large gaps.</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>Improvement acceleration data:</strong> 9% at 20 cities → 66% at 50 cities → 80% at 100 cities.</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>Conclusion upgraded:</strong> three-layer → four-layer acceleration (reconnaissance × transformation × cutting × AI execution); TSPLIB scaling evidence added.</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>References:</strong> 16 → 18 (added Reinelt 1991 TSPLIB, Chu & Beasley 1998 MKP).</p> |
| title | A Landscape Classification Framework for NP-Hard Problems: From Reconnaissance to Algorithm Selection |
| topic | NP-hard loss landscape algorithm selection fitness landscape analysis combinatorial optimisation meta-algorithm landscape classification reconnaissance MCCO |
| url | https://doi.org/10.5281/zenodo.19546748 |