getExactFront: Enumerate all Pareto-optimal solutions.

In jakobbossek/rmoco: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem

Enumerate all Pareto-optimal solutions.

Description

Function which expects a problem instance of a combinatorial optimization problem (e.g., MST), a multi-objective function and a solution enumerator, i.e., a function which enumerates all possible solutions (e.g., all Pruefer codes in case of a MST problem) and determines both the Pareto front and Pareto set by exhaustive enumeration.

Usage

getExactFront(instance, obj.fun, enumerator.fun, n.objectives, simplify = TRUE)

Arguments

instance	[any] Problem instance.
obj.fun	[function(solution, instance)] Objective function which expects a numeric vector solution encoding a solution candidate and a problem instance instance. The function should return a numeric vector of length n.objectives.
enumerator.fun	[function(n)] Function to exhaustively generate all possible candidate solutions. Expects a single integer value n, i.e., the instance size, e.g., the number of nodes for a graph problem.
n.objectives	[integer(1)] Number of objectives of problem.
simplify	[logical(1)] Should pareto set be simplified to matrix? This will only be done if all elements are of the same length. Otherwise the parameter will be ignored. Default is TRUE.

Value

[list] List with elements pareto.set (matrix of Pareto-optimal solutions) and pareto.front (matrix of corresponding weight vectors).

Note

This method exhaustively enumerates all possible solutions of a given multi-objective combinatorial optimization problem. Thus, it is limited to small input size due to combinatorial explosion.

Examples

# here we enumerate all Pareto-optimal solutions of a bi-objective mcMST problem
# we use the Pruefer-code enumerator. Thus, we need to define an objective
# function, which is able to handle this type of endcoding
objfunMCMST = function(pcode, instance) {
  getWeight(instance, prueferToEdgeList(pcode))
}

# next we generate a random bi-objective graph
g = genRandomMCGP(5L)

# ... and finally compute the exact front of g
res = getExactFront(g, obj.fun = objfunMCMST, enumerator.fun = enumerateMST, n.objectives = 2L)
## Not run: 
plot(res$pareto.front)

## End(Not run)

jakobbossek/rmoco documentation built on March 21, 2023, 9:09 p.m.