How to use the NAUTILI method¶
Introduction¶
NAUTILI is a trade-off-free interactive method developed for supporting multiple decision makers with conflicting preferences in solving multiobjective optimization problems.
Setting up the problem¶
While the implemented NAUTILI can be used for any kind of problem (analytical, data-based, etc.), it is recommended to consider the computational complexity of the objective functions so that it would not be too high as the whole group must wait each iteration for the computations. Another option is to use other methods in this framework to find an approximation of the Pareto front. This approximation can be used to make iterations faster.
To set up a problem, you can start with a problem object as described in "How to define a problem". Or you can use any of the existing test problems in DESDEO. Let us say that we have a group of five forest experts that wish to decide together how they want to manage their jointly owned forest holding. The problem is simulation based and therefore, to ease the computational costs, we use an approximation of the Pareto front. Very conveniently for our forest owners, this problem already exists as a testproblem in DESDEO. The problem has 3 objective functions. Objective 1 is called "stock" for the volume of wood stock in the forest. Objective 2 is called "harvest_value", meaning the value in euros that will be gained by harvesting the forest according to the plan. Objective 3 is called "npv", meaning net percent value of the currently standing forest.
Before starting the solution process, the group has to agree upon the number of steps they wish to conduct and how many votes are required to conduct a step backwards. For the sake of the example, the group wishes to take 5 steps and majority (3) is required to take a step backwards.
from desdeo.problem.testproblems import forest_problem_discrete
forest_problem = forest_problem_discrete()
total_steps = 5
You are now ready to use the NAUTILI method.
Using the method¶
Step 1: Import the relevant methods:¶
nautili_initto initialize the method. This method takes the problem object and creates the initial reachable ranges.nautili_all_stepsto run the method until the Pareto front is reached. This method takes the problem object, the return value ofnautili_init, the number of steps to take, and reference points from all DMs. It returns information about all the steps taken as a list ofNAUTILI_Responseobjects.NAUTILI_Responseis the object that contains information about the step taken. It is returned bynautili_init(single object) andnautili_all_steps(as a list). It contains the following fields:step_number: The step number.distance_to_front: The relative distance to the Pareto front at the end of the step. This is calculated as the ratio of the distance between thenavigation_pointandreachable_solutionand the distance between thenavigation_pointand thenadir point.navigation_point: The point from which the lower and upper reachable bounds are calculated for the current step.reachable_solution: The reachable solution at the end of the current path.reachable_bounds: The reachable ranges at the current step.reference_points: The reference points used in the step.improvement_directions: The improvement directions for each DM.group improvement direction: The group improvement direction.
import polars as pl
from desdeo.mcdm.nautili import (
NAUTILI_Response,
nautili_all_steps,
nautili_init,
)
from desdeo.mcdm.nautilus_navigator import (
step_back_index,
)
Step 2: Initialize the method:¶
Initialize the method by calling nautili_init with the problem object.
initial_response = nautili_init(forest_problem)
At this point, the analyst may use the initial_response to visualize the reachable ranges and the reachable solutions to the DMs. Get the aspiration levels from the DMs as a dictionary with a key to indicate each DM's dictionary containing objective names as keys and the aspiration levels as values.
Step 3: Run the method:¶
Run the method by calling nautili_all_steps with the problem object, the return value of nautili_init, the number of steps to take, and the aspiration levels. You can also provide your preferred solver, using the BaseSolver class.
# Set preferences and parameters
reference_points = {
"DM1": {
"stock": 2850,
"harvest_value": 290000,
"npv": 780000,
},
"DM2": {
"stock": 3100,
"harvest_value": 25000.5,
"npv": 77000,
},
"DM3": {
"stock": 2900,
"harvest_value": 50005,
"npv": 80000,
},
"DM4": {
"stock": 3100,
"harvest_value": 22000,
"npv": 850000,
},
"DM5": {
"stock": 3100,
"harvest_value": 29000,
"npv": 76500,
},
}
total_steps = 5
# Run the method
all_responses: list[NAUTILI_Response] = nautili_all_steps(
forest_problem,
total_steps,
reference_points,
[initial_response], # Note that this is a list of NAUTILI_Response objects
)
# Append the responses to the archive of responses
all_responses = [initial_response, *all_responses]
At this point, the analyst may use the all_responses to visualize the reachable ranges and the reachable solutions of each step to each of the DMs. Even though all steps have been evaluated at this point, the analyst (or the GUI) should only visualize these steps one at a time.
This will allow the DM to think that they are navigating the solution space without it consuming too much time.
Note, that according to the NAUTILI assumptions, we do not share the preferences of any DM to any other DM. However, if sharing of preference information is reasonable in your problem scenario, the analyst can share them e.g., via the GUI as a separate visualization.
One way to get the information to be visualized:
lower_bounds = pl.DataFrame([response.reachable_bounds["lower_bounds"] for response in all_responses])
upper_bounds = pl.DataFrame([response.reachable_bounds["upper_bounds"] for response in all_responses])
reference_point = pl.DataFrame([response.reference_points for response in all_responses[1:]])
print(f"lower, upper bounds {lower_bounds}, {upper_bounds} and reference_point {reference_point}")
lower, upper bounds shape: (6, 3)
┌─────────────┬───────────────┬─────────────┐
│ stock ┆ harvest_value ┆ npv │
│ --- ┆ --- ┆ --- │
│ f64 ┆ f64 ┆ f64 │
╞═════════════╪═══════════════╪═════════════╡
│ 834.908681 ┆ 0.0 ┆ 70547.89613 │
│ 1043.643571 ┆ 8136.624756 ┆ 72649.26423 │
│ 1252.378461 ┆ 16273.249512 ┆ 74750.63233 │
│ 1461.113352 ┆ 24409.874268 ┆ 76852.00043 │
│ 1669.848242 ┆ 32546.499024 ┆ 78953.36853 │
│ 1878.583132 ┆ 40683.12378 ┆ 81054.73663 │
└─────────────┴───────────────┴─────────────┘, shape: (6, 3)
┌─────────────┬───────────────┬─────────────┐
│ stock ┆ harvest_value ┆ npv │
│ --- ┆ --- ┆ --- │
│ f64 ┆ f64 ┆ f64 │
╞═════════════╪═══════════════╪═════════════╡
│ 3422.75801 ┆ 74114.92657 ┆ 91494.0437 │
│ 3103.579382 ┆ 65961.48171 ┆ 88335.81398 │
│ 2800.563249 ┆ 59783.94725 ┆ 86500.78807 │
│ 2471.797603 ┆ 52830.58596 ┆ 84520.70679 │
│ 2167.277355 ┆ 46479.51675 ┆ 82573.27019 │
│ 1878.583132 ┆ 40683.12378 ┆ 81054.73663 │
└─────────────┴───────────────┴─────────────┘ and reference_point shape: (5, 5)
┌───────────────────┬───────────────────┬───────────────────┬───────────────────┬──────────────────┐
│ DM1 ┆ DM2 ┆ DM3 ┆ DM4 ┆ DM5 │
│ --- ┆ --- ┆ --- ┆ --- ┆ --- │
│ struct[3] ┆ struct[3] ┆ struct[3] ┆ struct[3] ┆ struct[3] │
╞═══════════════════╪═══════════════════╪═══════════════════╪═══════════════════╪══════════════════╡
│ {2850,290000,7800 ┆ {3100,25000.5,770 ┆ {2900,50005,80000 ┆ {3100,22000,85000 ┆ {3100,29000,7650 │
│ 00} ┆ 00} ┆ } ┆ 0} ┆ 0} │
│ {2850,290000,7800 ┆ {3100,25000.5,770 ┆ {2900,50005,80000 ┆ {3100,22000,85000 ┆ {3100,29000,7650 │
│ 00} ┆ 00} ┆ } ┆ 0} ┆ 0} │
│ {2850,290000,7800 ┆ {3100,25000.5,770 ┆ {2900,50005,80000 ┆ {3100,22000,85000 ┆ {3100,29000,7650 │
│ 00} ┆ 00} ┆ } ┆ 0} ┆ 0} │
│ {2850,290000,7800 ┆ {3100,25000.5,770 ┆ {2900,50005,80000 ┆ {3100,22000,85000 ┆ {3100,29000,7650 │
│ 00} ┆ 00} ┆ } ┆ 0} ┆ 0} │
│ {2850,290000,7800 ┆ {3100,25000.5,770 ┆ {2900,50005,80000 ┆ {3100,22000,85000 ┆ {3100,29000,7650 │
│ 00} ┆ 00} ┆ } ┆ 0} ┆ 0} │
└───────────────────┴───────────────────┴───────────────────┴───────────────────┴──────────────────┘
This will give you the lower and upper bounds of the reachable ranges and the reference points used in each step as a DataFrame.
!!! note Maximization is already handled in all of these steps. You should provide the real (meaningful) values of the objectives to the method. The method will handle the maximization internally. Similarly, the returned values are already the true objective values and can be visualized to the DM directly.
Step 4: Take a step back¶
At any iteration (except the first one), the DMs have the option to begin a vote for taking a step backwards in the method. After a vote has been initiated, every DM can vote for it or against it. The voting can be implemented in the GUI or the analyst can manually gather the votes from the DMs. Let us say that in our case, 4 DMs wish to take a step backwards, hence, according to the majority threshold set earlier, we take a step backwards.
It does not matter when they make this choice, the all_responses list already contains all possible steps. The analyst should copy the response from the step that the group wants to go back to and append it to the all_responses list. Then, nautili_all_steps can be called with the new aspiration levels and the number of remaining steps. All DMs who wish to change their preferences can do so, and if any DM does not wish to change their preference, the earlier preference of that DM can be used instead. Note that any provided reference points must be strictly better than the current navigation point for each objective.
go_back_to = 3
steps_remaining = total_steps - go_back_to
# Set preferences and parameters
# Reference points must be strictly better than the navigation point at step 3
reference_points = {
"DM1": {
"stock": 2800,
"harvest_value": 30000,
"npv": 80000,
},
"DM2": {
"stock": 3000,
"harvest_value": 25200.5,
"npv": 78000,
},
"DM3": {
"stock": 2900,
"harvest_value": 50005,
"npv": 90000,
},
"DM4": {
"stock": 3100,
"harvest_value": 26000,
"npv": 90000,
},
"DM5": {
"stock": 3200,
"harvest_value": 29000,
"npv": 78000,
},
}
all_responses = [
*all_responses,
all_responses[step_back_index(all_responses, go_back_to)],
]
new_responses = nautili_all_steps(
forest_problem,
steps_remaining,
reference_points,
all_responses,
)
all_responses = [*all_responses, *new_responses]
Note, as all responses are appended to the same list, finding out the index of the step to go back to is not trivial. The step_back_index function can be used to find the index of the step to go back to. It finds all responses that have a step_number equal to the go_back_to and returns the index of the last such response. This is because the last such response is the one that was appended to the all_responses list most recently.
The next iteration after the preferences were changed contains the group_improvement_direction, that is used for all rest of the iterations as the DMs do not change their preferences:
group_improvement_direction = all_responses[step_back_index(all_responses, go_back_to) + 1].group_improvement_direction
print(f"Group improvement direction {group_improvement_direction}")
Group improvement direction {'stock': np.float64(-1538.88664844), 'harvest_value': np.float64(-7631.225732000001), 'npv': np.float64(-6347.99957)}
Moreover, the final Pareto optimal solution reached can be found from the NAUTILI_Response:
final_solution = all_responses[-1].reachable_solution
print(f"Final reachable solution {final_solution}")
Final reachable solution {'stock': 2342.140341, 'harvest_value': 28492.806, 'npv': 78350.26474}
Advanced Usage: NAUTILI with Fair Preference Aggregation¶
By default, NAUTILI aggregates the group's reference points by taking the arithmetic mean of the individual directions of simultaneous improvements.
One can also use local preference models (like the Additive or Symmetric Cones models) and enforce Max-Min fairness to aggregate a group reference point, that can then be used to determine the collective direction of improvement.
To do this, one needs to use nautili_step and the grp_subproblem module.
Below is an example using the ZDT1 problem where we calculate the fair Group Reference Point (GRP) iteratively at each step.
Step 1: Setup and Define Preferences¶
First, import the necessary tools and set up the problem. In this example, we assume three decision makers have already provided their preferred reference points.
import numpy as np
from desdeo.gdm.grp_subproblem import (
additive_preference_constraints,
build_grp_subproblem,
maxmin_fairness_constraints,
maxmin_fairness_objective,
)
from desdeo.mcdm.nautili import nautili_init, nautili_step
from desdeo.problem import get_ideal_dict, get_nadir_dict, objective_dict_to_numpy_array
from desdeo.problem.testproblems import zdt1
from desdeo.tools.utils import PyomoIpoptSolver
# Setup the problem and global boundaries
problem = zdt1(30)
ideal = objective_dict_to_numpy_array(problem, get_ideal_dict(problem))
nadir = objective_dict_to_numpy_array(problem, get_nadir_dict(problem))
# The DMs provide their reference points
dm_rps = np.array(
[
[0.71, 0.95],
[0.75, 0.83],
[0.94, 0.69],
]
)
total_steps = 3
Step 2: Initialize NAUTILI¶
Initialize the NAUTILI method to generate the starting point (the Current Iteration Point, or CIP).
init_response = nautili_init(problem, solver=PyomoIpoptSolver)
current_cip_dict = init_response.navigation_point
cip_arr = objective_dict_to_numpy_array(problem, current_cip_dict)
Step 3: Solve for the Fair Group Reference Point (GRP)¶
Pass the DMs' reference points to build_grp_subproblem and specify a local preference model (in this case, additive_preference_constraints). The solver finds the exact point that maximizes the Rawlsian fairness among the group based on their preferences.
prob = build_grp_subproblem(
rps=dm_rps,
cip=cip_arr,
ideal=ideal,
nadir=nadir,
preference_factory=additive_preference_constraints, # Or use symmetric_cones_preference_constraints
fairness_constraints_factory=maxmin_fairness_constraints,
fairness_objective_factory=maxmin_fairness_objective,
)
# Solve to maximize fairness (alpha)
res = PyomoIpoptSolver(prob).solve("obj_alpha_min")
grp_arr = np.array([res.optimal_variables["cgrp_0"], res.optimal_variables["cgrp_1"]])
print(f"Fair Group Reference Point: {np.round(grp_arr, 4)}")
Fair Group Reference Point: [0.8056 0.7891]
Step 4: Execute a Single NAUTILI Step¶
Subtract the newly calculated fair GRP from the Current Iteration Point to determine the collective direction of simultaneous improvements. By passing this to nautili_step, we step along this direction.
# Formulate the Group Improvement Direction (CIP to GRP)
group_improvement_arr = cip_arr - grp_arr
group_improvement_dict = {obj.symbol: group_improvement_arr[i] for i, obj in enumerate(problem.objectives)}
# Execute a single NAUTILI step
step_res = nautili_step(
problem=problem,
steps_remaining=total_steps,
step_number=1,
nav_point=current_cip_dict,
solver=PyomoIpoptSolver,
group_improvement_direction=group_improvement_dict,
)
next_cip = objective_dict_to_numpy_array(problem, step_res.navigation_point)
print(f"Step 1 completed. Iteration point moved to: {np.round(next_cip, 4)}")
Step 1 completed. Iteration point moved to: [0.8033 0.7866]
You can repeat Steps 3 and 4 in a loop for the remaining iterations, updating the DMs' reference points at each step as needed during the interactive process.