Feedback Control for Real-time Solving
Ying Lu, Lara S. Crawford, Wheeler Ruml, and Markus P.J. Fromherz
Abstract
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.
PDF file
Back to the top.