Preference-Based Combinatorial Optimization

点击翻译按钮获取中文摘要

Preference-Based Combinatorial Optimization refers to those real-world applications where we look for one or more solutions meeting a set of constraints, optimizing some objectives, and satisfying a set of preferences as much as possible. Preferences include those elicited from the decision maker to balance between conflicting objectives, which results in a Pareto optimal set of a manageable size. Constraints and preferences often come with uncertainty due to lack of knowledge, missing or incorrect information, or variability caused by external events. Moreover, the problem modeling phase is a tedious task requiring strong expertise and a significant background in constraint programming and Artificial Intelligence (AI). To address the above challenges, we propose a methodology based on the Constraint Satisfaction Problem (CSP) paradigm, and graphical models for preference representation. More precisely, hard constraints (corresponding to relations that can be satisfied or violated) will be represented through a CSP network. This two-level notion of satisfiability can be generalized to multiple levels, called soft constraints, to capture quantitative preferences and objectives. Graphical models, including the Conditional Preference network (CP-net) and the Lexicographic Preference trees (LP-trees) will be used to represent qualitative and conditional preferences. UCP-nets, Generalized Additive Independence networks (GAI-nets), and Weighted CP-nets (WCP-nets) will be chosen as alternatives for expressing utilities and costs. To express the relative importance between variables, we will rely on the Tradeoffs-enhanced Conditional Preference Network (TCP-net). Dealing with uncertainty will be expressed through both the probability and the possibility theories. These two theories are complementary and do not model the same facet of uncertainty.  To overcome the challenge with the modeling part, we will consider two learning mechanisms based on human-centric AI. In the first one, we will adopt active learning using membership queries, where examples are provided to the user to classify as positive or negative. In the second mechanism, learning is done in a passive mode from historical data.  The latter can be relevant for applications such as scheduling, where past available schedules are used as positive examples to learn from. Following a human-in-the-loop process, feedback data will be collected from a decision-maker in order to address noisy information and make the necessary adjustments to the learned model.  To solve a given optimization problem represented with the above models, we will use both exact methods and metaheuristics. The former will include variants of the backtrack search where constraint propagation and variable ordering heuristics are used to improve its practice efficiency. Metaheuristics are capable of tackling hard-to-solve applications by compromising solution quality for scalability and time efficiency.