Since many real world applications involve discrete decisions or events, multi-objective combinatorial optimization (MOCO) problems are often considered. For ease of presentation, we focus in particular on bi-objective combinatorial optimization (BOCO) problems. The general BOCO problem may be formulated as follows:
min{[f(x), g(x)] : x ∈ X}
where f and g are the two objectives to be minimized, and X is the feasible region deﬁned 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^{2} 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^{2} be the set of all efficient points related to a BOCO instance.We say that a point (φ, γ) ∈ R ^{2} 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 ﬁnite set of admissible points E* ⊂ R^{2} 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, ﬁnd 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. | ## Multiobjective Combinatorial Optimization |