טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentNof Yair
SubjectReal Time Solving of Discrete Optimization Problems
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Ofer Strichman
Full Thesis textFull thesis text - English Version


Abstract

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.