fork download 
  1. import numpy as np
  2. from scipy.optimize import minimize
  3. from functools import lru_cache 
  4. import scipy
  5.  
  6.  
  7. k = 3
  8. m = 420
  9. p = 6
  10.  
  11. def Evaluate(cs, reps=200):
  12.     assert m%p == 0
  13.  
  14.     C = [[cs[outer + inner] for inner in range(p-1, -1, -1) for _ in range(m//p)] for outer in range(0, len(cs)-1,p)]
  15.     C = np.array(C)
  16.  
  17.     @lru_cache(maxsize=None)
  18.     def dp(b, j, i, l):
  19.         if j>=k or i>=m:
  20.             return b
  21.  
  22.         if l<=C[j, i]:
  23.             ans = np.exp(-C[j,i]/m)*dp(b, j, i+1, l) + (1-np.exp(-C[j,i]/m))*(
  24.                 l/C[j, i] * dp(1, j+1, i+1, l) + (C[j, i]-l)/C[j, i] * dp(0, j+1, i+1, l))
  25.         else:
  26.             ans = np.exp(-C[j,i]/m)*dp(b, j, i+1, l) + (1-np.exp(-C[j,i]/m))*dp(1, j+1, i+1, l)
  27.         return ans
  28.  
  29.     def cost(l):
  30.         l = l[0]
  31.         return  dp(0, 0, 0, l)/(1-np.exp(-l))
  32.  
  33.     """Run global optimization on cost in the range (0, max(C)]"""
  34.     res = scipy.optimize.shgo(cost, bounds=[(0.000000000000001,C.max())], iters=10,  options={'disp':False, 'f_tol':1e-9})
  35.  
  36.     competitive_ratio = min(res.fun, 1-np.exp(-sum(C[0])/m)) #do not forget l'>max(C) case
  37.  
  38.     "As a sanity check, make sure that global minimizer succeeded"
  39.     ls = np.linspace(0.000000000000001, C.max(), reps)
  40.     ans = 1
  41.     for l in ls:
  42.         ans = min(ans, cost([l]))
  43.  
  44.     assert res.fun <= ans
  45.     """End of sanity check"""
  46.  
  47.     return competitive_ratio
  48.  
  49. cs0 = [3.64589394e+00, 3.58116098e+00, 2.03323633e+00, 1.93319241e+00,
  50.        1.15603731e+00, 9.92652855e-01, 6.10147568e-01, 3.94833386e-01,
  51.        2.41093283e-01, 1.36659577e-01, 4.80563875e-02, 2.83455285e-02,
  52.        8.39298670e-02, 1.91858842e-02, 0.00133218127, 1.33218127e-03,
  53.        1.05769060e-03, 1.05769044e-03]
  54.  
  55.  
  56. competitive_ratio = Evaluate(cs0, reps=5000) #Takes around a minute 
  57.  
  58. print(competitive_ratio)
  59.  
Time limit exceeded #stdin #stdout 5s 147644KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ez3tKW
language:
Python 3 (python  3.12)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!