Chapter Four · failure evidence
What Combinatorial & Discrete Optimization got wrong, from 31 dissertations
Combinatorial and discrete optimization methods frequently suffer from exponential computational complexity, solver timeouts, and rounding errors when continuous relaxations are applied to discrete spaces. Additionally, greedy heuristics and complex machine learning approaches often experience instability or fail to outperform classical baseline solvers and specialized algorithms. These records come from PhD theses at 15 institutions, 2021 to 2026. Each links to its thesis. They were extracted by language models reading the full text, so treat each as a lead to read, not a verdict.
Exact integer formulations and brute-force combinatorial searches suffer from exponential complexity and solver timeouts
Researchers attempting to solve routing, association, and profile optimization problems with exact integer programs or brute-force search encountered combinatorial explosions and excessive runtimes. Consequently, these approaches failed to return feasible solutions within operational limits and were frequently abandoned for polynomial-time or greedy alternatives.
Considered and rejected
Considered and rejected: Brute force combinatorial search and integer programming for cluster load-balancing association rejected due to exponential complexity O((|phi_V,c|+|phi_BS,c|-1 choose |phi_V,c|)), replaced by O(|phi_BS,c||phi_V,c|) greedy sequential association.
Modeling, analysis, and design of collaborative services in vehicular and cloud/edge networks · UT Austin
Considered and rejected
Considered and rejected: Rejected combinatorial search of hypothesis space H in favor of deterministic polynomial-time construction of the maximal Top Program.
Constructive approaches to Program Induction · Imperial
Considered and rejected
Considered and rejected: Rejected solving multi-cost path planning (varying weights of energy vs time) for exact TDOP due to prohibitive combinatorial runtime of running graph search per node pair and departure time.
EXPLOITING FLOWS FOR ORIENTEERING AND PLANNING PROBLEMS · Penn
Tried and failed
exact mixed integer linear programming solver applied to pickup and delivery routing problems. Outcome: too slow. Reason: failed to find any feasible solution within two hours on medium-sized combinatorial problem instances
Optimization of on-demand shared mobility: passenger and freight applications · EPFL
Considered and rejected
Considered and rejected: Decided against cyclic drone routes (visiting a node, making a sub-tour, and returning to the same node) due to intractable combinatorial precedence modeling in MIP.
UNMANNED AERIAL VEHICLES: TRAJECTORY PLANNING AND ROUTING IN THE ERA OF ADVANCED AIR MOBILITY · Georgia Tech
Considered and rejected
Considered and rejected: Rejected direct numerical optimization over the full combinatorial space of deviation functions in data markets in favor of closed-form pointwise maximization over discrete actions inside the regret definition.
Considered and rejected
Considered and rejected: Rejected direct combinatorial optimization for bi-level subset selection in UnEX, adopting iterative greedy empirical search instead
Enhancing medical image classification via uncertainty estimation · Iowa State
Tried and failed
exact integer programming for traveling salesperson problem applied to ordering point cloud boundary contours. Outcome: too slow. Reason: solving the exact formulation directly resulted in combinatorial explosion and impractical computation times
Development and integration of a perceptive robotic grinding system · Iowa State
Tried and failed
path-based formulation for stochastic vehicle routing applied to stochastic evacuation routing optimization. Outcome: too slow. Reason: combinatorial explosion of variables prevented solver convergence within time limit compared to arc-based single trip models
Patient evacuation optimization for health care facilities during hurricanes · UT Austin
Considered and rejected
Considered and rejected: Rejected pure combinatorial/Cross-Entropy brute-force profile optimization for raw time histories due to excessive computational inefficiency across long distances.
Profile Calculation and Bridge Damage Detection Using Vehicle-based Inertial Readings and the Fleet Monitoring Concept · Research Repository UCD
Continuous relaxations and gradient methods degrade performance due to discrete rounding distortions
Continuous optimization approaches and gradient descent struggle when applied to discrete search spaces, categorical inputs, and modular costs. The resulting continuous trajectory vectors fail to preserve discrete constraints, and post-hoc rounding introduces significant distortion that underperforms direct discrete search.
Tried and failed
continuous gradient-based optimization with discrete rounding applied to discrete acquisition function optimization. Outcome: worse than baseline. Reason: distortion introduced by rounding continuous search variables to discrete points
Accelerating HLS Autotuning of Large, Highly-parameterized Reconfigurable SoC Mappings · Penn
Tried and failed
continuous greedy algorithms with discrete greedy rounding applied to fair submodular maximization. Reason: Continuous relaxation trajectory vectors are not valid characteristic vectors of the required subset size.
Online Learning for Resource Allocation in Wireless Networks: Fairness, Communication Efficiency, and Data Privacy · Virginia Tech
Tried and failed
projected gradient descent with weighted L1 norm applied to adversarial examples on tabular data. Outcome: worse than baseline. Reason: continuous gradient optimization handles discrete feature transitions and modular edge costs poorly compared to discrete search
Challenging the Assumptions: Rethinking Privacy, Bias, and Security in Machine Learning · EPFL
Tried and failed
continuous relaxation of discrete surrogate optimization applied to heterogeneous resource allocation. Outcome: worse than baseline. Reason: continuous relaxation of the discrete problem performed worse than direct discrete search
AI and co-simulation driven resource management in fog computing environments · Imperial
Considered and rejected
Considered and rejected: Rejected treating discrete/categorical variables as continuous inputs rounded post-hoc, as it degrades optimization efficiency in structured/conditional search spaces.
Sequential black-box optimization via global optimization of tree ensembles · Imperial
Greedy heuristics and myopic search strategies yield suboptimal bounds, local traps, or training instability
Natural greedy selection rules fail to achieve optimal competitive ratios and frequently become trapped in local maxima compared to stochastic sampling. Moreover, greedy rollouts and low-iteration samples introduce high variance and algorithmic divergence during dynamic optimization and reinforcement learning.
Tried and failed
greedy heuristics for combinatorial scheduling applied to online matching and flow problems. Outcome: worse than baseline. Reason: natural greedy choices fail to achieve optimal competitive ratios, yielding poor worst-case approximation bounds
Designing Networks, Routing Fleets, and Trying to Find Parking · Cornell
Tried and failed
greedy deterministic search in discrete optimization applied to adversarial text generation. Outcome: worse than baseline. Reason: frequently trapped in local maxima compared to stochastic sampling
Tried and failed
greedy rollout baseline in policy optimization applied to reinforcement learning for combinatorial optimization. Outcome: unstable. Reason: frequently diverged early in training compared to using learned value critic networks
Complexity Scaling Laws for Neural Models using Combinatorial Optimization · Virginia Tech
Tried and failed
greedy optimization with low sample iterations applied to stochastic discrete-event resource allocation. Outcome: unstable. Reason: insufficient iterations per step caused high variance and failed to converge stably across large parameter spaces
Analyzing Sparing Policy in the Operations of Space Habitats · Georgia Tech
Learning-based policies and general metaheuristics fail to outperform standard baselines or specialized combinatorial solvers
Methods such as proximal policy optimization, genetic programming, and constraint programming were beaten by greedy heuristics, integer programming, and exhaustive search in reliability and speed. Similarly, proposed optimization frameworks failed to reach the solution quality and execution times achieved by established solvers like Tabu Search and GRASP.
Tried and failed
proximal policy optimization reinforcement learning applied to sequential dynamic combinatorial resource allocation. Outcome: worse than baseline. Reason: PPO-based policies failed to outperform greedy dynamic heuristics and static integer programming baselines on large instances
Lost to a baseline
Exhaustive search outperformed genetic programming in reproducibility and execution reliability despite higher theoretical combinatorial scale.
Strukturidentifikation und Unterscheidbarkeit von Modellen für elektromechanische Antriebsstränge · Leibniz Universität Hannover Repository
Lost to a baseline
Average solution quality and solution times did not match specialized combinatorial methods like Tabu Search and GRASP.
A Model for Combinatorial Optimization using Neural Networks and Object-Oriented Programming · TXST Digital Repository
Tried and failed
constraint programming for combinatorial optimization applied to large-scale grid asset planning. Outcome: worse than baseline. Reason: Failed to reach optimality within time limit compared to mixed-integer programming.
Advanced Techno-Economic and Sustainability Analysis Methods of Emerging Grid Technologies · Georgia Tech
State-space pruning rules prematurely eliminate optimal candidates and degrade solution quality
Applying pruning operations to dynamic programming and small discrete search spaces prematurely cuts off valid sub-tours and critical search paths. This loss of capacity causes underfitting and sacrifices global optimality across combinatorial routing and partitioning problems.
Tried and failed
search space pruning applied to small discrete optimization problems. Outcome: worse than baseline. Reason: pruning operations reduced capacity in small instance spaces, causing underfitting and suboptimal solutions
PLATFORM-DRIVEN CROWDSOURCED MANUFACTURING FOR MANUFACTURING AS A SERVICE · Georgia Tech
Tried and failed
dynamic programming state-space pruning heuristic applied to combinatorial route partitioning problems. Reason: pruning rules prematurely eliminated valid sub-tours, sacrificing global optimality
Developing efficient order and split heuristics for coordinated covering tour problems with drones · Texas Tech
Left open by the authors
Problems the authors named and did not get to.
Left open
Implement and benchmark alternative heuristic tree search algorithms beyond MCTS and weighted BFS within the combinatorial curriculum learning framework. Blocker: None
Deep Combinatorial Reasoning: From Games To Scientific Discovery · Cornell
Left open
Develop a theoretical framework explaining parameter-constrained complexity scaling laws and predicting model capacity breakdown points in combinatorial optimization. Blocker: No concrete mathematical approach or formalized hypotheses are provided to guide theoretical development.
Complexity Scaling Laws for Neural Models using Combinatorial Optimization · Virginia Tech
Left open
Develop low-dimensional dynamic programming coordinate descent algorithms over subgraphs for discrete planning problems. Blocker: Lacks detailed algorithmic specification and concrete benchmark targets for the discrete planning subgraph formulation
Efficient Learning and Inference for High-dimensional Lagrangian Systems · Penn
Left open
Extend gradient-based policy-based Bayesian experimental design optimization to discrete design spaces. Blocker: None
Automated data acquisition via Bayesian experimental design · Oxford
Left open
Extend MetaPG symbolic evolution of actor-critic loss functions to discrete action spaces and benchmark on standard discrete RL environments. Blocker: None
Robustness of Reinforcement Learning Systems in Real-World Environments · MIT
Left open
Extend unsupervised TSP learning concepts and Scattering Attention GNN architectures to solve additional graph combinatorial optimization problems. Blocker: The unfinished work lacks specific target combinatorial problems and detailed architectural adaptations.
DEEP UNSUPERVISED MODELS LEVERAGING LEARNING AND REASONING · Cornell
Left open
Reformulate continuous pre-disaster hardening optimization into an integer program by selecting discrete candidate subsets of power and water infrastructure links. Blocker: None
Disaster preparedness and restoration of interconnected infrastructure systems · UT Austin
Checking a claim in this area?
We can run the same search on any method or claim. If nothing turns up, we will say so, and that proves nothing on its own.