JuMENTO: Multi-Objective Optimization in Julia

JuMENTO.jl is a Julia-based mathematical programming framework designed for multi-objective optimization. Built to integrate seamlessly with the JuMP.dev ecosystem, it provides deterministic exact methods to generate, analyze, and visualize Pareto frontiers.

🚀 Key Features

• Exact Optimization Methods: Native implementations of the Augmented $\epsilon$-Constraint family:
  • AUGMECON
  • AUGMECON 2
  • SAUGMECON
• Quality Metrics: Tools for evaluating and assessing the quality of computed Pareto Frontiers.
• Advanced Visualization: Built-in support via the MultiPlots module to visualize high-dimensional objective spaces (2, 3, or more objectives) using interactive PlotlyJS charts (including Radar, Parallel Coordinates, and Scatter plots).

---

Table of Contents

• Installation
• How to Use
  • Build a Model
  • Augmented ε-Constraint Method (AUGMECON)
    • Configure User Options for AUGMECON
    • Solve with AUGMECON
• Evaluating Frontiers
  • Plot Results
  • Metrics for Evaluation
• Example Problems
• References

---

Installation

For installation, you can download directly from github as follows:

using Pkg
Pkg.add("JuMENTO")

---

How to Use

Build a Model

To solve problems with JuMENTO, you must first define a JuMP model (see JuMP Documentation and Multiobjective Tutorial). Below is an example showing how to build a model for use with JuMENTO:

using JuMP, HiGHS

import MultiObjectiveAlgorithms as MOA

using JuMENTO

model = Model(() -> MOA.Optimizer(HiGHS.Optimizer))

@variable(model, x[1:2] >= 0) 

@constraints model begin
    c1, x[1] <= 20
    c2, x[2] <= 40
    c3, 5*x[1] + 4*x[2] <= 200
end
@objective(model, Max, [x[1],  3*x[1] + 4*x[2]])

---

Augmented ε-Constraint Method (AUGMECON)

The AUGMECON method is an exact approach that generates the Pareto frontier by solving a series of single-objective optimization problems. It is based on the ε-constraint method, which transforms a multi-objective problem into a single-objective one by treating all but one objective as constraints with specified bounds (ε values).

For further details on the methods, please refer to Mavrotas (2009) paper for the original AUGMECON, Mavrotas and Florios (2013) paper for AUGMECON2, and Zhang and Reimann (2014) paper for SAUGMECON.

Configure User Options for AUGMECON

When using an AUGMECON-based method, you can control its behavior by adding attributes to the model. Some options are required; others are optional. The table below summarizes the available parameters:

Parameter	Description	Default
GridPoints	Number of grid divisions for ε-constraint	Required
Nadir	Nadir point	Auto computed
Penalty	Numeric value that is used by the AUGMECON	1e-3
AugmeconType	Used to know which AUGMECON will be used	1
PrintLevel	Logging detail (0 or 1)	0
Atol	Tolerance used when determining dominance relations between solutions	1e-8

set_attribute(model, MOA.Algorithm(), MethodAUGMECON.Augmecon(10)) # 10 grid points
set_attribute(model, MethodAUGMECON.AugmeconType(), 2) # To use AUGMECON 2
set_attribute(model, MethodAUGMECON.GridPoints(), 20) # If one wants to change

To use:

• AUGMECON: set_attribute(model, MethodAUGMECON.AugmeconType(), 1)
• AUGMECON 2: set_attribute(model, MethodAUGMECON.AugmeconType(), 2)
• SAUGMECON: set_attribute(model, MethodAUGMECON.AugmeconType(), 3)

Solve with AUGMECON

Solve the model above, its only necessary to call optimize!. For additional details, check MultiObjectiveAlgorithms.jl.

---

Evaluating Frontiers

To evaluate the quality of the obtained Pareto frontiers, you can use the plotting and metrics tools provided by JuMENTO. These tools allow you to visualize the trade-offs between objectives and quantitatively assess the performance of different algorithms.

Its important to clarify that the methods implemented here assume the frontier set $F$ is a $m × n$ matrix, where each of the $m$ rows corresponds to an specific objective, and each of the $n$ solutions is represented by a column.

Plot Results

This module leverages PlotlyJS.jl to generate interactive visualizations of Pareto frontiers.

The JuMENTO.MultiPlots module provides a suite of plotting functions designed to analyze objective space trade-offs. The implemented visualization types include:

• Scatter plots (2 to 3 objectives);
• Parallel coordinate plots;
• Radar charts (Spider plots);
• Level diagrams.

The following sections show how to use some of the plotting functions defined in the JuMENTO.MultiPlots module. For a comprehensive technical overview of specific parameters, please refer to the internal documentation for each function.

Radar Charts

using JuMENTO

frontier_set = [
    7 4 2;
    10 5 10;
    4 10 21
]

name_set = ["Product A", "Product B", "Product C"] # Optional, default is "Solution 1", "Solution 2", ...
cats = ["Cost", "Quality", "Time"] # Optional, default is "Objective 1", "Objective 2", ...
sens= [:min, :max, :min] # Optional, default is `:max` for all objectives
eps=0.2 # Optional, default is 0.2. This value is used to expand slightly the normalization range to improve visualization

fig = MultiPlots.radar(frontier_set, sense_set = sens, categories=cats, name_set=name_set, eps=eps)

For this frontier, the figure would look like this:

This visualization enables quantitative evaluation of product performance profiles. For instance, Product C occupies a dominant position regarding Quality and Cost; however, it exhibits significantly higher latency (Time), representing a clear trade-off in the objective space.

Parallel Coordinate Plots

using JuMENTO

frontier_set = [
    1 2 3 4 5 6 7 8 9 10.0;
    10 9 8 7 6 5 4 3 2 1;
    4 10 21 4 21 23 4 2 9 10
]

cats = ["Profit", "Quality", "Time"] # Optional, default is f_1, f_2 ...
sens = [:max, :max, :min] # Optional, default is :max for every objective
names = ["Product $j" for j in axes(frontier_set, 2)] # Optional, default is 'Solution 1', 'Solution 2' ...

fig = MultiPlots.parallel_coordinates(frontier_set, categories=cats, sense_set=sens, name_set=names)

The resulting figure would look like this:

Scatter Plots

using JuMENTO

v1 = [92.0 50.0 2.0 7.0 91.0; 20.0 91.0 100.0 97.0 81.0]
v2 = [10 45 81 91 93; 99 94 91 81 30]
v3 = [100.0 88.0 98.0 95.0; 80.0 100.0 89.0 99.0]

cats = ["Profit", "Quality"] # Optional, default is "f_1", "f_2"...
names = ["NSGA-2", "NSGA-3", "AUGMECON-2"] # Optional, default is "Method 1", "Method 2"...

fig = MultiPlots.scatter([v1, v2, v3], categories=cats, name_set=names)

The resulting figure would look like this:

Level Diagrams

using JuMENTO

cats = ["Profit", "Quality", "Costs"]
names = ["NSGA-2", "NSGA-3", "AUGMECON-2"]

sens = [:max, :max, :min]

v1 = [63.0 62.0 87.0 20.0 100.0 78.0 92.0 99.0; 92.0 20.0 87.0 44.0 66.0 64.0 100.0 80.0; 20.0 2.0 74.0 2.0 43.0 12.0 80.0 36.0]
v2 = [42.0 99.0 78.0 67.0 85.0 4.0 40.0 93.0; 98.0 17.0 5.0 19.0 90.0 82.0 80.0 73.0; 84.0 72.0 8.0 15.0 16.0 12.0 10.0 80.0]
v3 = [92.0 93.0 89.0 86.0 95.0 93.0 10.0 12.0 73.0 99.0; 63.0 9.0 46.0 99.0 99.0 87.0 47.0 58.0 1.0 94.0; 18.0 28.0 15.0 4.0 98.0 76.0 1.0 3.0 3.0 85.0]

fig = MultiPlots.level_diagrams([v1, v2, v3], categories=cats, sense_set=sens, name_set=names)

The resulting figure would look like this:

Metrics for Evaluation

WARNING: hypervolume metric is still in development, and may be slow to calculate for frontiers with lots of objetives

To compare the performance of different algorithms, specific multiobjective metrics are used to assess the quality of the solution sets obtained. This assessment typically considers aspects such as the dispersion of solutions and their distance from the Pareto frontier.

The JuMENTO repository includes the implementation of common multi-objective metrics:

• Spacing (SP) Measures the variation in distances between each solution in the evaluated set and its nearest neighbor in the reference set. Smaller values are desirable.
• Generalized Distance (GD) Calculates the p-norm of euclidean distances from each solution in the evaluated set to its nearest neighbor in the reference set. Smaller values indicate that the evaluated set is closer to the reference set, which is desirable.
• Diversity (Δ) Measures the dispersion of the solution set. Smaller values indicate better performance.
• Hypervolume (HV) Computes the hypervolume of the objective space dominated by the solution set bounded by a reference point. Larger values indicate better performance.
• Error Ratio (ER) Computes the proportion of solutions in the evaluated set that are not present in the reference set. Smaller values indicate better performance.

The metrics can be applied by calling their respective functions, as shown below:

using JuMENTO: Metrics

frontier_set = [3 6 9; 15 9 4.0]
reference_set = [1 2 3 4 5 6 7 8 9 10; 10 9 8 7 6 5 4 3 2 1.0]
nadir = [10.1, 15.15]

sp = Metrics.spacing(frontier_set, reference_set)
# 2.0126831744720173

gd = Metrics.general_distance(frontier_set, reference_set)
# 2.0816659994661326

dm = Metrics.diversity(frontier_set, reference_set)
# 0.39696030366206303

er = Metrics.error_ratio(frontier_set, reference_set)
# 1.0

hv = Metrics.hypervolume(frontier_set, nadir)
# 31.165

---

Example Problems

To test the implemented multi-objective optimization methods, you can access the "test" folder and check their functionality.

• Bi-objective: Simple linear model with two objectives
• Tri-objective: Energy planning model with three objectives
• mokp: A Multi-objective Knapsack Problem

---

References

AUGMECON

• Mavrotas, G. (2009). "Effective implementation of the epsilon-constraint method in Multi-Objective Mathematical Programming problems." Applied Mathematics and Computation, 213(2), 455–465. DOI: 10.1016/j.amc.2009.03.027
• Mavrotas, G., & Florios, K. (2013). "An improved version of the augmented ε-constraint method (AUGMECON2) for finding the exact Pareto set in Multi-Objective Integer Programming problems." Applied Mathematics and Computation, 219(18), 9652–9669. DOI: 10.1016/j.amc.2013.03.002
• Zhang, W., & Reimann, M. (2014). A simple augmented ∊-constraint method for multi-objective mathematical integer programming problems. European Journal of Operational Research, 234(1), 15–24. DOI: 10.1016/j.ejor.2013.09.001

Additional content

• Coello Coello, C. A. (2002). "Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art." Computer Methods in Applied Mechanics and Engineering, 191(11–12), 1245–1287. https://doi.org/10.1016/S0045-7825(01)00323-1
• Reynoso-Meza, G., Blasco, X., Sanchis, J., & Herrero, J. M. (2013). Comparison of design concepts in multi-criteria decision-making using level diagrams. Information Sciences, 221, 124–141. https://doi.org/10.1016/j.ins.2012.09.049
• Silva, Y. L. T. V., Herthel, A. B., & Subramanian, A. (2019). "A multi-objective evolutionary algorithm for a class of mean-variance portfolio selection problems." Expert Systems with Applications, 133, 225–241. https://doi.org/10.1016/j.eswa.2019.05.018
• JuMP Documentation: https://jump.dev

---