The paper introduces the Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling (MSABL/MSCABL) problems, which fix a minimum (cyclic) distance between adjacent vertex labels and aim to minimize the overall label span. A unified Boolean Satisfiability (SAT) framework is developed, formulating the problems as a sequence of decision problems and exploiting monotonicity to accelerate search. Two SAT solving strategies—parallel and incremental—are evaluated on benchmark instances from the Harwell‑Boeing Sparse Matrix Collection and compared with commercial solvers, showing that SAT-based approaches are highly competitive, with the parallel method best for MSCABL and the incremental method best for MSABL.
By Hieu Truong Xuan, Khanh To Van
arXiv:2606. 06656v1 Announce Type: new Abstract: We study parallel Continuous Local Search (CLS) as a solution approach for Boolean satisfiability problems with symmetric pseudo-Boolean (PB) constraints.
By Cody J Christopher, Charles Gretton
arXiv:2607. 23785v1 Announce Type: cross Abstract: The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints.
By Johannes K. Fichte, Johanna Groven, Peter Jonsson, Victor Lagerkvist, Jorke M. de Vlas
The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MAXSTP: compute a maximum-cardinality consistent subset of constraints.
arXiv:2606. 06641v1 Announce Type: new Abstract: We present Accelerated Fourier SAT (AFSAT), a GPU-accelerated solver for pseudo-Boolean satisfiability based on continuous local search (CLS).
By Cody J Christopher, Charles Gretton
arXiv:2608. 15143v1 Announce Type: new Abstract: Constraint solving is a declarative approach for solving combinatorial satisfaction and optimization problems.
By Tias Guns, Ignace Bleukx, Hendrik Bierlee, Jo Devriendt, Emilio Gamba, Orestis Lomis, Wout Piessens, Thomas Sergeys, Dimos Tsouros, Wout Vanroose, H\'el\`ene Verhaeghe
arXiv:2607. 07204v1 Announce Type: cross Abstract: Optimization geometrodynamics views optimizer state as evolving geometry.
By Zavier Li
arXiv:2606. 05956v1 Announce Type: new Abstract: Bidirectional heuristic search can potentially reduce search effort for problems amenable to backward search.
By Tzur Shubi, Ariel Felner, Solomon Eyal Shimony, Shahaf S. Shperberg
Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs. Existing neural--operations-research (OR) hybrids predict guidance without requiring learned transitions to satisfy constraints discovered during search.
arXiv:2602. 21312v4 Announce Type: replace-cross Abstract: This work considers a number of optimization problems and reductive relations between them.
By Micha{\l} Szyfelbein, Dariusz Dereniowski
arXiv:2608. 09042v1 Announce Type: new Abstract: Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs.
By Yancheng Song, Yongzhi Qi, Wei Qi, Zuo-Jun Max Shen
arXiv:2606. 07403v1 Announce Type: cross Abstract: Benders decomposition is a fundamental framework for solving large-scale mixed-integer optimization problems with complicating variables that, when fixed, yield significantly easier subproblems.
By Changkun Guan, El Mehdi Er Raqabi, Mathieu Tanneau, Pascal Van Hentenryck