diff options
| -rw-r--r-- | src/act4e_mcdp_solution/solver_dp.py | 52 |
1 files changed, 40 insertions, 12 deletions
diff --git a/src/act4e_mcdp_solution/solver_dp.py b/src/act4e_mcdp_solution/solver_dp.py index 4a573b3..dfcfc90 100644 --- a/src/act4e_mcdp_solution/solver_dp.py +++ b/src/act4e_mcdp_solution/solver_dp.py @@ -699,12 +699,13 @@ class DPSolver(DPSolverInterface): if len(us) < 2: return us - def poset_max(m1: RT, m2: RT) -> RT: - return m1 if poset.geq(m1, m2) else m2 + # def poset_max(m1: RT, m2: RT) -> RT: + # return m1 if poset.geq(m1, m2) else m2 def intersect_pair(u1: UpperSet[RT], u2: UpperSet[RT]) -> UpperSet[RT]: # always get the bigger of the two minimals - minimals: List[RT] = list(starmap(poset_max, zip(u1.minimals, u2.minimals))) + # minimals: List[RT] = list(starmap(poset_max, zip(u1.minimals, u2.minimals))) + minimals: List[RT] = [m for m in u1.minimals if m in u2.minimals] return UpperSet.from_points(poset, minimals) return reduce(intersect_pair, us[1:], us[0]) @@ -732,7 +733,7 @@ class DPSolver(DPSolverInterface): return union.minimals # Return antichain that is fixed point of phi - def kleene_ascent(phi, maxiter=100) -> List[R1]: + def kleene_ascent(phi) -> List[R1]: # initialize with bottoms, chain: List[RT] = dp.dp.R.global_maxima().maximals prev_chain = None @@ -760,18 +761,45 @@ class DPSolver(DPSolverInterface): # Hint: same as above, but go the other way... - raise NotImplementedError - def lowersets_intersection(poset: Poset[FT], ls: List[LowerSet[FT]]) -> LowerSet[FT]: if len(ls) < 2: return ls - def intersect_pair(l1: LowerSet[FT], l2: LowerSet[FT]) -> LowerSet[LT]: - elements = set() - for m1 in l1.maximals: - if m1 in l2.maximals: - elements.add(m1) + def intersect_pair(l1: LowerSet[FT], l2: LowerSet[FT]) -> LowerSet[FT]: + maximals: List[FT] = [m for m in l1.maximals if m in l2.maximals] + return LowerSet.from_points(poset, maximals) + + return reduce(intersect_pair, ls[1:], ls[0]) + + def phi(chain: List[FT]) -> List[FT]: + lowersets: List[LowerSet[FT]] = [] + for f in chain: + inner_r: RT = (query.resources,) + f[1:] + inner_query: FixResMaxFunQuery[RT] = FixResMaxFunQuery(resources=inner_r) + + max_fs: Interval[LowerSet[FT]] = self.solve_dp_FixResMaxFun(dp.dp, inner_query) + max_f: LowerSet[FT] = max_fs.pessimistic - maximals = list(poset.maximals(elements)) + dw_f = LowerSet.principal(f) + inters = lowersets_intersection(dp.dp.F, [max_f, dw_f]) + lowersets.append(inters) + + union: LowerSet[FT] = LowerSet.union(lowersets, dp.dp.F) + return union.maximals + + def kleene_ascent(phi) -> List[F1]: + chain: List[FT] = dp.dp.F.global_minima().minimals + prev_chain = None + + while chain != prev_chain: + prev_chain = chain + chain = phi(chain) + + first = lambda f: f[0] + chain: List[F1] = list(map(first, chain)) + return chain + chain: List[F1] = kleene_ascent(phi) + max_f_loop: LowerSet[F1] = LowerSet.from_points(dp.F, chain) + return Interval.degenerate(max_f_loop) |