Research map / Learning theory and algorithms / Combinatorial and search optimization
Towards More Practical and Efficient Automatic Dominance Breaking
Jimmy H.M. Lee, Allen Z. Zhong
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Common Assignment Elimination to nogood generation (ablation) | Automatic dominance breaking · Knapsack, DisjKnapsack, KnapsackSide, ConcertSched, MaxCut | generation time: up to 37.29% between 2-dom and 2-dom(*); up to 69.68% between 3-dom and 3-dom(*) and up to 90.08% between 4-dom and 4-do | Improved |
| Add Common Assignment Elimination to nogood generation (ablation) | Automatic dominance breaking · PCBoard | generation time: 4-dom(*), 5-dom(*) and 6-dom(*) reduce up to 72.40%, 76.55% and 89.75% generation time | Improved |
| Add Common Assignment Elimination to 2-dom (ablation) | Automatic dominance breaking · ConcertSched | total time: at most 12.08% | Improved |
| Add Common Assignment Elimination to 4-dom (ablation) | Automatic dominance breaking · MaxCut | total time: up to 49.58% less than 4-dom | Improved |
| Add Common Assignment Elimination to nogood generation (ablation) | Automatic dominance breaking · Knapsack, DisjKnapsack, KnapsackSide | total time: at least 28.44% and at most 65.57% | Improved |
| Add Common Assignment Elimination to nogood generation (ablation) | Automatic dominance breaking · PCBoard | total time: up to 88.48% | Improved |
| Use 6-dom(*) instead of 5-dom (ablation) | Automatic dominance breaking · PCBoard | average total time: 2449.26 seconds | Improved |
| Add Common Assignment Elimination to 6-dom (ablation) | Automatic dominance breaking · PCBoard | average total time: 3034.01 seconds | Improved |
| Generate nogoods with CAE rather than without CAE (ablation) | Automatic dominance breaking · Knapsack, DisjKnapsack, KnapsackSide | problem solving time | No clear effect |
| Generate more nogoods after applying CAE when both 4-dom variants time out (ablation) | Automatic dominance breaking · Knapsack, KnapsackSide | problem solving time | Hurt |
| Generate more nogoods after applying CAE when both 4-dom variants time out (ablation) | Automatic dominance breaking · DisjKnapsack | problem solving time | Improved |
| Skip implied-satisfaction checks for non-EC constraints whose variables are outside the candidate nogood scope | Automatic dominance breaking · KnapsackSide | solving speed | Improved |
Closest papers by meaning
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.82)
- Exploiting Symmetries in MUS Computation (AAAI 2025 · similarity 0.82)
- Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction (ICML 2025 · similarity 0.81)
- EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulations (ICML 2025 · similarity 0.81)
- On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? (AAAI 2024 · similarity 0.81)
- Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity (AAAI 2025 · similarity 0.81)
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.
