Concepts and Challenges

where f and g are the two objectives to be minimized, and X is the feasible region defined by the constraints, including integrality requirements. Any vector x ∈ X is a feasible solution. If a BOCO problem is well formed, there should not be a single solution that simultaneously minimizes both objectives to their fullest. A feasible solution x is Pareto optimal if there exists no feasible solution x’ such that f(x’) ≤ f(x) and g(x’) ≤ g(x), and at least one inequality is strict. A point (φ, γ) ∈ R² is an efficient point if there exists a Pareto optimal solution x such that f(x) = φ and g(x) = γ. Let the efficient set E ⊂ R² be the set of all efficient points related to a BOCO instance.

An important aspect related to MOCO problems is that the cardinality of E often grows exponentially with the problem size. This result is demonstrated for several problems, such as the assignment problem or the traveling salesman problem. For this reason, many different heuristics and meta-heuristics were developed in the last decades. Such methods give a good trade-off between the quality of an approximation of the efficient set and the computational time, even if they cannot give any theoretical guarantee on the distance between the computed points in the objective space and the exact efficient points.

We say that a point (φ, γ) ∈ R² is admissible if φ = f(x) and γ = g(x) for some feasible solution x ∈ X. Let (φ*, γ*) be an efficient point. An admissible point (φ, γ) is an ε-approximation of (φ*, γ*) if (i) φ ≤ (1 + ε)φ* and (ii) γ ≤ (1 + ε)γ*. A finite set of admissible points E* ⊂ R² is an ε-approximation of E if, for every (φ*, γ*) ∈ E there is a (φ, γ) ∈ E* which is an ε-approximation of (φ*, γ*). We may expect that an ε-approximation E* of E is such that |E*| < |E|. A Pareto ε-approximation E* of E is an ε-approximation such that E* ⊆ E. In other words, a Pareto ε-approximation of E is any subset of efficient points that ε-approximates the whole set E. Trivially, E is a Pareto ε-approximation of itself for any ε ≥ 0. When the cardinality of E is so high that we cannot compute it explicitly, two interesting challenges may be formulated:

• Given a required maximum error e, find a Pareto ε-approximation of minimum cardinality

• Given a maximum cardinality M, find a Pareto ε-approximation of cardinality M such that ε is minimum.

Both challenges are, in fact, too hard to tackle directly in a general context. However, they may inspire manageable interesting questions on problems with special structure, like routing or scheduling problems.