Feedback control for real-time solving

• Constraint Programming 2004 International Workshop on Constraint Solving under Change and Uncertainty

Numerous solvers have been proposed to solve constraint satisfaction problems (CSPs) or constrained optimization problems (COPs). Research has demonstrated that solvers' performance is instance-dependent and that no single solver is the best for all problem instances. In this paper, we further demonstrate that solvers' relative performance is time-dependent and that, given a problem instance, the best solver varies for different solving time bounds. We investigate an on-line feedback control paradigm for solver or problem reconfiguration so that the solver can reach the best possible solution within a specified time. Our framework is unique in specifically considering the time constraint in the feedback control of solving. With this augmented time-adaptivity, our paradigm improves solver performance for real-time applications. As a case study, we apply the feedback control paradigm to real-time performance control of a multidimensional knapsack problem solver.

citation

Lu, Y.; Crawford, L. S. ; Ruml, W. ; Fromherz, M. P. J. Feedback control for real-time solving. Constraint Programming 2004 International Workshop on Constraint Solving under Change and Uncertainty; 2004 September 27; Toronto; Canada.