Multi-Objective Constraint Optimization with Lexicographic Preference Models
Refereed Conference Meeting Proceeding
In this paper, we consider algorithms for solving Multi-Objective Constraint Optimization Problems (MOCOP) with tradeoffs, which consist of elicited or observed preferences over decisions (feasible solutions). In MOCOP, each decision is evaluated on a number of criteria, and can thus be associated with a vector of objective values, each component corresponding to a different criterion. The comparison between decisions is based on a comparison between objective vectors. The optimal decisions are those that are not dominated by any other decision due to some order relation, which respects the restrictions given by the tradeoffs. We consider a branch-and-bound algorithm to find optimal solutions, which uses a minibuckets algorithm for generating the upper bound at each node. A key issue is how one orders the objective vectors. The two most common methods are using a weighted sum, or a Pareto ordering. Here, we propose to use preference inference, which involves inferring additional user preferences from the given tradeoffs, based on the assumption that the user preference relation is a lexicographic order. We use this concept to perform dominance checks. Our implementation indicates that when using a lexicographic modelbased approach, the number of solutions is drastically reduced in comparison with other approaches, while the running time increases.
Workshop on Algorithmic issues for Inference in Graphical Models (AIGM) 2015
Digital Object Identifer (DOI):
National University of Ireland, Cork (UCC)
Open access repository: