Research map / Learning theory and algorithms / Combinatorial and search optimization
Using Clustering to Strengthen Decision Diagram Bounds for Discrete 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.
Proposes clustering-based node selection (k-means on DP states) for compiling relaxed and restricted approximate decision diagrams, outperforming the sortObj objective-based baseline on knapsack and scheduling problems.
Problem
Node selection (which nodes to merge or discard when a DD layer exceeds maximum width) strongly affects primal and dual bounds from approximate decision diagrams, and generic sorting-based heuristics often merge dissimilar states.
Approach
Cluster the nodes of each DD layer with k-means on their DP state vectors; merge nodes within each cluster for relaxed DDs, or keep the best-objective node per cluster for restricted DDs, giving a generic, problem-agnostic node selection rule.
Key results
- On 0/1 knapsack, clustering-based node selection gives substantially better primal and dual bounds than sortObj at smaller maximum width and lower computation time.
- On 1||sum w_j U_j with 500-job instances, clustering with W=100 reaches a dual bound of 0.14 in 0.1 s versus sortObj's 0.23 at W=2000 time 0.05 s style comparisons; Gurobi IP gave far weaker bounds after 120 s.
- Using k < W clusters preserves bound quality noticeably while reducing DD size and running time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use clustering-based node selection instead of sortObj | Approximate DD compilation · KP, MKP, P2||ΣC³j, P2||ΣwjCj, and 1||ΣwjUj | bound quality | Helped |
| Set the number of clusters k below the maximum width W (ablation) | Clustering-based node selection for KP · KP | bound quality | No clear effect |
| Set the number of clusters k below the maximum width W (ablation) | Clustering-based node selection for KP · KP | DD size | Helped |
| Set the number of clusters k below the maximum width W (ablation) | Clustering-based node selection for KP · KP | compilation time | Helped |
Surprising findings
- Setting k smaller than W (clustering only in some layers) does not noticeably degrade bound quality while reducing DD size and runtime.
Limitations
- Only k-means clustering evaluated in main results; other clustering methods gave high variance.
- Evaluated only as bounding within DD compilation, not within an exact DD-based branch-and-bound solver.
Experimental setup
Datasets: Pisinger 0/1 knapsack instances (100 instances, 200 items) Chu and Beasley MKP instances (10 instances, 5 dimensions, 100 items) OR-Library wt100 job instances (125 instances, 100 jobs) Tanaka et al. 1||sum wjUj instances (25 instances, 500 jobs)
Benchmarks: 0/1 knapsack multidimensional knapsack P2||sum C_j^3 P2||sum w_j C_j 1||sum w_j U_j
Metrics: primal bound dual bound DD size (maximum width) running time
Baselines: sortObj IP (Gurobi)
Builds on: approximate decision diagrams (Bergman et al.) DP by reaching sortObj node selection
Closest papers by meaning
- Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms (ICML 2025 · similarity 0.86)
- Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning (AAAI 2025 · similarity 0.83)
- Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · similarity 0.83)
- Bayesian Optimization of Functions over Node Subsets in Graphs (NeurIPS 2024 · similarity 0.83)
- Solver-Free Decision-Focused Learning for Linear Optimization Problems (NeurIPS 2025 · similarity 0.83)
- OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling (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.