diff options
Diffstat (limited to 'src/act4e_mcdp_solution')
| -rw-r--r-- | src/act4e_mcdp_solution/solver_dp.py | 229 |
1 files changed, 201 insertions, 28 deletions
diff --git a/src/act4e_mcdp_solution/solver_dp.py b/src/act4e_mcdp_solution/solver_dp.py index d6d1a7a..a95451f 100644 --- a/src/act4e_mcdp_solution/solver_dp.py +++ b/src/act4e_mcdp_solution/solver_dp.py @@ -1,6 +1,10 @@ from typing import Optional, TypeVar from act4e_mcdp import * # type: ignore from decimal import Decimal +from functools import reduce +from typing import Tuple + +import itertools __all__ = [ "DPSolver", @@ -88,7 +92,10 @@ class DPSolver(DPSolverInterface): # This is the dual of Constant above. Swap functionalities and resources. - raise NotImplementedError + max_f = dp.c.value + max_functionality = LowerSet.principal(max_f) + return Interval.degenerate(max_functionality) + def solve_dp_FixFunMinRes_Limit( self, dp: Limit[X], query: FixFunMinResQuery[X] @@ -99,7 +106,12 @@ class DPSolver(DPSolverInterface): # This is the dual of Constant above. Swap functionalities and resources. - raise NotImplementedError + if dp.F.geq(dp.c.value, query.functionality): + min_r = () + return Interval.degenerate(UpperSet.principal(min_r)) + else: + empty = UpperSet.empty() + return Interval.degenerate(empty) # walkthrough: ceil(f) <= r DP @@ -179,8 +191,19 @@ class DPSolver(DPSolverInterface): # f <= floor(r) # This is dual to M_Ceil_DP + f = query.functionality + assert isinstance(f, Decimal) - raise NotImplementedError + R: Numbers = dp.R + F: Numbers = dp.F + + if f.is_infinite(): + min_r = f + else: + min_r = Decimal(f.__floor__()) + + min_resources = R.largest_upperset_above(min_r) + return Interval.degenerate(min_resources) def solve_dp_FixResMaxFun_M_FloorFun_DP( self, dp: M_FloorFun_DP, query: FixResMaxFunQuery[Decimal] @@ -188,8 +211,16 @@ class DPSolver(DPSolverInterface): # f <= floor(r) # This is dual to M_Ceil_DP + r = query.resources + assert isinstance(r, Decimal), r - raise NotImplementedError + if r.is_infinite(): + max_f = r + else: + max_f = Decimal(r.__floor__()) + + max_functionalities = dp.F.largest_lowerset_below(max_f) + return Interval.degenerate(max_functionalities) # exercise: catalogue @@ -200,21 +231,36 @@ class DPSolver(DPSolverInterface): F = dp.F # Hint: iterate over the entries of the catalogue + min_rs = [] + name: str entry_info: EntryInfo[FT, RT] for name, entry_info in dp.entries.items(): # Then check if this entry is valid for the functionality - # In that case, the resources of the entry are a valid solution - ... + # In that case, the resources of the entry are a valid solution + if F.leq(f, entry_info.f_max): + min_rs.append(entry_info.r_min) - raise NotImplementedError + if not min_rs: + return Interval.degenerate(UpperSet.empty()) + + min_r = min(min_rs) + return Interval.degenerate(UpperSet.principal(min_r)) def solve_dp_FixResMaxFun_CatalogueDP( self, dp: CatalogueDP[FT, RT], query: FixResMaxFunQuery[RT] ) -> Interval[LowerSet[FT]]: - # Same pattern as above, but functionalities and resources are swapped. - raise NotImplementedError + max_fs = [] + for _, info in dp.entries.items(): + if dp.R.geq(query.resources, info.r_min): + max_fs.append(info.f_max) + + if not max_fs: + return Interval.degenerate(LowerSet.empty()) + + max_f = max(max_fs) + return Interval.degenerate(LowerSet.principal(max_f)) # exercise: series interconnections @@ -233,13 +279,74 @@ class DPSolver(DPSolverInterface): # Note 2: the solve_dp_FixFunMinRes_DPSeries() returns an *interval* of upper sets. # Just treat the optimistic and pessimistic cases separately and then combine them in an interval. - raise NotImplementedError + def chain_naive(queries, dp): + us_res = [self.solve_dp_FixFunMinRes(dp, query) + for query in queries] + + optimistic = (FixFunMinResQuery(functionality=r) + for us_r in us_res for r in us_r.optimistic.minimals) + + pessimistic = (FixFunMinResQuery(functionality=r) + for us_r in us_res for r in us_r.pessimistic.minimals) + + return itertools.chain(optimistic, pessimistic) + + queries = list(reduce(chain_naive, dp.subs, (query,))) + + if not queries: + return Interval.degenerate(UpperSet.empty()) + + min_r = queries[0].functionality + max_r = queries[0].functionality + + for query in queries: + r = query.functionality + if r < min_r: + min_r = r + + if r > max_r: + max_r = r + + return Interval(optimistic=dp.R.largest_upperset_above(min_r), + pessimistic=dp.R.largest_upperset_above(max_r)) def solve_dp_FixResMaxFun_DPSeries( self, dp: DPSeries, query: FixResMaxFunQuery[object] ) -> Interval[LowerSet[object]]: # Hint: same as above, but go the other way... - raise NotImplementedError + + def chain_naive(queries, dp): + ls_fun = [self.solve_dp_FixResMaxFun(dp, query) + for query in queries] + + optimistic = (FixResMaxFunQuery(resources=f) + for ls_f in ls_fun + for f in ls_f.optimistic.maximals) + + pessimistic = (FixResMaxFunQuery(resources=f) + for ls_f in ls_fun + for f in ls_f.pessimistic.maximals) + + return itertools.chain(optimistic, pessimistic) + + queries = list(reduce(chain_naive, reversed(dp.subs), (query,))) + + if not queries: + return Interval.degenerate(LowerSet.empty()) + + max_f = queries[0].resources + min_f = queries[0].resources + + for query in queries: + f = query.resources + if f < min_f: + min_f = f + + if f > max_f: + max_f = f + + return Interval(optimistic=dp.F.largest_lowerset_below(max_f), + pessimistic=dp.F.largest_lowerset_below(min_f)) # walkthrough: add a constant to functionalities ( f + constant <= r) @@ -297,7 +404,12 @@ class DPSolver(DPSolverInterface): ) -> Interval[UpperSet[Decimal]]: # f <= r + constant # This is dual to the M_Res_AddConstant_DP case above. - raise NotImplementedError + + f = query.functionality + min_r = f - dp.vu.value + us = dp.R.largest_upperset_above(min_r) + + return Interval.degenerate(us) def solve_dp_FixResMaxFun_M_Fun_AddConstant_DP( self, dp: M_Fun_AddConstant_DP, query: FixResMaxFunQuery[Decimal] @@ -305,7 +417,11 @@ class DPSolver(DPSolverInterface): # f <= r + constant # This is dual to the M_Res_AddConstant_DP case above. - raise NotImplementedError + r = query.resources + max_f = r + dp.vu.value + ls = dp.F.largest_lowerset_below(max_f) + + return Interval.degenerate(ls) # walkthrough: multiplying constants (f * constant <= r) def solve_dp_FixFunMinRes_M_Res_MultiplyConstant_DP( @@ -332,19 +448,33 @@ class DPSolver(DPSolverInterface): ) -> Interval[LowerSet[Decimal]]: # (f * constant <= r) - raise NotImplementedError + r = query.resources + max_f = r / dp.vu.value + ls = dp.F.largest_lowerset_below(max_f) + + return Interval.degenerate(ls) # exercise: multiply by constant (f <= r * constant) def solve_dp_FixFunMinRes_M_Fun_MultiplyConstant_DP( self, dp: M_Fun_MultiplyConstant_DP, query: FixFunMinResQuery[Decimal] ) -> Interval[UpperSet[Decimal]]: - raise NotImplementedError + + f = query.functionality + min_r = f / dp.vu.value + us = dp.R.largest_upperset_above(min_r) + + return Interval.degenerate(us) def solve_dp_FixResMaxFun_M_Fun_MultiplyConstant_DP( self, dp: M_Fun_MultiplyConstant_DP, query: FixResMaxFunQuery[Decimal] ) -> Interval[LowerSet[Decimal]]: - raise NotImplementedError + + r = query.resources + max_f = r * dp.vu.value + ls = dp.F.largest_lowerset_below(max_f) + + return Interval.degenerate(ls) # walktrough: multiply functionalities @@ -370,8 +500,11 @@ class DPSolver(DPSolverInterface): # similar to the above # this is the easy direction + multiply = lambda acc, f: acc * f + fun = reduce(multiply, query.functionality, Decimal(1)) - raise NotImplementedError + us = dp.R.largest_upperset_above(fun) + return Interval.degenerate(us) # walkthough: add many @@ -399,12 +532,12 @@ class DPSolver(DPSolverInterface): def solve_dp_FixResMaxFun_M_Fun_AddMany_DP( self, dp: M_Fun_AddMany_DP, query: FixResMaxFunQuery[tuple[Decimal, ...]] ) -> Interval[LowerSet[Decimal]]: - # this is a relation of the type - # (f1 ≤ r) and (f2 ≤ r) and (f3 ≤ r) and ... - # This direction is easy, we just add the resources + add = lambda acc, r: acc + r + res = reduce(add, query.resources, Decimal(0)) - raise NotImplementedError + ls = dp.F.largest_lowerset_below(res) + return Interval.degenerate(ls) # exercise: meet @@ -426,7 +559,13 @@ class DPSolver(DPSolverInterface): def solve_dp_FixResMaxFun_MeetNDualDP( self, dp: MeetNDualDP[X], query: FixResMaxFunQuery[X] ) -> Interval[LowerSet[tuple[X, ...]]]: - raise NotImplementedError + + max_f = dp.opspace.meet(query.resources) + if max_f is None: + return Interval.degenerate(LowerSet.empty()) + + ls = dp.F.largest_lowerset_below(max_f) + return Interval.degenerate(ls) # exercise: join @@ -441,14 +580,20 @@ class DPSolver(DPSolverInterface): f = query.functionality min_r: Optional[X] = dp.opspace.join(f) if min_r is None: - raise NotImplementedError("TODO: join") + return Interval.degenerate(UpperSet.empty()) + us: UpperSet[X] = dp.R.largest_upperset_above(min_r) return Interval.degenerate(us) def solve_dp_FixResMaxFun_JoinNDP( self, dp: JoinNDP[X], query: FixResMaxFunQuery[X] ) -> Interval[LowerSet[tuple[X, ...]]]: - raise NotImplementedError + + r = query.resources + max_f = (r,) * len(dp.F.subs) + + ls = dp.F.largest_lowerset_below(max_f) + return Interval.degenerate(ls) # The above are sufficient for lib1 # @@ -466,7 +611,11 @@ class DPSolver(DPSolverInterface): # f/c <= r # Similar to a case above - raise NotImplementedError + r = query.resources + max_f = r * dp.vu.value + ls = dp.F.largest_lowerset_below(max_f) + + return Interval.degenerate(ls) def solve_dp_FixFunMinRes_M_Res_DivideConstant_DP( self, dp: M_Res_DivideConstant_DP, query: FixFunMinResQuery[Decimal] @@ -474,7 +623,11 @@ class DPSolver(DPSolverInterface): # f/c <= r # Similar to a case above - raise NotImplementedError + f = query.functionality + min_r = r / dp.vu.value + us = dp.R.largest_upperset_above(min_r) + + return Interval.degenerate(us) # Exercise: parallel interconnection @@ -499,15 +652,35 @@ class DPSolver(DPSolverInterface): # The product of upper sets is the upper set of the cartesian product # and it is implemented as UpperSet.product(). - raise NotImplementedError + queries = (FixFunMinResQuery(functionality=f) + for f in query.functionality) + + min_res = [self.solve_dp_FixFunMinRes(dp, query) + for dp, query in zip(dp.subs, queries)] + + optimistic = lambda res: res.optimistic + pessimistic = lambda res: res.pessimistic + + return Interval(optimistic=UpperSet.product(map(optimistic, min_res)), + pessimistic=UpperSet.product(map(pessimistic, min_res))) def solve_dp_FixResMaxFun_ParallelDP( self, dp: ParallelDP[FT, RT], query: FixResMaxFunQuery[tuple[RT, ...]] ) -> Interval[LowerSet[FT]]: # Hint: same as above, swapping functionalities and resources + queries = (FixResMaxFunQuery(resources=r) + for r in query.resources) + + max_fun = [self.solve_dp_FixResMaxFun(dp, query) + for dp, query in zip(dp.subs, queries)] + + optimistic = lambda fun: fun.optimistic + pessimistic = lambda fun: fun.pessimistic + # You will need to use LowerSet.product() - raise NotImplementedError + return Interval(optimistic=LowerSet.product(map(optimistic, max_fun)), + pessimistic=LowerSet.product(map(pessimistic, max_fun))) # exercise (advanced): loops! |