Lexicographic and Multi-Objective Optimization in CP

Many CP models have more than one criterion we'd like to optimize. A scheduling model might want both low makespan and low total tardiness; a routing model might want low cost and low travel time. With more than one objective, "optimal" is ambiguous unless we specify how to compare candidate solutions.

The fundamental notion is Pareto dominance. For minimization objectives $f_1, f_2, \ldots, f_k$, solution $s$ dominates solution $s'$ — written $s \prec s'$ — when

$$f_i(s) \le f_i(s') \quad \text{for every } i, \qquad \text{and} \qquad f_j(s) < f_j(s') \quad \text{for at least one } j.$$

A solution that is not dominated by any other feasible solution is called Pareto-optimal (or non-dominated). The set of all Pareto-optimal solutions is the Pareto front.

For example, consider four schedules evaluated on (makespan, total tardiness):

$$A: (10, 12), \quad B: (12, 8), \quad C: (11, 11), \quad D: (14, 14).$$

Solution $A$ dominates $D$ because $10 < 14$ and $12 < 14$. Comparing the remaining pairs, each beats the other on one objective, so none of $A$, $B$, $C$ dominates another. The Pareto front is $\{A, B, C\}$.