fall2023

4 files changed, 675 insertions, 178 deletions

diff --git a/.gitignore b/.gitignore
index 9a5bb0b..206cad0 100644
--- a/.gitignore
+++ b/.gitignore
@@ -4,4 +4,6 @@ __pycache__
 .DS_Store
 .python-version
 .vscode/*log
-.out-results/*html
\ No newline at end of file
+.out-results/*htmloutput_summary.yaml
+downloaded
+output_summary.yaml
diff --git a/README.md b/README.md
index 6022733..7b98092 100644
--- a/README.md
+++ b/README.md
@@ -1,8 +1,4 @@
-# ACT4EI, Spring 2023, DP exercise
-
-Note: for Spring 2023 this exercise is **optional** -- it is very interesting to do, but we do not feel we have play-tested it enough for it to be a graded exercise.
-
-This exercise will NOT affect your final grade in ACT4EI Spring 2023 course. The final grade will be calculated as if everyone got 100% in this exercise.
+# ACT4EI, Fall 2023, DP exercise
 
 
 
@@ -24,44 +20,34 @@ What you'll do is **clone this repository**, and just *install* the code from `A
 
 ## Overview of the exercise
 
-The goal of this exercise is for you to build a DP and MCDP queries solver.
+The goal of this exercise is for you to build a DP queries solver.
 
 There are various phases of difficulty progression (listed at the end of this document).
 
 You will be given a DP represented using the data structures defined in `ACT4E-mcdp` along with a query.
 
-You have to extend the code in this repository by implementing the `DPSolver` and `MCDPSolver` classes.
+You have to extend the code in this repository by implementing the `DPSolver` class.
 
-For example, this is the interface of the `DPSolver` class:
+These are the main entrypoints of the `DPSolver` class:
 
 ```python
 from act4e_mcdp import DPSolverInterface, Interval, LowerSet, PrimitiveDP, UpperSet
 
 class DPSolver(DPSolverInterface):
-    def solve_dp_FixFunMinRes(
+     def solve_dp_FixFunMinRes(
         self,
-        dp: PrimitiveDP,
-        functionality_needed: object,
+        dp: PrimitiveDP[FT, RT],
+        query: FixFunMinResQuery[FT],
         /,
-        resolution_optimistic: int = 0,
-        resolution_pessimistic: int = 0,
-    ) -> Interval[UpperSet[object]]:
-         # just a template -- return infeasibility!
-        optimistic = pessimistic = UpperSet([])
-        return Interval(pessimistic=pessimistic, optimistic=optimistic)
-
-    def solve_dp_FixResMaxFun(
+    ) -> Interval[UpperSet[RT]]:
+         ...
+
+   def solve_dp_FixResMaxFun(
         self,
-        dp: PrimitiveDP,
-        resource_budget: object,
-        /,
-        resolution_optimistic: int = 0,
-        resolution_pessimistic: int = 0,
-    ) -> Interval[LowerSet[object]]:
-    
-        # just a template -- return infeasibility!
-        optimistic = pessimistic = LowerSet([])
-        return Interval(pessimistic=pessimistic, optimistic=optimistic)
+        dp: PrimitiveDP[FT, RT],
+        query: FixResMaxFunQuery[RT],
+    ) -> Interval[LowerSet[FT]]:
+        ...
 ```
 
 The two methods `solve_dp_FixFunMinRes` and `solve_dp_FixResMaxFun` correspond to the two queries studied in class
@@ -72,18 +58,54 @@ These includes the one that appeared in class or in the book (identity, addition
 
 [here]: https://act4e-mcdp.readthedocs.io/en/latest/API/primitivedps/00_index/
 
-The inputs (`functionality_needed` and `resource_budget`) are elements of the poset `F` or  `R` for the DPs. 
+The `query` parameter gives the parameters for the computation:
+
+- `FixFunMinResQuery` has the field `functionality` of type `FT` (the functionality to be provided).
+- `FixResMaxFunQuery` has the field `resources` of type `RT` (the resource budget).
+
+In addition, there are two more fields: `resolution_optimistic` and `resolution_pessimistic`. These are used in the case the DP is not finitely computable and needs an approximated solution. In that case, your code would be called with increasing values of the resolutions and the expectation is that the interval becomes tighther and tighther.  (You can ignore these fields for now.)
+
 For these exercises we have [3 types of posets](https://act4e-mcdp.readthedocs.io/en/latest/API/posets/):
 
 1. `FinitePoset`: finite posets, with strings as elements
 2. `Numbers`: with Python `Decimal` as elements.
 3. `PosetProduct`, whose elements are *tuples* (`(a, b, c)`) of elements of its subposets. 
 
-The return value is an `Interval` of upper / lower sets. The two extram of the interval represent optimistic and pessimistic solutions. 
+The posets are already implemented in `ACT4E-mcdp` and you can use them directly. They have useful methods such as `leq()` and `meet()`, `minimals()`, `join()`, `maximals()`.
+
+The return value is an `Interval` of upper / lower sets. The two extreama of the interval represent optimistic and pessimistic solutions. 
+
+### What you have to implement 
+
+What you have to implement are the methods called `solve_dp_FixFunMinRes_DPTYPE` and `solve_dp_FixResMaxFun_DPTYPE`.
+You have to implement these methods for each type of DP available.
+
+There are already some completed methods in the template solution, as well as hints for many of the methods.
+
+For example, this is the skeleton for implementing `IdentityDP`:
+
+```python
+    def solve_dp_FixFunMinRes_IdentityDP(
+        self, _: IdentityDP[X], query: FixFunMinResQuery[X]
+    ) -> Interval[UpperSet[X]]:
+        f = query.functionality
+        min_r = f # Easy: the minimal resources are the functionality itself
+        min_resources = UpperSet.principal(min_r)
+
+        # We need to return an interval of upper sets. It is a degenerate interval
+        return Interval.degenerate(min_resources)
+
+    def solve_dp_FixResMaxFun_IdentityDP(
+        self, _: IdentityDP[X], query: FixResMaxFunQuery[X]
+    ) -> Interval[LowerSet[X]]:
+        # same as above, but we return lower sets
+        r = query.resources
+        max_f = r # the maximum functionality is the resource budget
+        max_functionalities = LowerSet.principal(max_f)
+        return Interval.degenerate(max_functionalities)
+```
 
-The template code above returns empty upper / lower sets, which means that the solution is not feasible.
 
-The parameters `resolution_optimistic` and `resolution_pessimistic` are needed in the case the DP is not finitely computable and needs an approximated solution. In that case, your code would be called with increasing values of the resolutions and the expectation is that the interval becomes tighther and tighther.
 
 ### Workflow
 
@@ -91,14 +113,9 @@ This is the suggested workflow:
 
 1. Setup everything as described in the next section.
 2. Run the test runner and observe the errors.
-3. Select one error and work on that. This usually means adding support for a new type of DP or poset.
+3. Select one error and work on that. This usually means adding support for a new type of DP.
 4. repeat from 2
 
-**Note**: the `ACT4E-mcdp` package only contains the data structures to describe the problems. It does not contain the actual "code"! For example, the `PosetProduct` class available has a member `subs` that contains the subposets. However, there is no `leq()` or `meet()` method implemented.
-
-
-
-
 ## Turning in the exercise
 
 You can either email us a `.zip` file, or (better), create a **private** repository and gives us access.
@@ -106,6 +123,8 @@ You can either email us a `.zip` file, or (better), create a **private** reposit
 We ask you that **you do not make your code public**.
 
 
+-----
+
 # Setup the development environment
 
 This walkthrough makes you setup the development environment on VS Code in a docker container. 
@@ -159,7 +178,7 @@ If we tell you to update the library, use this:
 
 ## Make sure everything runs fine with the template solution
 
-### Download test cases
+### Download and run the test cases
 
 Use this command to download the test cases:
 
@@ -171,70 +190,20 @@ These are divided in "libraries" of varying complexity:
 
 * `lib1-parts`: very simple test cases, with only one primitive DP per file;
 * `lib2-simple`: simple test cases, with a few primitive DPs per file.
-* `lib3-advanced`: more complex test cases, with many primitive DPs per file.
-
-### Running the DP solver for a specific model and query
-
-`act4e-mcdp-solve-dp` is the command you use to run the DP solver 
-for a particular model and query:
-
-    act4e-mcdp-solve-dp \
-        --solver act4e_mcdp_solution.DPSolver \
-        --query FixFunMinRes \
-        --model downloaded/lib1-parts/lib1-parts.primitivedps.e03_splitter1.mcdpr1.yaml \
-        --data '10'
-
-In brief:
-
-* `--solver act4e_mcdp_solution.DPSolver`: this selects the class for your solver;
-* `--query FixFunMinRes`: this selects `FixFunMinRes` (other choice: `FixResMaxFun`);
-* `--model downloaded/lib1-parts/lib1-parts.primitivedps.e03_splitter1.mcdpr1.yaml`: this selects the model to use for optimization;
-* `--data '10'`: this selects the query to give.
-
-You will see the result in the logs:
-
-```
-INFO query: 10
-INFO solution: Interval(pessimistic=UpperSet(minima=[]), optimistic=UpperSet(minima=[]))
-```
+* `lib3-advanced`: more complex test cases (**not included for Fall 2023**).
 
-The template `act4e_mcdp_solution.MySolution` always returns an empty `UpperSet` (= infeasible).
 
-### Running the DP solver on a set of test cases
+`act4e-mcdp-solve-dp-queries` is the command you use to run the DP solver.
 
-`act4e-mcdp-solve-dp-queries` is the command you use to run the DP solver on a set of test cases:
+For example, you can run the solver on the test cases in `lib1-parts` using:
 
-    act4e-mcdp-solve-dp-queries \
-        -d downloaded/lib1-parts/ \
-        --solver act4e_mcdp_solution.DPSolver
+    act4e-mcdp-solve-dp-queries --solver act4e_mcdp_solution.DPSolver downloaded/lib1-parts
 
-In brief:
 
-* `-d downloaded`: this selects the directory with the test cases to use;
+The parameters are:
 * `--solver act4e_mcdp_solution.DPSolver`: this selects the class for your solver.
-
-At the end of the processing, you will see an output similar to this:
-
-```
-Summary:
-
-comparison_not_implemented:
-- downloaded/lib1-parts/lib1-parts.dp-queries.FixFunMinRes.e10_conversions2-0006.mcdpr1.yaml
-- downloaded/lib1-parts/lib1-parts.dp-queries.FixResMaxFun.e05_sumf-0002.mcdpr1.yaml
-...
-failed:
-- downloaded/lib1-parts/lib1-parts.dp-queries.FixResMaxFun.e03_splitter1-0006.mcdpr1.yaml
-- downloaded/lib1-parts/lib1-parts.dp-queries.FixFunMinRes.e12_catalogue_true-0010.mcdpr1.yaml
-... 
-succeeded:
-- downloaded/lib1-parts/lib1-parts.dp-queries.FixResMaxFun.e12_catalogue_empty-0001.mcdpr1.yaml
-- downloaded/lib1-parts/lib1-parts.dp-queries.FixFunMinRes.e12_catalogue-0001.mcdpr1.yaml
-...
-INFO Find the summary at 'output_summary.yaml'
-```
-
-For each query, the result is either `succeeded` or `failed`. (The status `comparison_not_implemented` means that we didn't implement yet
-the comparison between the result and the expected result.)
+* `downloaded/lib1-parts`: this selects the directory with the test cases to use;
+ 
 
 In the file `output_summary.yaml` you will find details of the results.
 
@@ -255,86 +224,40 @@ This indicated the type of query (`FixResMaxFun`), the value of the query (`Deci
 obtained result (`result_obtained`).
 This particular test case failed because the obtained result is empty ("infeasible"), while the expected result is not empty.
 
-### Running the MCDP solver
-
-This is the command you use to run the MCDP solver:
-
-    act4e-mcdp-solve-mcdp \
-        --solver act4e_mcdp_solution.MCDPSolver \
-        --query FixFunMinRes \
-        --model downloaded/lib1-parts.models.e03_splitter1.mcdpr1.yaml \
-        --data '{f: 42}'
-
-Note that for the MCDP solver we give a file of type `models.mcdpr1.yaml` instead of `primitivedps.mcdpr1.yaml`.
-
-For the data, we use a key-value pair with the functionality name and the value.
-
-You should see the output:
-
-    query: {'f': Decimal('42')}
-    solution: Interval(pessimistic=UpperSet(minima=[]), optimistic=UpperSet(minima=[]))
-
-## Running the MCDP solver on a set of test cases
-
-TODO: finish this part
-
----
-
 # ACT4E exercises progression
 
-There are 4 phases of increasing difficulty.
+There are 3 phases of increasing difficulty.
 
 Phase 1 and 2 are approachable, and were designed to be the graded part.
 
-Phases 3 and 4 are more challenging, and require some extra effort, and were always thought as optional.
+Phases 3 is challenging, and require some extra effort, and were always thought as optional.
 
 ## Phase 1: solve simple DP queries for each component
 
-In this first phase, you will implement the queries for each type of DP in isolation.
+In this first phase, you will implement the queries for each type of DP in isolation
+and the series composition.
 
-The following query must run successfully:
+The following command must run successfully:
 
-    act4e-mcdp-solve-dp-queries -d downloaded/lib1-parts  --solver act4e_mcdp_solution.DPSolver
+    act4e-mcdp-solve-dp-queries  --solver act4e_mcdp_solution.DPSolver downloaded/lib1-parts
 
 ## Phase 2: solve DP queries with multiple DPs (series, parallel, loop) 
 
-In this phase, you will implement the queries for *composition of DPs* joined by series, parallel, loop constructions.
-
-The following query must run successfully:
+In this phase, you will implement the queries for *composition of DPs* joined by parallel, loop constructions.
 
-    act4e-mcdp-solve-dp-queries -d downloaded/lib2-simple --solver act4e_mcdp_solution.DPSolver
+The following command must run successfully:
 
-## Phase 3: solve MCDP queries (*)
+    act4e-mcdp-solve-dp-queries  --solver act4e_mcdp_solution.DPSolver downloaded/lib2-simple
 
-In this phase, you are given only the graph. You then need to convert the graph into a DP. 
 
-To do this, you might need some experience or strong intuition about manipulating graphs.
 
-The following should work successfully:
 
-    act4e-mcdp-solve-mcdp-queries -d downloaded/lib1-parts  --solver act4e_mcdp_solution.MCDPSolver
-    act4e-mcdp-solve-mcdp-queries -d downloaded/lib2-simple --solver act4e_mcdp_solution.MCDPSolver
-
-## Phase 4: solve advanced queries (*)
+## Phase 3: solve advanced queries (excluded for Fall 2023)
 
 These are advanced queries that require a nontrivial implementation to solve efficiently.
 
-    act4e-mcdp-solve-dp-queries   -d downloaded/lib3-advanced   --solver act4e_mcdp_solution.DPSolver
-    act4e-mcdp-solve-mcdp-queries -d downloaded/lib3-advanced --solver act4e_mcdp_solution.MCDPSolver
-
-
-
-
-# Creating more test cases
-
-The models are created using [this online environment][IDE] - very experimental!
-
-[IDE]: https://editor.zuper.ai/editor/gh/co-design-models/ACT4E-exercises-spring2023/main/view/
-
-If you make an account you can play around. You can obtain the YAML file read by `ACT4E-mcdp` by selecting the "DP compiled YAML representation" option from the drop down menu. Some of the other visualizations might also be helpful.
-
-[Example: drone model](https://editor.zuper.ai/editor/gh/co-design-models/ACT4E-exercises-spring2023/main/view/libraries/lib2-simple/specs/models/things/drone1/)
-
- <img width="1113" alt="mcdpdrone" src="https://github.com/ACT4E/ACT4E-mcdp-exercise-template/assets/81052/b2e3c9ec-c55c-49c8-9e0c-071c02fb03c0">
-
+    act4e-mcdp-solve-dp-queries   -d downloaded/lib3-advanced --solver act4e_mcdp_solution.DPSolver
+    
+# Extra information 
 
+Please see the file [extra_info.md](extra_info.md) for more optional information about the data structures and the queries.
diff --git a/extra_info.md b/extra_info.md
new file mode 100644
index 0000000..2b2fb69
--- /dev/null
+++ b/extra_info.md
@@ -0,0 +1,71 @@
+# Extra information
+
+### Running the DP solver for a specific model and query
+
+`act4e-mcdp-solve-dp` is the command you use to run the DP solver 
+for a particular model and query:
+
+    act4e-mcdp-solve-dp \
+        --solver act4e_mcdp_solution.DPSolver \
+        --query FixFunMinRes \
+        --model downloaded/lib1-parts/lib1-parts.primitivedps.e03_splitter1.mcdpr1.yaml \
+        --data '10'
+
+In brief:
+
+* `--solver act4e_mcdp_solution.DPSolver`: this selects the class for your solver;
+* `--query FixFunMinRes`: this selects `FixFunMinRes` (other choice: `FixResMaxFun`);
+* `--model downloaded/lib1-parts/lib1-parts.primitivedps.e03_splitter1.mcdpr1.yaml`: this selects the model to use for optimization;
+* `--data '10'`: this selects the query to give.
+
+You will see the result in the logs:
+
+```
+INFO query: 10
+INFO solution: Interval(pessimistic=UpperSet(minima=[]), optimistic=UpperSet(minima=[]))
+```
+
+The template `act4e_mcdp_solution.MySolution` always returns an empty `UpperSet` (= infeasible).
+
+
+
+# Creating more test cases
+
+The models are created using [this online environment][IDE] - very experimental!
+
+[IDE]: https://editor.zuper.ai/editor/gh/co-design-models/ACT4E-exercises-spring2023/main/view/
+
+If you make an account you can play around. You can obtain the YAML file read by `ACT4E-mcdp` by selecting the "DP compiled YAML representation" option from the drop down menu. Some of the other visualizations might also be helpful.
+
+[Example: drone model](https://editor.zuper.ai/editor/gh/co-design-models/ACT4E-exercises-spring2023/main/view/libraries/lib2-simple/specs/models/things/drone1/)
+
+ <img width="1113" alt="mcdpdrone" src="https://github.com/ACT4E/ACT4E-mcdp-exercise-template/assets/81052/b2e3c9ec-c55c-49c8-9e0c-071c02fb03c0">
+
+
+
+<!--
+
+### Running the MCDP solver
+
+This is the command you use to run the MCDP solver:
+
+    act4e-mcdp-solve-mcdp \
+        --solver act4e_mcdp_solution.MCDPSolver \
+        --query FixFunMinRes \
+        --model downloaded/lib1-parts.models.e03_splitter1.mcdpr1.yaml \
+        --data '{f: 42}'
+
+Note that for the MCDP solver we give a file of type `models.mcdpr1.yaml` instead of `primitivedps.mcdpr1.yaml`.
+
+For the data, we use a key-value pair with the functionality name and the value.
+
+You should see the output:
+
+    query: {'f': Decimal('42')}
+    solution: Interval(pessimistic=UpperSet(minima=[]), optimistic=UpperSet(minima=[]))
+
+## Running the MCDP solver on a set of test cases
+
+TODO: finish this part
+
+--->
diff --git a/src/act4e_mcdp_solution/solver_dp.py b/src/act4e_mcdp_solution/solver_dp.py
index 8a4d58c..d6d1a7a 100644
--- a/src/act4e_mcdp_solution/solver_dp.py
+++ b/src/act4e_mcdp_solution/solver_dp.py
@@ -1,29 +1,530 @@
-from act4e_mcdp import DPSolverInterface, Interval, LowerSet, PrimitiveDP, UpperSet
+from typing import Optional, TypeVar
+from act4e_mcdp import *  # type: ignore
+from decimal import Decimal
 
 __all__ = [
     "DPSolver",
 ]
 
 
+X = TypeVar("X")
+FT = TypeVar("FT")
+RT = TypeVar("RT")
+R1 = TypeVar("R1")
+R2 = TypeVar("R2")
+F1 = TypeVar("F1")
+F2 = TypeVar("F2")
+
+
 class DPSolver(DPSolverInterface):
-    def solve_dp_FixFunMinRes(
-        self,
-        dp: PrimitiveDP,
-        functionality_needed: object,
-        /,
-        resolution_optimistic: int = 0,
-        resolution_pessimistic: int = 0,
+    # walkthrough: identity
+
+    def solve_dp_FixFunMinRes_IdentityDP(
+        self, _: IdentityDP[X], query: FixFunMinResQuery[X]
+    ) -> Interval[UpperSet[X]]:
+        # Easy: the minimal resources are the functionality itself
+        f = query.functionality
+        min_r = f
+        min_resources = UpperSet.principal(min_r)
+
+        # We need to return an interval of upper sets. It is a degenerate interval
+        return Interval.degenerate(min_resources)
+
+    def solve_dp_FixResMaxFun_IdentityDP(
+        self, _: IdentityDP[X], query: FixResMaxFunQuery[X]
+    ) -> Interval[LowerSet[X]]:
+        # same as above, but we return lower sets
+
+        r = query.resources
+        max_f = r
+        max_functionalities = LowerSet.principal(max_f)
+        return Interval.degenerate(max_functionalities)
+
+    # walkthrough: constant resources
+
+    def solve_dp_FixFunMinRes_Constant(
+        self, dp: Constant[X], query: FixFunMinResQuery[tuple[()]]
+    ) -> Interval[UpperSet[X]]:
+        # The DP is a relation of the type
+        #
+        #    42 ≤ r
+
+        # The functionalities are the empty tuple
+
+        assert query.functionality == (), query.functionality
+
+        # The minimal resources do not depend on functionality
+        # They are the constant value of the DP
+
+        min_r = dp.c.value
+        min_resources = UpperSet.principal(min_r)
+        return Interval.degenerate(min_resources)
+
+    def solve_dp_FixResMaxFun_Constant(
+        self, dp: Constant[X], query: FixResMaxFunQuery[X]
+    ) -> Interval[LowerSet[tuple[()]]]:
+        # The DP is a relation of the type
+        #
+        #    42 ≤ r
+
+        # Here we need to check whether the resources are at least 42
+
+        R = dp.R
+        if R.leq(dp.c.value, query.resources):
+            # the functionalities are the empty tuple
+            max_f = ()
+            return Interval.degenerate(LowerSet.principal(max_f))
+        else:
+            # the given budget is not enough
+            empty: LowerSet[tuple[()]] = LowerSet.empty()
+            return Interval.degenerate(empty)
+
+    # exercise: limit
+
+    def solve_dp_FixResMaxFun_Limit(self, dp: Limit[X], query: FixResMaxFunQuery[X]) -> Interval[LowerSet[X]]:
+        # The DP is a relation of the type
+        #
+        #    f ≤ 42
+
+        # This is the dual of Constant above. Swap functionalities and resources.
+
+        raise NotImplementedError
+
+    def solve_dp_FixFunMinRes_Limit(
+        self, dp: Limit[X], query: FixFunMinResQuery[X]
+    ) -> Interval[UpperSet[tuple[()]]]:
+        # The DP is a relation of the type
+        #
+        #    f ≤ 42
+
+        # This is the dual of Constant above. Swap functionalities and resources.
+
+        raise NotImplementedError
+
+    # walkthrough: ceil(f) <= r  DP
+
+    def solve_dp_FixFunMinRes_M_Ceil_DP(
+        self, dp: M_Ceil_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        # In the documentation of the class M_Ceil_DP we have
+        # that the relation is defined as:
+        #
+        #   ceil(f) ≤ r
+
+        # Therefore, the minimal resources are the ceiling of the functionality
+        #   r >= ceil(f)
+        f = query.functionality
+        assert isinstance(f, Decimal)
+
+        # For M_Ceil_DP, the F and R posets are Numbers
+        R: Numbers = dp.R
+        F: Numbers = dp.F
+
+        # Note: the f = +inf is a special case for which __ceil__() does not work
+        if f.is_infinite():
+            min_r = f
+        else:
+            # otherwise, we just use the ceil function
+            min_r = Decimal(f.__ceil__())
+
+        # now, one last detail: in general, the F poset can have
+        # different upper/lower bound or discretization than the R poset.
+        # We need to make sure that we provide a valid resource.
+
+        # There is a function largest_upperset_above() that will do this for us.
+        # See documentation there.
+
+        min_resources = R.largest_upperset_above(min_r)
+        return Interval.degenerate(min_resources)
+
+    def solve_dp_FixResMaxFun_M_Ceil_DP(
+        self, dp: M_Ceil_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        # Now r is fixed
+        r = query.resources
+        assert isinstance(r, Decimal), r
+
+        R: Numbers = dp.R
+        F: Numbers = dp.F
+
+        # For M_Ceil_DP, the F/R posets are Numbers
+
+        # first special case: r = +inf
+        if r.is_infinite():
+            max_f = r
+
+        else:
+            # what is the maximum f such that
+            #   ceil(f) <= r
+            # ?
+
+            # for example, if r = 13.2, then the maximum f is 13
+            # in fact, we obtain the floor of r
+
+            max_f = Decimal(r.__floor__())
+
+        # one last detail: we need to make sure that the functionality is valid
+        # for the F poset. We use the largest_lowerset_below() function in Numbers.
+        # See documentation there.
+
+        max_functionalities = F.largest_lowerset_below(max_f)
+
+        return Interval.degenerate(max_functionalities)
+
+    # exercise: floor relation
+
+    def solve_dp_FixFunMinRes_M_FloorFun_DP(
+        self, dp: M_FloorFun_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        # f <= floor(r)
+
+        # This is dual to M_Ceil_DP
+
+        raise NotImplementedError
+
+    def solve_dp_FixResMaxFun_M_FloorFun_DP(
+        self, dp: M_FloorFun_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        # f <= floor(r)
+
+        # This is dual to M_Ceil_DP
+
+        raise NotImplementedError
+
+    # exercise: catalogue
+
+    def solve_dp_FixFunMinRes_CatalogueDP(
+        self, dp: CatalogueDP[FT, RT], query: FixFunMinResQuery[FT]
+    ) -> Interval[UpperSet[RT]]:
+        f = query.functionality
+        F = dp.F
+
+        # Hint: iterate over the entries of the catalogue
+        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
+            ...
+
+        raise NotImplementedError
+
+    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
+
+    # exercise: series interconnections
+
+    def solve_dp_FixFunMinRes_DPSeries(
+        self, dp: DPSeries, query: FixFunMinResQuery[object]
     ) -> Interval[UpperSet[object]]:
-        optimistic = pessimistic = UpperSet([])
-        return Interval(pessimistic=pessimistic, optimistic=optimistic)
-
-    def solve_dp_FixResMaxFun(
-        self,
-        dp: PrimitiveDP,
-        resource_budget: object,
-        /,
-        resolution_optimistic: int = 0,
-        resolution_pessimistic: int = 0,
+        # This is the interconnection of a sequence of DPs.
+        # (You can assume that the sequence is at least 2 DPs).
+
+        # Hint: you should solve each DP in the sequence, and then
+        # pass it to the next.
+        # You can use the function self.solve_dp_FixFunMinRes() for this.
+
+        # Note 1: the solve_dp_FixFunMinRes_DPSeries() takes a single functionality.
+        # But in general the previous DP returns an upperset. You need to call it multiple times.
+        # 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 solve_dp_FixResMaxFun_DPSeries(
+        self, dp: DPSeries, query: FixResMaxFunQuery[object]
     ) -> Interval[LowerSet[object]]:
-        optimistic = pessimistic = LowerSet([])
-        return Interval(pessimistic=pessimistic, optimistic=optimistic)
+        # Hint: same as above, but go the other way...
+        raise NotImplementedError
+
+    # walkthrough: add a constant to functionalities ( f + constant <= r)
+
+    def solve_dp_FixFunMinRes_M_Res_AddConstant_DP(
+        self, dp: M_Res_AddConstant_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        f: Decimal = query.functionality
+        assert isinstance(f, Decimal)
+
+        R: Numbers = dp.R
+        F: Numbers = dp.F
+
+        # the relation is of the type
+        #
+        #    f + constant <= r
+
+        # therefore, the minimum resource is simply f + constant
+        min_r = f + dp.vu.value
+
+        # one last detail: we need to make sure that the resource is valid
+        # for the R poset. We use the largest_upperset_above() function in Numbers.
+        # See documentation there.
+        us = R.largest_upperset_above(min_r)
+
+        return Interval.degenerate(us)
+
+    def solve_dp_FixResMaxFun_M_Res_AddConstant_DP(
+        self, dp: M_Res_AddConstant_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        r = query.resources
+        assert isinstance(r, Decimal)
+
+        R: Numbers = dp.R
+        F: Numbers = dp.F
+
+        # the relation is of the type
+        #
+        #    f + constant <= r
+
+        # therefore, the maximal functionality is r - constant
+
+        max_f = r - dp.vu.value
+
+        # one last detail: we need to make sure that the functionality is valid
+        # for the F poset. We use the largest_lowerset_below() function in Numbers.
+        # See documentation there.
+        ls = F.largest_lowerset_below(max_f)
+
+        return Interval.degenerate(ls)
+
+    # exercise: add a constant to resource ( f <= r + constant)
+
+    def solve_dp_FixFunMinRes_M_Fun_AddConstant_DP(
+        self, dp: M_Fun_AddConstant_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        # f <= r + constant
+        # This is dual to the M_Res_AddConstant_DP case above.
+        raise NotImplementedError
+
+    def solve_dp_FixResMaxFun_M_Fun_AddConstant_DP(
+        self, dp: M_Fun_AddConstant_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        # f <= r + constant
+        # This is dual to the M_Res_AddConstant_DP case above.
+
+        raise NotImplementedError
+
+    # walkthrough: multiplying constants (f * constant <= r)
+    def solve_dp_FixFunMinRes_M_Res_MultiplyConstant_DP(
+        self, dp: M_Res_MultiplyConstant_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        #  (f * constant <= r)
+
+        # This is similar to the M_Res_AddConstant_DP case above with
+        # multiplication instead of addition.
+
+        f = query.functionality
+        assert isinstance(f, Decimal)
+        min_r = f * dp.vu.value
+
+        # one last detail: we need to make sure that the resource is valid
+        # for the R poset. We use the largest_upperset_above() function in Numbers.
+        # See documentation there.
+        us = dp.R.largest_upperset_above(min_r)
+
+        return Interval.degenerate(us)
+
+    def solve_dp_FixResMaxFun_M_Res_MultiplyConstant_DP(
+        self, dp: M_Res_MultiplyConstant_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        #  (f * constant <= r)
+
+        raise NotImplementedError
+
+    # 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
+
+    def solve_dp_FixResMaxFun_M_Fun_MultiplyConstant_DP(
+        self, dp: M_Fun_MultiplyConstant_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        raise NotImplementedError
+
+    # walktrough: multiply functionalities
+
+    def solve_dp_FixResMaxFun_M_Fun_MultiplyMany_DP(
+        self, dp: M_Fun_MultiplyMany_DP, query: FixResMaxFunQuery[tuple[Decimal, ...]]
+    ) -> Interval[LowerSet[Decimal]]:
+        # f <= r1 * r2 * r3 * ...
+
+        # This direction is easy, we just multiply the resources
+
+        res = Decimal(1)
+        for ri in query.resources:
+            res *= ri
+        ls = dp.F.largest_lowerset_below(res)
+        return Interval.degenerate(ls)
+
+    # exercise: multiply resources
+
+    def solve_dp_FixFunMinRes_M_Res_MultiplyMany_DP(
+        self, dp: M_Res_MultiplyMany_DP, query: FixFunMinResQuery[tuple[Decimal, ...]]
+    ) -> Interval[UpperSet[Decimal]]:
+        # f1 * f2 * f3 * ... <= r
+        # similar to the above
+
+        # this is the easy direction
+
+        raise NotImplementedError
+
+    # walkthough: add many
+
+    def solve_dp_FixFunMinRes_M_Res_AddMany_DP(
+        self, dp: M_Res_AddMany_DP, query: FixFunMinResQuery[tuple[Decimal, ...]]
+    ) -> Interval[UpperSet[Decimal]]:
+        # f1 + f2 + f3 + ... <= r
+
+        f = query.functionality
+        F: PosetProduct[Decimal] = dp.F
+        assert isinstance(f, tuple), f
+        assert len(f) == len(F.subs), (f, F)
+
+        # This direction is easy, we just add the functionalities
+        res = f[0]
+        for fi in f[1:]:
+            res += fi
+
+        min_r = res
+        us = dp.R.largest_upperset_above(min_r)
+        return Interval.degenerate(us)
+
+    # exercise: add many functionalities
+
+    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
+
+        raise NotImplementedError
+
+    # exercise: meet
+
+    def solve_dp_FixFunMinRes_MeetNDualDP(
+        self, dp: MeetNDualDP[X], query: FixFunMinResQuery[X]
+    ) -> Interval[UpperSet[tuple[X, ...]]]:
+        # this is a relation of the type
+        #  (f ≤  r₁) and (f ≤  r2)  and (f ≤  r3) and ...
+
+        # this direction is very easy, as we can just let each resource
+        # be equal to the functionality
+
+        f = query.functionality
+        min_res = (f,) * len(dp.R.subs)
+
+        us = dp.R.largest_upperset_above(min_res)
+        return Interval.degenerate(us)
+
+    def solve_dp_FixResMaxFun_MeetNDualDP(
+        self, dp: MeetNDualDP[X], query: FixResMaxFunQuery[X]
+    ) -> Interval[LowerSet[tuple[X, ...]]]:
+        raise NotImplementedError
+
+    # exercise: join
+
+    def solve_dp_FixFunMinRes_JoinNDP(
+        self, dp: JoinNDP[X], query: FixFunMinResQuery[tuple[X, ...]]
+    ) -> Interval[UpperSet[X]]:
+        # this is a relation of the type
+        #  (f1 ≤  r) and (f2 ≤ r) and (f3 ≤ r) and ...
+
+        # similar to above
+
+        f = query.functionality
+        min_r: Optional[X] = dp.opspace.join(f)
+        if min_r is None:
+            raise NotImplementedError("TODO: join")
+        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
+
+    # The above are sufficient for lib1
+    #
+    #
+    #
+    #
+
+    # The following are only for lib2.
+    #
+    #
+
+    def solve_dp_FixResMaxFun_M_Res_DivideConstant_DP(
+        self, dp: M_Res_DivideConstant_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        # f/c <= r
+
+        # Similar to a case above
+        raise NotImplementedError
+
+    def solve_dp_FixFunMinRes_M_Res_DivideConstant_DP(
+        self, dp: M_Res_DivideConstant_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        # f/c <= r
+
+        # Similar to a case above
+        raise NotImplementedError
+
+    # Exercise: parallel interconnection
+
+    def solve_dp_FixFunMinRes_ParallelDP(
+        self, dp: ParallelDP[FT, RT], query: FixFunMinResQuery[tuple[FT, ...]]
+    ) -> Interval[UpperSet[tuple[RT, ...]]]:
+        # This is the parallel composition of a sequence of DPs.
+
+        f = query.functionality
+
+        # F and R are PosetProducts
+        F: PosetProduct[FT] = dp.F
+        R: PosetProduct[RT] = dp.R
+
+        # and f is a tuple of functionalities
+        assert isinstance(f, tuple), f
+        # ... of the same length as the number of DPs
+        assert len(f) == len(dp.subs), (f, F)
+
+        # You should decompose f into its components, and then solve each DP.
+        # Then you need to take the *product* of the solutions.
+        # The product of upper sets is the upper set of the cartesian product
+        # and it is implemented as UpperSet.product().
+
+        raise NotImplementedError
+
+    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
+
+        # You will need to use LowerSet.product()
+        raise NotImplementedError
+
+    # exercise (advanced): loops!
+
+    def solve_dp_FixFunMinRes_DPLoop2(
+        self, dp: DPLoop2[F1, R1, object], query: FixFunMinResQuery[F1]
+    ) -> Interval[UpperSet[R1]]:
+        # Note: this is an advanced exercise.
+
+        # As in the book, the intermediate goal is to define a function f such that
+        # the solution is the least fixed point of f.
+
+        raise NotImplementedError
+
+    def solve_dp_FixResMaxFun_DPLoop2(
+        self, dp: DPLoop2[F1, R1, object], query: FixResMaxFunQuery[R1]
+    ) -> Interval[LowerSet[F1]]:
+        # Note: this is an advanced exercise.
+
+        # Hint: same as above, but go the other way...
+        raise NotImplementedError