Preference-Based Combinatorial Optimization

基于偏好的组合优化

• 批准号: RGPIN-2021-04109
• 负责人: Mouhoub, Malek
• 金额: $ 2.11万
• 依托单位: University of Regina
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=742878
• 关键词: 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-net）和词典偏好树（LP-trees）将用于表示定性和条件偏好。ucp网络、广义可加性独立网络（GAI-nets）和加权cp网络（WCP-nets）将被选择作为表示效用和成本的替代方案。为了表达变量之间的相对重要性，我们将依赖于权衡增强的条件偏好网络（TCP-net）。对不确定性的处理将通过概率论和可能性理论来表达。这两种理论是互补的，并不模拟不确定性的同一方面。为了克服建模部分的挑战，我们将考虑基于以人为中心的AI的两种学习机制。在第一种方法中，我们将使用隶属度查询采用主动学习，其中向用户提供示例来分类为积极或消极。在第二种机制中，学习是被动地从历史数据中完成的。后者可能与调度等应用程序相关，在这些应用程序中，过去可用的调度被用作学习的积极示例。在人在循环过程中，将从决策者那里收集反馈数据，以处理有噪声的信息，并对学习的模型进行必要的调整。为了解决用上述模型表示的给定优化问题，我们将同时使用精确方法和元启发式方法。前者将包括回溯搜索的变体，其中使用约束传播和变量排序启发式来提高其实践效率。元启发式能够通过牺牲解决方案的质量来实现可伸缩性和时间效率，从而解决难以解决的应用程序。