Preference-Based Combinatorial Optimization

基于偏好的组合优化

• 批准号: RGPIN-2021-04109
• 负责人: Mouhoub, Malek
• 金额: $ 2.11万
• 依托单位: University of Regina
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749878
• 关键词: 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.

基于偏好的组合优化是指在现实世界的应用中，我们寻找一个或多个满足一组约束条件的解决方案，优化某些目标，并尽可能满足一组偏好。偏好包括决策者为了在相互冲突的目标之间取得平衡而得出的偏好，这会导致帕累托最优集的规模可控。约束和偏好往往伴随着不确定性，这是由于缺乏知识、信息缺失或不正确，或者外部事件造成的变化。此外，问题建模阶段是一项繁琐的任务，需要强大的专业知识和约束编程和人工智能（AI）的重要背景。 为了解决上述挑战，我们提出了一种基于约束满足问题（CSP）范式的方法，以及偏好表示的图形模型。更确切地说，硬约束（对应于可以满足或违反的关系）将通过CSP网络表示。这种两级的可满足性概念可以推广到多个级别，称为软约束，以捕获定量偏好和目标。图形模型，包括条件偏好网络（CP网）和词典偏好树（LP树）将被用来表示定性和条件偏好。UCP网，广义加性独立网络（GAI-nets），加权CP网（WCP-nets）将被选择作为替代表达效用和成本。为了表达变量之间的相对重要性，我们将依赖于权衡增强的条件偏好网络（TCP-net）。处理不确定性将通过概率和可能性理论来表达。这两种理论是互补的，并且不对不确定性的相同方面进行建模。为了克服建模部分的挑战，我们将考虑两种基于以人为中心的AI的学习机制。在第一个中，我们将采用使用成员查询的主动学习，其中向用户提供示例以分类为积极或消极。在第二种机制中，学习是在被动模式下从历史数据中完成的。后者可能与调度等应用相关，其中过去可用的调度被用作学习的积极示例。在一个人在回路的过程中，将从决策者那里收集反馈数据，以便处理噪声信息并对学习模型进行必要的调整。为了解决上述模型表示的给定优化问题，我们将使用精确方法和元分析法。前者将包括回溯搜索的变体，其中使用约束传播和变量排序算法来提高其实践效率。元分析能够通过牺牲解决方案质量来实现可扩展性和时间效率，从而解决难以解决的应用程序。