Long-Term Reliability of Nanometer VLSI Systems by Sheldon Tan & Mehdi Tahoori & Taeyoung Kim & Shengcheng Wang & Zeyu Sun & Saman Kiamehr

Author:Sheldon Tan & Mehdi Tahoori & Taeyoung Kim & Shengcheng Wang & Zeyu Sun & Saman Kiamehr
Language: eng
Format: epub
ISBN: 9783030261726
Publisher: Springer International Publishing

10.3.4 Time Complexity Analysis

It has been proved that MILP problems are NP hard. Though branch and bound techniques can be used to solve the problem, the time complexity is not easy to analyze as we use commercial CPLEX as the solver. For the Q-learning, each value iteration can be performed in O(|A||S|2) steps, or faster if there is sparsity in the transition function (where A is a number of actions and S is a number of states). In practice, policy iteration converges in fewer iterations than value iteration, and there is no known tight worst-case bound available [34]. As a result, we report the running CPU times of Q-learning and MILP in our experiments with more p-states in Table 10.3 in Sect. 10.4 to compare the time complexities of the two methods. We further remark that it is rather difficult to fairly compare CPU times for these two optimization methods as the Q-learning was running on Python, whereas the MILP was running on commercial CPLEX Optimizer. Nevertheless, the numerical results still show that MILP has much higher computation cost than the Q-learning method. Table 10.3Elapsed CPU time to solve the proposed Q-learning and MILP problems [31]

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.