How to use MCDM methods¶
In this example, we will see how MCDM methods available in DESDEO can be utilized to solve multiobjective optimization problems. MCDM methods are implemented in a functional way, which means their individual components must be first combined. This might feel unnecessary at first, but in practice, it means we are able to combine components of multiple methods to create new methods that can best suit our needs and the needs of decision makers.
Since scalarization sits often in a central role in DESDEO, we will first see examples of how it can be done. Then, we will see examples of the Reference Point Method and Synchronous NIMBUS in action. Throughout this example, we will be solving the river pollution problem, consisting of two continuous variables and four objective functions ($f_1, f_2, f_3, f_4$ to be maximized). We choose this problem because of its relative simplicity.
Scalarization in DESDEO¶
Scalarization is the transformation of a multiobjective optimization problem
into a single-objective optimization one. In DESDEO, this happens by adding a
ScalarizationFunction to an instance of the Problem class. However, because
many scalarization functions require information on either the ideal or nadir
point, or both, of the problem being solved, we first need to compute these
before proceeding with scalarization.
Computing the ideal point and (approximating) the nadir point¶
To compute the ideal point, and approximate the nadir point, of the rive pollution problem,
we can utilize the payoff table method
(payoff_table_method).
We begin by creating an instance of the river pollution problem and
passing it to the payoff table method:
from desdeo.problem.testproblems import river_pollution_problem
from desdeo.tools import PyomoIpoptSolver, payoff_table_method
problem = river_pollution_problem(five_objective_variant=False) # we use the four objective variant
ideal, nadir = payoff_table_method(problem, solver=PyomoIpoptSolver)
print(f"{ideal=}")
print(f"{nadir=}")
ideal={'f_1': 6.34, 'f_2': 3.444871794145378, 'f_3': 7.499999999424789, 'f_4': -7.777537502917653e-10}
nadir={'f_1': 4.751000003065099, 'f_2': 2.853461538677661, 'f_3': 0.32111111111111956, 'f_4': -9.706666666666656}
While the computed ideal point will have its components at the true ideal
points, as the nadir point will generally be a very rough approximation of the
true nadir point due to the nature of the payoff table method. We also notice
that we passed the
PyomoIpoptSolver
solver to the payoff table method. This solver interfaces to the
Ipopt from the COIN-OR project through a
Pyomo model (https://www.pyomo.org/), hence the name. Ipopt is suitable for
non-linear optimization.
Choosing the right solver
While it is not required to supply a solver to many of the functions utilizing them, relying on the automatic inference of the correct type of solver implemented in DESDEO can be unpredictable. This is because the correct type of solver cannot be always inferred from the properties of the problem alone, since this could be transformed in various ways (e.g., when scalarized). Thus, it is recommended to always manually choose and supply an appropriate solver, when possible.
In practice, the nadir point can be either inquired from a decision maker (domain expert), or it can be approximated by solving the problem utilizing an evolutionary method, such as NSGA3, and then reading the nadir point values of the approximated Pareto front. However, while inaccurate, the payoff table method works out-of-the-box with almost any problem, and it gives at least a first workable approximation fo the nadir point. The ideal point computed by the payoff table method is often accurate enough to get some preliminary results. A more accurate approximation should be considered for more ambitious tasks.
The payoff table method is not very accurate
The payoff table method is a very rough way to approximate the nadir point of a problem. It is better to use an evolutionary method instead to approximate the problem's Pareto front, and then read an approximated value for the nadir point from the front.
Regardless the source of the information about the nadir (and ideal) point values, we can update the problem with this information. For the purpose of this example, the nadir point approximated by the payoff table method is accurate enough.
problem = problem.update_ideal_and_nadir(ideal, nadir)
print(f"Ideal: {problem.get_ideal_point()}")
print(f"Nadir: {problem.get_nadir_point()}")
Ideal: {'f_1': 6.34, 'f_2': 3.444871794145378, 'f_3': 7.499999999424789, 'f_4': -7.777537502917653e-10}
Nadir: {'f_1': 4.751000003065099, 'f_2': 2.853461538677661, 'f_3': 0.32111111111111956, 'f_4': -9.706666666666656}
It is important to note that the utilized method update_ideal_and_nadir
and then used its output to redefine the variable problem. In DESDEO, instances
of the Problem class are, in principle, immutable. This means that anytime
we wish to change an already instantiated Problem object, we essentially have
to create a new one. Problems are chosen to be immutable in DESDEO to avoid
involuntarily changing the original problem, which can easily happen when
solving the problem with multiple methods.
Problems are immutable
Instances of the Problem class in DESDEO are immutable. When making
changes to an existing Problem objects, methods and functions will return a
new instance of the original Problem with the applied changes.
Scalarizing a problem¶
Once we have the ideal and nadir point values available, we can scalarize our
problem. We will use the achievement scalarizing function, or ASF. To utilize
the ASF, we will need a reference point. Let us use the values $\left[5.55,
3.20, 3.91, -4.85\right]$ for the reference point, as an example. Because the
river pollution problem is differentiable, we can use the differentiable variant of the
ASF (desdeo.tools.add_asf_diff):
from desdeo.tools import add_asf_diff
reference_point = {
"f_1": 5.55,
"f_2": 3.20,
"f_3": 3.91,
"f_4": -4.85,
}
# The first returned value is the problem with the scalarization, while the
# second is the symbol of the newly added scalarization function.
problem_w_asf, target = add_asf_diff(problem, symbol="asf", reference_point=reference_point)
When adding the ASF, we had to supply also a symbol in addition to the
reference_point. As discussed in the previous example, the symbol is
utilized to identify various components of a Problem. In this case, the
symbol="asf" is used to refer to the ASF, which was added to the problem.
Note that the symbol is just a name, it can be any string as long as the
instance of the Problem does not have existing components with the
same symbol.
We also mentioned that we can use the differentiable variant of the ASF, because
our problem is differentiable. This is important because we want to keep the
differentiability of our problem even after scalarization. This allows us to
use, e.g., gradient-based optimizers when solving the scalarized problem. In
turn, this allows us to get accurate and optimal solutions. If our problem was
not differentiable, then we could have used the non-differentiable variant of
ASF
(desdeo.tools.add_asf_nondiff.
This would be practical if we knew we had to solve our problem using
heuristics-based methods, which are impartial to the differentiability of our
problem. In fact, it could be even detrimental to utilize the differentiable
variant when solving the scalarized problem with an evolutionary method, since
the differentiable variant introduces additional constraints to the problem,
which evolutionary methods are not very adept to handle. The lesson here is,
that we should be knowledgeable enough about our problem to manipulate it in the
best possible way.
Custom scalarization functions
While DESDEO provides functions (such as add_asf_diff) to add scalarization functions to problems,
user are by no means limited to only these. A scalarization function is nothing more than a field
in a Problem object. Users can define their own
ScalarizationFunction objects
and add them to an instance of a Problem using its
add_scalarization
method.
Solving a scalarized problem¶
To solve the scalarized problem, we can once again utilize the PyomoIpoptSolver
interface. However, this time we will have to set it up ourselves instead of
just passing it as an argument to the payoff table method:
solver = PyomoIpoptSolver(problem_w_asf)
result = solver.solve(target)
Notice how we passed the target to the solve method. This tells the solver, which
objective function should be optimized. The solver interfaces in DESDEO
return their optimization results in a Pydantic object. We can inspect its content
by printing it as a dictionary:
pprint(result.__dict__, width=120)
{'constraint_values': {'f_1_con': -0.3057121161773089,
'f_2_con': 5.2541548611895195e-09,
'f_3_con': -9.922041001309001e-08,
'f_4_con': 4.461188946036643e-09},
'extra_func_values': None,
'lagrange_multipliers': {'mu_f_1_con': -7.790331909609123e-09,
'mu_f_2_con': -0.5327506089857361,
'mu_f_3_con': -0.02064958136703413,
'mu_f_4_con': -0.44659980185689796},
'message': "Pyomo solver status is: 'ok', with termination condition: 'optimal'.",
'optimal_objectives': {'f_1': 6.209215259580463,
'f_2': 3.2645521421644514,
'f_3': 4.6935717699556765,
'f_4': -3.7905237220787527},
'optimal_variables': {'_alpha': -0.10914933504396458, 'x_1': 0.9423855769076929, 'x_2': 0.942293488230703},
'scalarization_values': {'asf': -0.1091590258964131},
'success': True}
Out of the results, we are likely most interested in the fields
optimal_objectives and optimal_variables, which represent the optimal
objective function and variable values for the found optimal solution of the
scalarized problem. The success field will indicate whether the optimization
was successful, and the message field will yield solver-specific information
on the success, failure, or other details, of the optimization process. Lastly, checking
the constraint_values field can be valuable as well, since as we recall from the
previous example, constraints in DESDEO are defined such that a negative value
means the constraint holds, and a positive that it is breached. Here we see
some values being positive, yet extremely close to zero. In practice, these
values can be safely assumed to be zero due to the nature and precision
of floating-point arithmetics on computers.
Utilizing the Reference Point Method¶
The Reference Point method is a relatively simple interactive multiobjective optimization method, which utilizes scalarization, and a reference point as preference information. The method uses the reference point to create $k+1$, with $k$ being the number of objective functions, sub-problems, which use a perturbed version of the original reference point (one of the sub-problems uses the original unperturbed reference point as well) to scalarize the problem being solved using the achievement scalarizing function. The resulting solutions from the sub-problems will be more spread out the farther the original reference point is from the true Pareto front of the problem. This can allow a decision maker to get a more general picture of what kind of solutions are available, when far from the front; and fine-tune their solution once the decision maker begins to close on the Pareto front with the given reference point. The method is interactive, which means that a decision maker is expected to provide reference points iteratively during multiple iterations of the method.
As the Reference Point Method is quite simple, we will need only one function to operate it. We begin by importing it, we choose to use the same reference point we utilized previously as the initial preference information, and then we iterate the method:
from desdeo.mcdm import rpm_solve_solutions
results = rpm_solve_solutions(problem, reference_point, solver=PyomoIpoptSolver)
print(f"Number of solutions {len(results)}")
print(f"Original reference point: {reference_point}")
for i, result in enumerate(results):
print(f"Solution {i + 1}: F={result.optimal_objectives}")
Number of solutions 5
Original reference point: {'f_1': 5.55, 'f_2': 3.2, 'f_3': 3.91, 'f_4': -4.85}
Solution 1: F={'f_1': 6.209215259580463, 'f_2': 3.2645521421644514, 'f_3': 4.6935717699556765, 'f_4': -3.7905237220787527}
Solution 2: F={'f_1': 6.333581085606338, 'f_2': 3.2320614749864305, 'f_3': 0.7869049796974465, 'f_4': -3.0864154299166513}
Solution 3: F={'f_1': 6.34, 'f_2': 3.444871794871795, 'f_3': 0.32111111111111956, 'f_4': -9.706666666666656}
Solution 4: F={'f_1': 6.03526345485618, 'f_2': 3.2609445665046404, 'f_3': 6.12463871022508, 'f_4': -3.8497338520291216}
Solution 5: F={'f_1': 6.2401194817884615, 'f_2': 3.2220277161467132, 'f_3': 4.177385497175266, 'f_4': -3.0136071413650147}
As seen from the output, we got 5 solutions, which is expected with 4 objective
functions. Notice also how we passed the instance of the problem without an
added scalarization function (problem). The addition of the scalarization
function happened in the function implementing the Reference Point Method.
Suppose a decision maker now provides a new reference point: $[6.10, 3.50, 7.1, -5.67]$. We use it to iterate the method again:
new_reference_point = {"f_1": 6.10, "f_2": 3.50, "f_3": 7.1, "f_4": -5.67}
results = rpm_solve_solutions(problem, new_reference_point, solver=PyomoIpoptSolver)
print(f"Number of solutions {len(results)}")
print(f"Original reference point: {new_reference_point}")
for i, result in enumerate(results):
print(f"Solution {i + 1}: F={result.optimal_objectives}")
Number of solutions 5
Original reference point: {'f_1': 6.1, 'f_2': 3.5, 'f_3': 7.1, 'f_4': -5.67}
Solution 1: F={'f_1': 6.101764818212015, 'f_2': 3.388971290256371, 'f_3': 5.752269996149671, 'f_4': -7.492283083683719}
Solution 2: F={'f_1': 6.34, 'f_2': 3.233240022491159, 'f_3': 0.32111111111111956, 'f_4': -3.098253311827942}
Solution 3: F={'f_1': 6.34, 'f_2': 3.444871794871795, 'f_3': 0.32111111111111956, 'f_4': -9.706666666666656}
Solution 4: F={'f_1': 5.596912123721864, 'f_2': 3.314737137151284, 'f_3': 7.096351335710338, 'f_4': -5.378452885225466}
Solution 5: F={'f_1': 6.162954663873434, 'f_2': 3.347633136093806, 'f_3': 5.250483945197805, 'f_4': -5.901520819860092}
We notice how the solutions changed with the new reference point. This process of providing a reference point and inspecting solutions can continue for multiple iterations until a satisfactory solution is found, or the decision maker gets tired, for instance.
Utilizing Synchronous NIMBUS¶
In the interactive Synchronous NIMBUS (or just NIMBUS) method, instead of providing a reference point, a decision maker classifies each objective function value of a Pareto optimal solution into one of five different classes in each iteration. These classes are:
- $<$: to be improved from its current value,
- $\leq$: to be improved until some aspiration level is reached,
- $\geq$: to be worsened until some reservation level is reached,
- $=$: to stay at its current value, and
- $0$: to change freely.
This classification information is then utilized to compute 1 to 4 (depending on the wishes of the decision maker) new Pareto optimal solutions. Internally, for each computed solution, a different scalarization function is formulated based on the given classifications. The reason to utilize different scalarization functions is that different functions will result in different Pareto optimal solutions once solved, even if the same preference information is utilized. Having different solution candidates available for the decision maker to inspect can be argued to be beneficial from a decision-support perspective
Apart from a different preference type, in NIMBUS the decision maker has also the possibility to save interesting solutions to an archive to be inspected later, or chosen as the next solution to be classified. Furthermore, the decision maker has also the option to request a desired number of solutions to be computed between two previously found solutions. Thus, unlike in the Reference Point Method, we will be utilizing more than just one function to build a simple implementation of NIMBUS.
Generating a starting point¶
As mentioned, in NIMBUS, the decision maker classifies the objective function values of a Pareto optimal solution in each iteration. This means that we will need an initial solution to begin with. This solution may come from outside the method (e.g., from a previously utilized method), or it may be computed based on an initial reference point given by a decision maker, for example; or we may just utilize a "compromise" reference point, which is a reference point having its aspiration level values sitting in the middle point of the objective function's ideal and nadir point values, respectively.
If we keep considering the river pollution problem, we have the previously computed solutions available from the Reference Point Method. But in case we did not, we could use the middle point values between the ideal and nadir values of each objective function as a "compromise" reference point as follows:
# we recall that each objective function is to be maximized
compromise_reference_point = {obj.symbol: obj.nadir + (obj.ideal - obj.nadir) / 2.0 for obj in problem.objectives}
print(f"{compromise_reference_point=}")
compromise_reference_point={'f_1': 5.545500001532549, 'f_2': 3.1491666664115194, 'f_3': 3.9105555552679543, 'f_4': -4.853333333722205}
Then, to solve for the starting point utilizing a reference point, we utilize
the
generate_starting_point
function defined for NIMBUS:
from desdeo.mcdm.nimbus import generate_starting_point
result_starting_point = generate_starting_point(
problem, reference_point=compromise_reference_point, solver=PyomoIpoptSolver
)
starting_point = result_starting_point.optimal_objectives
print(f"{starting_point=}")
starting_point={'f_1': 6.184587708565152, 'f_2': 3.240173842302374, 'f_3': 5.015253701464943, 'f_4': -3.359657987318718}
Classification of objective function values¶
Once we have a starting point, we can define the classifications of the objective function values. In the implementation of NIMBUS, the classifications are given as components of a reference point according to the following logic:
- $<$: for objective functions to be improved, we provide the objective function's ideal value;
- $\leq$: for objective functions to be improved until some aspiration level, we provide the aspiration level's value, which should be better than the current value of the objective function being classified, but not better than the ideal;
- $\geq$: for objective functions to be worsened until some reservation level, we provide the reservation level's value, which should be worse than the current value of the objective function being classified, but not worse than the nadir;
- $=$: for objective functions to be kept at their current value, we provide that objective function's current value; and
- $0$: for objective functions to change freely, we provide that objective function's nadir value.
In addition, the classifications given should overall allow at least one objective function to be worsened and one to be improved. In other words, the classifications should include at least one classification belonging to the classes $<, \leq$, and one belonging to $\geq, 0$ to be valid.
Suppose now we consider the previously computed starting point $[6.18, 3.24, 5.02, -3.40]$ and we wish to improve the first two objective function values (the first improve freely, and the second until the value $3.5$), keep the third one as it is, and let the fourth one worsen until $-4.2$. The corresponding reference point would then be as follows:
classification_reference_point = {
"f_1": problem.get_objective("f_1").ideal,
"f_2": 3.5,
"f_3": starting_point["f_3"],
"f_4": -4.2,
}
While the reference point defined above is enough to compute new solutions, we
can also utilize the function
infer_classifications
to double-check our classifications:
from desdeo.mcdm.nimbus import infer_classifications
print(f"Inferred classifications: {infer_classifications(problem, starting_point, classification_reference_point)}")
Inferred classifications: {'f_1': ('<', None), 'f_2': ('<=', 3.5), 'f_3': ('=', None), 'f_4': ('>=', -4.2)}
In the above output, we see that the tuple corresponding to each objective
function's symbol contains the classification as its first element, and an
aspiration/reservation level as its second element. The None values are
present since the classifications $<, =$ (and $0$ as well) can be inferred from
the properties of the problem.
Solving for new solutions¶
Once we have a starting point and a reference point corresponding to a valid classification,
we can solve for 1 to 4 new Pareto optimal solutions. For this, we invoke
solve_sub_problem defined
for NIMBUS, and choose to solve for 3 new solutions:
from desdeo.mcdm.nimbus import solve_sub_problems
results = solve_sub_problems(
problem,
current_objectives=starting_point,
reference_point=classification_reference_point,
num_desired=3,
solver=PyomoIpoptSolver,
)
print(f"Number of solutions {len(results)}")
print(f"Original reference point: {classification_reference_point}")
for i, result in enumerate(results):
print(f"Solution {i + 1}: F={result.optimal_objectives}")
Number of solutions 3
Original reference point: {'f_1': 6.34, 'f_2': 3.5, 'f_3': 5.015253701464943, 'f_4': -4.2}
Solution 1: F={'f_1': 6.184587700124071, 'f_2': 3.283334556353461, 'f_3': 5.015253801055101, 'f_4': -4.200000009641642}
Solution 2: F={'f_1': 6.3399980882569675, 'f_2': 3.4447026988269798, 'f_3': 0.3212587492880097, 'f_4': -9.696572625117863}
Solution 3: F={'f_1': 6.273460524017516, 'f_2': 3.367352404597743, 'f_3': 3.4051013435198696, 'f_4': -6.377107849693838}
From the output of the above cell, we see that our starting point and provided classifications have resulted in three new and clearly distinct (Pareto optimal) solutions. These differ because, as mentioned, different scalarization functions will generally lead to different solutions when the respective scalarized problem is solved, even if using the same preference information.
Next, after inspecting the new solutions, the decision maker may choose one of the solutions as the next solution to be classified (or even as the final one, if they are already happy). Alternatively, they may choose to store one or more of the solutions to an archive, from which they may also choose the next solution to be classified, if the archive had solutions saved to it prior to the current iteration. The decision maker may also choose to select two of any previously computed solutions in the NIMBUS method, and ask for a desired number of solutions to be generated between these two points.
Let us next consider a situation in which the decision maker would like to generate five
solutions between the starting point and the second solution computed ("Solution
2") based on the classifications provided in the first iteration. We use the
function
solve_intermediate_solutions
for this as demonstrated:
from desdeo.mcdm.nimbus import solve_intermediate_solutions
num_desired_intermediate = 5
intermediate_results = solve_intermediate_solutions(
problem,
solution_1=result_starting_point.optimal_variables,
solution_2=results[1].optimal_variables,
num_desired=num_desired_intermediate,
solver=PyomoIpoptSolver,
)
print(f"Number of solutions {len(intermediate_results)}")
print(f"Original reference point: {classification_reference_point}")
for i, result in enumerate(intermediate_results):
print(f"Solution {i + 1}: F={result.optimal_objectives}")
Number of solutions 5
Original reference point: {'f_1': 6.34, 'f_2': 3.5, 'f_3': 5.015253701464943, 'f_4': -4.2}
Solution 1: F={'f_1': 6.3177965989102605, 'f_2': 3.406465503009948, 'f_3': 1.724014934685246, 'f_4': -7.80410511995609}
Solution 2: F={'f_1': 6.295595115534031, 'f_2': 3.3719737994017005, 'f_3': 2.6950337813729064, 'f_4': -6.493468799173886}
Solution 3: F={'f_1': 6.27339363278114, 'f_2': 3.3407008078262788, 'f_3': 3.4069608093430572, 'f_4': -5.5322157575971636}
Solution 4: F={'f_1': 6.251192150007812, 'f_2': 3.3122141822300173, 'f_3': 3.951215614761292, 'f_4': -4.797169212086176}
Solution 5: F={'f_1': 6.228990667398271, 'f_2': 3.286155757080037, 'f_3': 4.380733438126935, 'f_4': -4.216967022329955}
Notice that the function solve_intermediate_solutions requires the decision
variables of the solutions between which to compute the points. Internally, a
number of linearly spaced decision vectors, corresponding to the desired number
of new solutions, are generated between solution_1 and solution_2. These
vectors are then used to evaluate the problem being solved, and the result of
these evaluations are used as reference points used in a scalarization function
to solve for new Pareto optimal solutions.
Solving intermediate solutions in NIMBUS
According to how the Synchronous NIMBUS method has been defined in its
original publication, the intermediate solutions are computed according
to the decision vector values generated between the two supplied
solutions. For problems with relatively linear objective functions and
continuous variables, this can make sense. However, in general, it
might be a better idea to generate the points directly in the objective
space of the problem between the objective function values of the
provided solutions. For this, DESDEO provides the function
rpm_intermediate_solutions,
which should be useful in any general case where such intermediate
solutions are needed. We have chosen to showcase the original way of
computing the intermediate solutions to not deviate from the original
publication.
Saving solutions¶
We have mentioned that the decision maker has the possibility to also save
solutions in the NIMBUS method. In a notebook environment, this can mean
storing the solutions to, e.g., a dict. But in practice, this can be
cumbersome. This is why in NIMBUS, and many other interactive methods in DESDEO,
we have not implemented specific functions necessarily for all the features of
an interactive method, but have instead focused on implementing the features
that are algorithmic and mathematical in nature, which are all available
for the implemented methods.
It makes much more sense for the archiving of solutions in NIMBUS to be part of
the application implementing the user interface for the method. Therefore, these
features are being implemented in the web-API and web-GUI of DESDEO instead.
Conclusions¶
We have seen two examples of how MCDM methods are implemented, and how they can be operated, in a notebook environment in DESDEO. The basic workflow consists of calling various functions, inspecting their output, and possibly utilizing the output in further calls to other functions. It is relatively easy to see how these functions can be combined in various ways to not just re-create the existing methods they are related to, but new ones as well.
We also noted that the input of a decision maker is central, and information generated by the functions implementing components of MCDM methods is often to be inspected by a decision maker. This makes a notebook interface very impractical, calling for a dedicated interface instead. In practice, we would use at least visualizations to better convey communicate information about the solutions to a decision maker. However, the purpose of this example has been to showcase how the algorithmic aspect of interactive methods can be utilized in DESDEO. Users are encouraged to utilize the user interfaces and visualizations provided in the Web-GUI of the framework, or their own, in real-life decision-support settings and studies involving human decision makers.