Problem solvers

Once we have our data prepared for analysis and processing, we can employ a set of Solvers for the task. The MODA library implements variety of hypervolume centered methods. This section lists all the solvers and provides simple code snippets for each of the algorithms.

Solvers

Let’s start by listing all the base types. The library uses a hierarchical structure, each task is executed with a dedficated solver. The solver accepts a set of hyperparameters and returns a result embedded in an object of a dedicated type. Before we move onto the detailed solvers, let’s describe the base classes.

Base Solver Class

class Solver

The base class providing an interface and utility methods for solving optimization problems.

DataSet *currentlySolvedProblem: Pointer to the dataset currently being processed.

DataSetParameters *currentSettings: Pointer to the configuration settings for the current problem.

void (*StartCallback)(DataSetParameters problemSettings, std::string SolverMessage): Called when the solver starts execution.

void (*IterationCallback)(int currentIteration, int totalIterations, Result *stepResult): Called at the end of each iteration to report progress.

void (*EndCallback)(DataSetParameters problemSettings, Result *stepResult): Called upon the completion of the solving process.

Public Methods

virtual Result *Solve(DataSet *problem, SolverParameters settings): Abstract Solve function. Each solver implements it to solve the problem and return a result.

Protected Methods

void prepareData(DataSet *problem, SolverParameters settings): Prepares operational data structures before starting the solver.

The moda library utilizes a configuration system for various optimization solvers. All specific solver settings inherit from the base SolverParameters class.

Base Solver Parameters Class

class SolverParameters

The foundational class for all solver configurations.

enum ReferencePointCalculationStyle

Enumeration of all methods for calculating the reference points. Depending on the optimization direction, the worse and better reference points are set either to the point based on either minimum or maximum values, approprietly

enumerator epsilon

For the dataset \(X \subseteq \mathbb{R}^n\), define the minimum and maximum values for each dimension \(i\) as:

\[m_i = \min_{x \in X} (x_i), \quad M_i = \max_{x \in X} (x_i) .\]

The adjusted reference points are defined as:

\[ \begin{align}\begin{aligned}\{ m_i - \epsilon \mid 0 < i \le n \},\\\{ M_i + \epsilon \mid 0 < i \le n \} .\end{aligned}\end{align} \]

The parameter \(\epsilon\) is currently set to a default value of 0.001. You can modify this value by updating the corresponding constant in the include.h file.

enumerator tenpercent

For the dataset \(X \subseteq \mathbb{R}^n\), define the minimum and maximum values for each dimension \(i\) as:

\[m_i = \min_{x \in X} (x_i), \quad M_i = \max_{x \in X} (x_i) .\]

The adjusted reference points are defined as:

\[ \begin{align}\begin{aligned}\{ m_i - 0.1 \cdot |m_i - M_i| \mid 0 < i \le n \},\\\{ M_i + 0.1 \cdot |m_i - M_i| \mid 0 < i \le n \} .\end{aligned}\end{align} \]

enumerator zeroone

For the dataset \(X \subseteq \mathbb{R}^n\), the reference points are defined as:

\[ \begin{align}\begin{aligned}\{ 0 \mid 0 < i \le n \},\\\{ 1 \mid 0 < i \le n \} .\end{aligned}\end{align} \]

enumerator userdefined

The reference points are defined by user prior to the solver execution. In order to use this setting declare the worseReferencePoint and betterReferencePoint values.

enumerator exact

For the dataset \(X \subseteq \mathbb{R}^n\), the reference points are defined as:

\[ \begin{align}\begin{aligned}\{ \min_{x \in X} (x_i) \mid 0 < i \le n \},\\\{ \max_{x \in X} (x_i) \mid 0 < i \le n \} .\end{aligned}\end{align} \]

enumerator pymoo

For the dataset \(X \subseteq \mathbb{R}^n\), define the minimum and maximum values for each dimension \(i\) as:

\[m_i = \min_{x \in X} (x_i), \quad M_i = \max_{x \in X} (x_i) .\]

The adjusted reference points are defined as:

\[ \begin{align}\begin{aligned}\{ 0 \mid 0 < i \le n \},\\\{ 11 \mid 0 < i \le n \} .\end{aligned}\end{align} \]

ReferencePointCalculationStyle BetterReferencePointCalculationStyle: How to calculate the better reference point (see the enum above).

ReferencePointCalculationStyle WorseReferencePointCalculationStyle: How to calculate the worse reference point (see the enum above).

bool callbacks: Toggle to enable or disable iteration callbacks.

int MaxEstimationTime: Maximum time allowed for the estimation process (in ms).

Point *worseReferencePoint;: User defined reference point;for minimization: lower boundary point of the problem; for maximization: upper boundary point of the problem

Point *betterReferencePoint;: User defined reference point; for minimization: upper boundary point of the problem; for maximization: lower boundary point of the problem

Point *GetWorseReferencePoint(DataSet *set): This function returns the worse reference point according to the chosen method.

Point *GetBetterReferencePoint(DataSet *set): This function returns the better reference point according to the chosen method.

Base Result Class

The base result class is very simple it only denotes the elapsed time and information wether this is the final or intermediate result. Additionally it carries meta information on the method name and auxiliary, additional denotion of the result type.

class Result

Represents the output and metadata for a calculation process.

int ElapsedTime: Time passed since the beginning of the calculation given in ms.

bool FinalResult: Is this the final result of the calculation.

enum ResultType

Enumeration of all result types.

enumerator Hypervolume

enumerator Estimation

enumerator Contribution

enumerator SubsetSelection

enumerator R2

ResultType type: Additional annotation of the result type (auxiliary).

std::string methodName: The name of the method used for the calculation.

Dedicated Solvers

MODA library uses a hierarchical structure of solvers designated for various tasks. This set of derived classes servers as a programming interface to the library computation kernel.

_images/solvers_umls.png — Solvers Hierarchy.

_images/results.png — Results Hierarchy.

Improved Quick Hypervolume

Classes

class IQHVSolver : public Solver : This class implements exact hypervolume calculation as described in [Andrzej Jaszkiewicz. 2018. Improved quick hypervolume algorithm. Comput. Oper. Res. 90, C (February 2018), 72–83. https://doi.org/10.1016/j.cor.2017.09.016]

class IQHVParameters : public SolverParameters : Settings for IQHV - a method of finding exact hypervolume. This class includes no additional parameters.

class HypervolumeResult : public Result 

Calculated hypervolume result inheriting from the base Result class.

float HyperVolume: The resulting hypervolume value calculated by the process.

Code snippet#include <moda\DataSet.h>
#include <moda\IQHVSolver.h>
#include <moda\SolverParameters.h>
#include <moda\Point.h>
#include <iostream>
int main()
{
   moda::DataSet* dataSet = moda::DataSet::LoadFromFilename("sample_file");
   dataSet->normalize();
   moda::IQHVSolver solver;
   moda::IQHVParameters* parameters = new moda::IQHVParameters(moda::SolverParameters::ReferencePointCalculationStyle::zeroone, moda::SolverParameters::ReferencePointCalculationStyle::zeroone);
   moda::HypervolumeResult* result = solver.Solve(dataSet, *parameters);
   std::cout << "Hypervolume: " << result->HyperVolume << std::endl;
   return 0;
}
//Result:
//   Hypervolume: 0.859209

Distance based hypevolume estimation

Classes

class DBHVESolver : public Solver 

This class implements the hypervolume estimation as described in [Jaszkiewicz, Andrzej & Zielniewicz, Piotr. (2024). Improving the Efficiency of the Distance-Based Hypervolume Estimation Using ND-Tree. IEEE Transactions on Evolutionary Computation. PP. 1-1. 10.1109/TEVC.2024.3391857.]

class DBHVEParameters : public SolverParameters 

Settings for DBHVE - a method of finding hypervolume estimation expressed as a real number.

unsigned MCIterations: Number of iterations.

class BoundedResult : public Result 

Result class providing bounded estimation values, inheriting from Result. This class will be used for all “bounded” result types.

bool Guaranteed: Flag indicating if the lower and upper bounds are exact. If true, the precise value is guaranteed to be within these bounds. This is typically false for Monte Carlo methods.

float LowerBound: Lower bound of the hypervolume.

float UpperBound: Upper bound of the hypervolume.

float HyperVolumeEstimation: The estimated hypervolume value.

Code Snippet

Quick Extreme Hypervolume Contributon

Classes

class QEHCSolver : public Solver 

This class implements an algorithm for finding the extreme hypervolume contributor. It is described in [Andrzej Jaszkiewicz and Piotr Zielniewicz. 2021. Quick extreme hypervolume contribution algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ‘21). Association for Computing Machinery, New York, NY, USA, 412–420. https://doi.org/10.1145/3449639.3459394]

class QEHCParameters : public SolverParameters 

Parameters for the QEHC Solver.

enum SearchSubjectOption

enumerator MinimumContribution: The QEHC process will search for minimum contributor.

enumerator MaximumContribution: The QEHC process will search for maximum contributor.

enumerator Both: The QEHC process will search for both maximum and minimum contributor at once (not implemented).

class QEHCResult : public Result 

Result class specific to Quick Hypervolume Contribution (QEHC) metrics, inheriting from Result.

float MaximumContribution: The lowest contribution value for any single point in the set.

float MinimumContribution: The highest hypervolume (HV) contribution value for any single point in the set.

int MaximumContributionIndex: The index of the point associated with the highest HV contribution value.

int MinimumContributionIndex: The index of the point associated with the lowest HV contribution value.

Code snippet

#include <moda\DataSet.h>
#include <moda\QEHCSolver.h>
#include <moda\SolverParameters.h>
#include <moda\Point.h>
#include <moda\Result.h>
#include <iostream>
int main()
{
   moda::DataSet* dataSet = moda::DataSet::LoadFromFilename("sample_file");
   dataSet->normalize();
   moda::QEHCSolver solver;
   moda::QEHCParameters* parameters = new moda::QEHCParameters(moda::SolverParameters::ReferencePointCalculationStyle::zeroone, moda::SolverParameters::ReferencePointCalculationStyle::zeroone);
   parameters->SearchSubject = moda::QEHCParameters::SearchSubjectOption::MaximumContribution;
   moda::QEHCResult* result = solver.Solve(dataSet, *parameters);
   std::cout << "Maximum contribution: " << result->MaximumContribution << std::endl;
   std::cout << "Maximum contributor index: " << result->MaximumContributionIndex << std::endl;
   return 0;
}
//Result:
//   Maximum contribution: 0.00114615
//   Maximum contributor index: 21

Hypervolume Subset Selection

Classes

class HSSSolver : public Solver 

This class implements a method of finding a subset of points with best estimated hypervolume, according to the algorithm described in [Andrzej Jaszkiewicz, Piotr Zielniewicz: Lazy Hypervolume Subset Selection Algorithm with Contributions Update. GECCO Companion 2025: 223-226]

class HSSParameters : public SolverParameters 

Configuration for HSS solvers.

enum StoppingCriteriaType

Enumeration of various HSS termination criteria.

enumerator SubsetSize: The process will terminate once a specified size of the set of selected points has been reached.

enumerator Time: The process will terminate once a specific time of execution has been reached (note, the time is checked upon the start of iteration, which selects a point, at least one point will be added/substracted).

enum SubsetSelectionStrategy

Enumeration of HSS processing strategies.

enumerator Incremental: Start with an empty set. In every iteration add a point, which would maximize the hypervolume of the subset.

enumerator Decremental: Start with all points. In every iteration remove a point, which would reduce the hypervolume by the minimal value.

StoppingCriteriaType StoppingCriteria: HSS termination criteria.

SubsetSelectionStrategy Strategy: HSS processing strategy.

Code Snippet

#include <moda\DataSet.h>
#include <moda\HSSSolver.h>
#include <moda\SolverParameters.h>
#include <moda\Point.h>
#include <moda\Result.h>
#include <iostream>
int main()
{
   moda::DataSet* dataSet = moda::DataSet::LoadFromFilename("sample_file");
   dataSet->normalize();
   moda::HSSSolver solver;
   moda::HSSParameters* hssparams = new moda::HSSParameters(moda::SolverParameters::ReferencePointCalculationStyle::zeroone, moda::SolverParameters::ReferencePointCalculationStyle::zeroone);
   hssparams->Strategy = moda::HSSParameters::SubsetSelectionStrategy::Incremental;
   hssparams->StoppingSubsetSize = 10;
   hssparams->StoppingCriteria = moda::HSSParameters::StoppingCriteriaType::SubsetSize;
   auto result = solver.Solve(dataSet, *hssparams);
   std::cout << "Selected points: [";
   for (int i = 0; i < 10; i++)
   {
      std::cout << result->selectedPoints[i] << ",";
   }
   std::cout << "]";
   return 0;
}
//Result:
//   Selected points: [48,349,246,217,296,358,376,53,478,7,]

Quick Hypervolume Guaranteed Bounds Approximation

Classes

class QHV_BRSolver : public Solver 

class QHV_BRParameters : public SolverParameters : Settings for QHV-BR - a method of finding hypervolume estimation expressed as lower and upper bounds. This method requires no additional parameters.

This class uses the BoundedResult class.

Code Snippet

Quick Hypervolume Bounds Estimation with Priority Queue

Classes

class QHV_BQSolver : public Solver 

class QHV_BQParameters : public SolverParameters 

Settings for QHV-BQ - a method of finding hypervolume estimation expressed as lower and upper bounds.

SwitchParameters SwitchToMCSettings: Configuration for switching to Monte Carlo methods.

bool MonteCarlo: Toggle to turn on/off Monte Carlo estimation. If turned on, the algorithm will switch to Monte Carlo estimation once specific termination criteria are satisfied (look at SwitchToMCSettings).

class SwitchParameters

Internal configuration for algorithm switching logic.

int switchTime: Threshold in ms to switch to Monte Carlo.

DType gap: Once the difference between lower and upper bounds of the estimation is lower than this value, switch to Monte Carlo.

This class uses the BoundedResult class.

Code Snippet

#include <moda\DataSet.h>
#include <moda\QHV_BQSolver.h>
#include <moda\SolverParameters.h>
#include <moda\Point.h>
#include <moda\Result.h>
#include <iostream>
int main()
{
   moda::DataSet* dataSet = moda::DataSet::LoadFromFilename("sample_file");
   dataSet->normalize();
   moda::QHV_BQSolver solver;
   moda::QHV_BQParameters* parameters = new moda::QHV_BQParameters(moda::SolverParameters::ReferencePointCalculationStyle::zeroone, moda::SolverParameters::ReferencePointCalculationStyle::zeroone);
   parameters->MaxEstimationTime = 320;
   auto result = solver.Solve(dataSet, *parameters);
   std::cout << "Lower bound: " << result->LowerBound << std::endl;
   std::cout << "Upper bound: " << result->UpperBound << std::endl;
   return 0;
}
//Result:
//    Lower bound: 0.825077
//    Upper bound: 0.897067