Library · Optimization & control
What Combinatorial & Discrete Optimization got wrong, from 26 theses
Summary written by a model from the records below: Across the records, discrete and combinatorial optimization approaches frequently encounter severe runtime intractability or fail when continuous relaxations and post-hoc rounding distort problem structures. In addition, greedy heuristics and complex learning algorithms often fall into local optima or underperform established combinatorial baselines and exact solvers. These records come from graduate theses, 2021 to 2026, each labeled with its degree where the repository states it, and 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.
Plus 6 problems the authors left open, listed at the end.
Failure modes, by theses reporting them
Select a mode to jump to its records.
Exact mathematical formulations and brute force combinatorial searches suffer from combinatorial explosion and prohibitive runtimes
Exact mixed integer programming solvers, path-based models, and graph searches failed to converge or timed out on medium and large problem instances due to combinatorial explosion. Researchers repeatedly rejected exact brute force searches and complex precedence formulations in favor of polynomial-time constructions and greedy sequential 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 · PhD
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 · PhD
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 · PhD
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 · PhD
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 · PhD
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.
Advancing AI for Incentive-Aligned Systems · Harvard · PhD
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 · Master's
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 · Master's
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 · PhD
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 · University College Dublin · PhD
Continuous relaxations and post-hoc rounding degrade solution quality on discrete search spaces
Applying continuous gradient optimization, continuous relaxations, or post-hoc rounding introduced severe distortion and generated invalid trajectory vectors on discrete problem instances. These continuous approximations handled discrete feature transitions poorly and performed worse than direct discrete search strategies.
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 · PhD
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 · Doctorate
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 · PhD
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 · PhD
Tried and failed
interpolating discrete game formulations to continuous spaces applied to multi-agent pursuit-evasion games. Outcome: worse than baseline. Reason: discrete approximations to continuous games yield suboptimal payoff bounds
PERIMETER DEFENSE WITH MULTI-ROBOT SYSTEMS · Penn · PhD
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 · PhD
Greedy and deterministic search heuristics get trapped in local optima or exhibit instability
Deterministic greedy choices failed to achieve optimal competitive ratios and frequently became trapped in local maxima compared to stochastic alternatives. Greedy rollout baselines and low-sample iterations also suffered from high variance, causing early training divergence and convergence failures.
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 · PhD
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
Towards Deployable Robust Text Classifiers · MIT · PhD
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 · Master's
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 · PhD
Considered and rejected
Considered and rejected: Rejected an optimization-based single-sector approach in favor of discrete-choice simulation, as single-sector optimization leads to unrealistic local optima and cannot represent heterogeneous adoption behaviors under data scarcity.
Transformation of Europe's energy-intensive industry sites : a model-based assessment of diffusion dynamics · TU Wien · PhD
Complex reinforcement learning and metaheuristics fail to outperform established combinatorial baselines
Reinforcement learning, genetic programming, and generic constraint programming failed to outperform simpler integer programming baselines, dynamic greedy heuristics, or exhaustive search. The proposed learning and search techniques also failed to match the solution quality and execution speeds of specialized combinatorial methods such as Tabu Search and GRASP.
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 · PhD
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 · PhD
State space pruning and discrete convexity assumptions sacrifice optimality or fail to generalize
Pruning rules applied to dynamic programming and discrete instance spaces prematurely eliminated valid sub-tours or caused underfitting, sacrificing global optimality. In addition, discrete convexity local search failed to generalize because the underlying convexity assumptions broke down under heterogeneous arrival flows and network routing dependencies.
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 · PhD
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 · PhD
Tried and failed
discrete convexity optimization via local search applied to multi-station stochastic network scheduling. Outcome: did not generalise. Reason: discrete convexity does not hold under heterogeneous arrival flows and network routing dependencies
Innovation models in value-based health care · UT Austin · PhD
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 · PhD
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 · Master's
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 · PhD
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 · PhD
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 · PhD
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 · PhD
Who has worked on this
Authors of the public theses cited on this page, most-cited first.
- Lowell Meyer Weissman · Virginia Tech · Master's · 2025
Complexity Scaling Laws for Neural Models using Combinatorial Optimization - Yanchen Jiang · Harvard · PhD · 2026
Advancing AI for Incentive-Aligned Systems - Min Ru Wang · EPFL · PhD · 2026
Optimization of on-demand shared mobility: passenger and freight applications - Yiming Chen · Georgia Tech · PhD · 2025
Advanced Techno-Economic and Sustainability Analysis Methods of Emerging Grid Technologies - Aobo Chen · Iowa State · Master's · 2025
Enhancing medical image classification via uncertainty estimation - Marius Neuwirth · TU Wien · PhD · 2025
Transformation of Europe's energy-intensive industry sites : a model-based assessment of diffusion dynamics - Austin Ku Chen · Penn · PhD · 2024
PERIMETER DEFENSE WITH MULTI-ROBOT SYSTEMS - Mathias Tantau · Leibniz Universität Hannover · PhD · 2024
Strukturidentifikation und Unterscheidbarkeit von Modellen für elektromechanische Antriebsstränge - DR Ivanova · Oxford · PhD · 2024
Automated data acquisition via Bayesian experimental design - Dieqiao Feng · Cornell · PhD · 2023
Deep Combinatorial Reasoning: From Games To Scientific Discovery - Juan José Garau Luis · MIT · PhD · 2023
Robustness of Reinforcement Learning Systems in Real-World Environments - Alexander Thebelt · Imperial · PhD · 2023
Sequential black-box optimization via global optimization of tree ensembles
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.