Real-time solving of computationally hard problems using optimal algorithm portfolios
- PDF / 745,533 Bytes
- 18 Pages / 439.642 x 666.49 pts Page_size
- 7 Downloads / 148 Views
Real-time solving of computationally hard problems using optimal algorithm portfolios Yair Nof1
· Ofer Strichman1
© Springer Nature Switzerland AG 2020
Abstract Various hard real-time systems have a desired requirement which is impossible to fulfill: to solve a computationally hard optimization problem within a short and fixed amount of time T , e.g., T = 0.5 seconds. For such a task, the exact, exponential algorithms, as well as various Polynomial-Time Approximation Schemes, are irrelevant because they can exceed T . What is left in practice is to combine various anytime algorithms in a parallel portfolio. The question is how to build such an optimal portfolio, given a budget of K computing cores. It is certainly not as simple as choosing the K best performing algorithms, because their results are possibly correlated (e.g., there is no point in choosing two good algorithm for the portfolio if they win on a similar set of instances). We prove that the decision variant of this problem is NP-complete, and furthermore that the optimization problem is approximable. On the practical side, our main contribution is a solution of the optimization problem of choosing K algorithms out of n, for a machine with K computing cores, and the related problem of detecting the minimum number of required cores to achieve an optimal portfolio, with respect to a given training set of instances. As a benchmark, we took instances of a hard optimization problem that is prevalent in the real-time industry, in which the challenge is to decide on the best action within time T . We include the results of numerous experiments that compare the various methods. Hence, a side effect of our tests is that it gives the first systematic empirical evaluation of the relative success of various known stochasticsearch algorithms in coping with a hard combinatorial optimization problems under a very short and fixed timeout. Keywords Algorithm portfolios · NP-optimization · Real-time Mathematics Subject Classification (2010) 68T20
Yair Nof
[email protected] Ofer Strichman [email protected] 1
Information Systems Engineering, Technion, Haifa, Israel
Y. Nof, O. Strichman
1 Introduction Hard real-time systems frequently have a seemingly impossible requirement: To solve within a short, fixed amount of time T (e.g., T = 0.5 second), a computationally hard optimization problem. For example, a centrally-controlled team of robots playing soccer need to make split-second decisions, but those decisions are subject to hard constraints such as not walking into each other or not hitting a teammate with the ball. Since there are multiple players and each has multiple options, the number of combinations grow exponentially with the number of players. Another example is a fleet of drones with a central control. The fleet has to fly in an urban area and hence react to the environment, and make decisions in real-time. Those decisions are subject to both hard constraints (e.g., not to collide) and to soft objectives, such as minimizing the time to complete the mi
Data Loading...
