M.Sc Student | Nof Yair |
---|---|

Subject | Real Time Solving of Discrete Optimization Problems |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Ofer Strichman |

Full Thesis text |

Many 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. For such a task,
the exact, exponential algorithms are out of scope. Polynomial-Time
Approximation Schemes guarantee a *1-epsilon* approximation with a
polynomial run-time, but this run-time can easily exceed the short and fixed
requirement. In this thesis we define the `*fixed-time variant'* of a hard
optimization problem, based on giving weights to the hard constraints. In
practice only any-time algorithms are relevant for such tasks.

We define a concrete optimization
problem that we call *RAFP* and prove that its decision variant is
NP-complete. We then study the performance of several probabilistic algorithms
(most of them are local-search) that we fit to *RAFP*'s fixed-time
variant, with very short time bounds. We study the practical impact of
automatically tuning the parameters of those algorithms. In addition, we
consider the problem of optimizing a parallel portfolio of algorithms.
Specifically, we study the 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 benchmarks. The thesis includes the
results of numerous experiments that compare the various methods.