Conflict-Weighting Variable Selection in Reactive Multi-Objective Job-Shop and RCPSP
Abstract Conflict-weighting variable selection (dom/wdeg and its descendants) is central to constraint-programming (CP) search for scheduling, yet its variants are easily conflated, and their behaviour under repeated multi-objective re-solving of perturbed snapshots with long-scope propagators (noOverlap, cumulative) had not been characterised. We first make the weight-increment rules explicit: crediting a propagator failure to the entire scope of the failing constraint is the original dom/wdeg rule of 2004, as implemented by Choco's domOverWDegSearch; per-variable attribution is a later refinement. We compare scope-sharing, per-variable weighting, and a History of Decisions (HD) augmentation in a single Choco harness where only the increment rule varies, on 162 standard job-shop and PSPLIB Resource-Constrained Project Scheduling Problem (RCPSP) instances with paired seeds and five reactive snapshots (159 form the test set). Three findings emerge: scope-sharing coincides with Choco dom/wdeg up to tie-breaking; measured instantaneous scope-freshness is low, making the sufficient high-freshness convergence bound vacuous on these benchmarks, and direct search-tree measurements show the two rules are not interchangeable in the tested regime; and HD leaves hypervolume unchanged while reducing search effort on the RCPSP instances where proofs close. Against contextual priority-rule Non-dominated Sorting Genetic Algorithm (NSGA-II/III) baselines at an equal per-snapshot budget, the CP selectors attain higher hypervolume and far lower internal solver time on RCPSP only; NSGA leads on job-shop hypervolume, a gap that persists when its fronts are capped to the CP front cardinality. Conflict-weighting gains are thus family-dependent; we provide the controlled, reproducible benchmark that delimits where the variants genuinely differ.
Authors
- Madani Bezoui (ORCID: https://orcid.org/0000-0001-6930-1088)
- Lillia Ouali
- Kamal Amroun (ORCID: https://orcid.org/0000-0002-4259-2783)
Institutions
- University of Béjaïa (DZ)
Publication Details
- Journal
- Research Square
- Published
- 2026-11-13
- DOI
- https://doi.org/10.21203/rs.3.rs-10008411/v1
- Primary Topic
- Constraint Satisfaction and Optimization
- Type
- preprint