Decision support systems developed for real-world applications often rely on solving complex combinatorial problems using carefully crafted constraint models. However, users of such systems may input data that leads to a problem without any solution, rendering it unsatisfiable. The responsibility of understanding and correctly modifying the data generally falls on the user. Previous research on unsatisfiability mainly focused on reporting subsets of problematic constraints, which requires a good understanding of the underlying model. We introduce the concept of Cost-Minimal Parameter Correction Subset (CMPCS) as a subset of data parameters and their correction to make an instance satisfiable at a minimal cost. We propose a problem-independent approach, called CMPCS-Finder, which aims at reporting a CMPCS given an unsatisfiable instance. We empirically evaluate this approach on existing combinatorial benchmark problems and demonstrate that, in most cases, it successfully identifies the changes in the data that initially caused the instances to be unsatisfiable.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Cost-Minimal Parameter Correction Subsets for Unsatisfiable Constraint Problems

  • Antoine Laviolette,
  • Claude-Guy Quimper,
  • Raphaël Boudreault

摘要

Decision support systems developed for real-world applications often rely on solving complex combinatorial problems using carefully crafted constraint models. However, users of such systems may input data that leads to a problem without any solution, rendering it unsatisfiable. The responsibility of understanding and correctly modifying the data generally falls on the user. Previous research on unsatisfiability mainly focused on reporting subsets of problematic constraints, which requires a good understanding of the underlying model. We introduce the concept of Cost-Minimal Parameter Correction Subset (CMPCS) as a subset of data parameters and their correction to make an instance satisfiable at a minimal cost. We propose a problem-independent approach, called CMPCS-Finder, which aims at reporting a CMPCS given an unsatisfiable instance. We empirically evaluate this approach on existing combinatorial benchmark problems and demonstrate that, in most cases, it successfully identifies the changes in the data that initially caused the instances to be unsatisfiable.