Sep 2026· Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence· pp. 2265-2272· 0 citations· 21 references
TL;DR
A new solver is developed, ULE-MWC (UnLocking Enhanced MWC), which consistently yields tighter upper bounds and outperforms state-of-the-art exact solvers in both runtime and search efficiency.
Abstract
The Maximum Weight Clique Problem (MWCP) is NP-hard and is typically solved exactly within a Branch-and-Bound (BnB) framework, where the quality of upper bounds critically determines the pruning efficiency. Recent solvers enhance independent-set-based bounds using MaxSAT reasoning. However, their effectiveness is limited by two inherent limitations: (i) independent sets in conflicts are discarded after a single use, preventing their reuse in subsequent reasoning; and (ii) conflicts are detected in a fixed order regardless of their potential contribution to bound tightening. To address these issues, we propose two complementary techniques. The UnLocking Mechanism (ULM) preserves conflict cores and enables the reuse of independent sets in subsequent reasoning, while the Benefit-Enhanced Strategy (BES) steers the MaxSAT reasoning process toward conflicts and independent sets with higher pruning potential. By integrating ULM and BES, we develop a new solver, ULE-MWC (UnLocking Enhanced MWC). Experimental results on standard benchmarks show that ULE-MWC consistently yields tighter upper bounds and outperforms state-of-the-art exact solvers in both runtime and search efficiency.
The Dual-GNN Multilevel Coarsening framework uses learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making and achieves the best mean solution quality among all evaluated methods.
K-adaptive Ensembled Partitioning (KEP) is presented, which combines recursive bisection and direct 𝐾 -way search and replaces hard-feasibility Fiduccia–Mattheyses (FM) with an augmented-Lagrangian refinement step (AL-FM) that can cross short infeasible regions before repairing balance.
Efficient resource use in packing and assembly-line applications requires decisions that jointly account for capacity and precedence constraints. The strongly NP-hard bin packing problem with generalized precedence constraints (BPP-GP) models such decisions by minimizing the number of ordered, capacitated bins required...
Sunkanghong Wang, Zheng-Zhong You, Roberto Baldacci et al.· 0 citations
This paper proposes and formalizes two new minimization algorithms that guarantee subset-minimal reasons and ensures cardinality-minimal reasons in the AMOSUM constraint and demonstrates that extending the solver wasp with these minimization strategies leads to substantial performance improvements.
Test-time reasoning systems often respond to failure by restarting or revising the latest step, even when an earlier decision caused the error. We introduce CORE, a search controller that requests a certified conflict core from a verifier, backjumps to the latest decision in that core, and caches the conflict to avoid...
Si-Yu Song, Rui-Peng Xu, Jia Lin et al.· arXiv.org· 0 citations
We revisit the capacitated $k$-median problem, focusing on constant-factor approximation algorithms with either $(1+\epsilon)$-cardinality or capacity violations. Previous results [DemirciL16, Li16} achieve an $O_\epsilon(1)$-approximation with $(1+\epsilon)$-violations via complex extended configuration linear program...
Han Dai, Shi Li· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.