Ying Lu, Lara S. Crawford, Wheeler Ruml, and Markus P.J. Fromherz
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 bound. 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.