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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Conflict-Weighting Variable Selection in Reactive Multi-Objective Job-Shop and RCPSP

Madani Bezoui, Lillia Ouali, Kamal Amroun
1 links
Research Square
Constraint Satisfaction and Optimization
preprint

Conflict-Weighting Variable Selection in Reactive Multi-Objective Job-Shop and RCPSP

Madani Bezoui, Lillia Ouali, Kamal Amroun
preprint en

Abstract

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.

Research Square
University of Béjaïa (DZ)
Constraint Satisfaction and Optimization
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon