The Disjunctive Temporal Problem (DTP), which involves Boolean combination of difference constraints of the form x - y ≤ c, is an expressive framework for constraints modeling and processing. When a DTP is unfeasible we may want to select a feasible subset of its DTP constraints (i.e., disjunctions of difference constraints), possibly subject to some degree of satisfaction: The Max-DTP extends DTP by associating a preference, in the form of weight, to each DTP constraint for its satisfaction, and the goal is to find an assignment to its variables that maximizes the sum of weights of satisfied DTP constraints. In this paper we first present an approach based on Boolean optimization solvers to solve Max-DTPs. Then, we implement our ideas in TSAT++, an efficient DTP solver, and evaluate its performance on randomly generated Max-DTPs, using both different Boolean optimization solvers and two optimization techniques.
展开▼
机译：讨论的时间问题（DTP）涉及Boolean X - Y≤C的差异约束的差异约束，是用于约束建模和处理的表现力框架。当DTP不可行时，我们可能希望选择其DTP约束的可行子集（即，差异约束的剖钉），可能受到某种程度的满意度：MAX-DTP通过以重量的形式关联偏好而扩展DTP对每个DTP约束的满意度，目标是找到对其变量的分配，最大化满足DTP约束的权重和。在本文中，我们首先提出了一种基于布尔优化求解器的方法来解决MAX-DTPS。然后，我们在TSAT ++中实现了我们的想法，高效的DTP求解器，并使用不同的布尔优化求解器和两种优化技术评估随机生成的MAX-DTPS的性能。
展开▼
