Research map / Learning theory and algorithms / Combinatorial and search optimization
What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization
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.
Gives an exact geometric characterization of which datasets (linear queries on the cost vector) suffice to recover an optimal LP decision under a convex open cost uncertainty set, and an MILP-based algorithm to build minimal sufficient datasets.
Problem
Determining which datasets are sufficient to recover a task-optimal decision for a linear program when the cost vector is unknown but lies in a known uncertainty set, and constructing minimal such datasets.
Approach
Sufficiency is characterized by whether the dataset's span contains the relevant extreme directions (or equivalently the span of differences between reachable optimal solutions over the uncertainty set); this yields an iterative MILP-based algorithm that builds a minimal basis of these directions and selects canonical queries accordingly.
Key results
- In the hiring application (100 candidates, hire 20), the minimal sufficient dataset size increases with noise level, e.g. 8, 24, 31, 52 interviews across increasing noise for the vanilla setting.
- For the experience-constrained setting the sizes are 8, 28, 43, 70 across increasing noise, showing that the high-noise experience-constrained case needs more data than the vanilla case.
- Proposition on noisy observations: least-squares estimate of cost yields optimal decisions when noise norm is below a threshold depending on the sufficient dataset.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase noise in the cost uncertainty set | Data selection algorithm for vanilla hiring · Vanilla hiring, noise settings from left to right | number of interviews: 8,24,31,52 | Hurt |
| Increase noise in the cost uncertainty set | Data selection algorithm for experience-constrained hiring · Experience-constrained hiring, noise settings from left to right | number of interviews: 8,28,43,70 | Hurt |
| Add experience-group hiring constraints | Data selection algorithm · High-noise hiring | number of interviews: 52 -> 70 | Hurt |
Surprising findings
- Adding decision constraints (experience quotas) can require more data than the vanilla task in the high-noise regime, despite the smaller feasible set.
Limitations
- Restricted to linear programs; extension to MIP or convex programs left open.
- Query sets assumed to be basis vectors or a basis; general queries are a hard problem.
- Theory covers only open convex uncertainty sets; discrete or low-dimensional sets excluded.
Experimental setup
Datasets: synthetic hiring instances (100 candidates, GPA in [2,4], experience in {1..5})
Metrics: number of candidates to interview (dataset size)
Builds on: Blackwell informativeness complementary slackness Algorithms with predictions
Closest papers by meaning
- Solver-Free Decision-Focused Learning for Linear Optimization Problems (NeurIPS 2025 · similarity 0.87)
- Statistical Methodologies for Decision-Making and Uncertainty Reduction in Machine Learning (AAAI 2025 · similarity 0.86)
- Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index (NeurIPS 2024 · similarity 0.85)
- Decision Theoretic Foundations for Conformal Prediction: Optimal Uncertainty Quantification for Risk-Averse Agents (ICML 2025 · similarity 0.85)
- Leaving the Nest: Going beyond Local Loss Functions for Predict-Then-Optimize (AAAI 2024 · similarity 0.85)
- Using Noise to Infer Aspects of Simplicity Without Learning (NeurIPS 2024 · similarity 0.85)
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.