Unimodular Probing for Minimal Perturbance in Dynamic Resource Feasibility Problems

. This paper describes unimodular probing -- a new technique that has been used to solve a class of dynamic scheduling problems. In benchmarks a unimodular probing algorithm has outperformed two wellestablished approaches: backtrack search with local consistency and specialised heuristics, and mixed integer programming (MIP). The problems amenable to unimodular probing involve disjunctive constraints, discrete variables, and a linear optimisation function. In addition, some of the constraints should be totally unimodular -- for example, temporal precedence and distance constraints. Problems in this class are difficult for CSP techniques because of the optimisation requirement, and for MIP because of the number of discrete (integer) variables. Our studies have focussed on DCSPs, with an optimisation criterion of minimal perturbance to an existing solution. Unimodular probing builds on an ordinary backtracking repair algorithm with constraint propagation. However, by contrast with previo..