Anytime Lexicographic Enumeration of the Pareto Front in Multi‐Objective Combinatorial Optimisation

Abstract

Multi‐objective combinatorial optimisation problems are widespread in real‐world scenarios, including resource allocation, scheduling and logistics, where multiple competing objectives need to be optimised simultaneously. In industrial contexts, lexicographic optimisation is often used to solve these problems, requiring the decision‐maker (DM) to only rank the objectives according to their importance. However, a major limitation of this approach is that the resulting solution may not completely align with the DM's preferences. Alternatively, other approaches enumerate the entire Pareto front, allowing the DM to select their preferred solution. However, computing the full Pareto front can be time‐consuming and may overwhelm the DM. Moreover, these methods are unable to account for preference information such as lexicographic order, which would enable the specification of a ranking of the objectives. In this paper, we investigate how to lexicographically enumerate the Pareto front in an anytime fashion; with the goal of quickly providing a limited set of the lexicographically best non‐dominated solutions. As such, we propose two new exact anytime algorithms designed for this task: Fix‐Improve (FI) and Fix‐Worsen‐Improve (FWI). As our experimental evaluation shows, our proposed methods are able to enumerate these solutions more efficiently than existing methods.