Feedback control for real-time solving
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.
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.