summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/act4e_mcdp_solution/solver_dp.py229
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!
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-28 12:09:57 +0100