|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.