mcMST (version 1.0.1)

getExactFront: 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)

Value

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

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.

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)
if (FALSE) {
plot(res$pareto.front)
}