Class 布尔可满足性调度 [多项式时间缩减]

Question

我有一些 theoretical/practical 问题，我现在不知道如何管理，这里是：

我使用遗传算法在 C 中创建了一个 SAT solver able to find a model when one is existing and to prove the contradiction when it's not the case on CNF 问题。

一道 SAT 题基本上是这样的：我的目标是使用此求解器找到许多不同 NP-completes 问题的解决方案。基本上，我将不同的问题转化为 SAT，用我的求解器解决 SAT，然后将解决方案转换为原始问题可接受的解决方案。

我已经成功解决了 N*N 数独和 N 皇后问题，但这是我的新目标：将 Class 调度问题减少到 SAT，但我不知道如何形式化class-scheduling problem 为了在SAT之后轻松改造它。

显然，目标是在几个月内生成一张这样的时间表图片：

我发现这个 source-code 能够解决 class-scheduling 但不幸的是没有任何减少 SAT :/

我还找到了一些关于总体规划的文章（例如http://www.cs.rochester.edu/users/faculty/kautz/papers/kautz-satplan06.pdf）。

但是本文中使用的 planning domain definition language 对我来说似乎过于笼统，无法代表 Class 调度问题。 :/

是否有人知道如何有效地形式化 Class 调度以将其简化为 SAT，然后将 SAT 解决方案（如果存在 ^^）转换为 Class-时间表？

我基本上对任何建议持开放态度，我现在不知道如何表示，如何减少问题，如何将 SAT 解决方案转化为时间表...

跟进问题：

Answer 1

我将尝试先将问题形式化，然后尝试将其简化为 SAT。

定义 class 调度问题为：

Input = { S1,S2,....,Sn | Si = {(x_i1, y_i1), (x_i2, y_i2) , ... , (x_ik, y_ik) | 0 <= x_ij < y_ij <= M } }

非正式地：输入是一组 classes，每个 class 是一组（开）间隔，形式为 (x,y)
（M 是描述 "end of the week" 的常数）

输出：当且仅当存在某个集合时为真：

R = { (x_1j1, y_1j1) , ..., (x_njn, y_njn) | for each a,b: (x_aja,y_aja) INTERSECTION (x_bjb,y_bjb) = {} }

非正式地：当且仅当存在某种区间分配使得每对区间之间的交集为空时才为真。

降低 SAT：

为每个区间定义一个布尔变量，V_ij
在此基础上，定义公式：

F1 = (V_11 OR V_12 OR ... OR V_1(k_1)) AND .... AND (V_n1 OR V_n2 OR ... OR V_n(k_n))

非正式地，当且仅当每个 class 的间隔中至少有一个是 "satisfied"

时，F1 才满足

定义 Smaller(x,y) = true 当且仅当 if x <= y¹
我们将使用它来确保间隔不会重叠。
请注意，如果我们要确保 (x1,y1) 和 (x2,y2) 不重叠，我们需要：

x1 <= y1 <= x2 <= y2 OR  x2 <= y2 <= x1 <= y1

由于输入保证 x1<=y1, x2<=y2，它减少为：

y1<= x2 OR y2 <= x1

并使用我们的 Smaller 和布尔子句：

Smaller(y1,x2) OR Smaller(y2,x1)

现在，让我们定义新的子句来处理它：

对于每对 classes a,b 和其中的区间 c,d (c in a, d in b)

G_{c,d} = (Not(V_ac) OR Not(V_bd) OR Smaller(y_ac,x_bd) OR Smaller(y_bd,x_ac))

非正式地，如果未使用间隔 b 或 d 之一 - 子句得到满足，我们就完成了。否则，两者都使用，我们必须确保两个区间之间没有重叠。
这保证如果 c,d 都是 "chosen" - 它们不会重叠，并且对于每对间隔都是如此。

现在，形成我们的最终公式：

F = F1 AND {G_{c,d} | for each c,d}

这个公式确保我们：

对于每个class，至少选择一个区间
对于每两个区间 c,d - 如果同时选择了 c 和 d，则它们不会重叠。

小提示：这个公式允许从每个 class 中选择超过 1 个区间，但是如果有一些 t>1 区间的解决方案，您可以轻松地删除其中的 t-1 个而不改变正确性解决方案。

最后，选择的区间就是我们定义的布尔变量V_ij。

示例：

Alebgra = {(1,3),(3,5),(4,6)} Calculus = {(1,4),(2,5)}

定义 F:

F1 = (V1,1 OR V1,2 OR V1,3) AND (V2,1 OR V2,2)

定义 G：

G{A1,C1} = Not(V1,1) OR Not(V2,1) OR  4 <= 1 OR 3 <= 1 //clause for A(1,3) C(1,4)
         = Not(V1,1) OR Not(V2,1) OR false = 
         = Not(V1,1) OR Not(V2,1)
G{A1,C2} = Not(V1,1) OR Not(V2,2) OR  3 <= 2 OR 5 <= 1 // clause for A(1,3) C(2,5)
         = Not(V1,1) OR Not(V2,2) OR false = 
         = Not(V1,1) OR Not(V2,2)
G{A2,C1} = Not(V1,2) OR Not(V2,1) OR  5 <= 1 OR 4 <= 3 //clause for A(3,5) C(1,4)
         = Not(V1,2) OR Not(V2,1) OR false = 
         = Not(V1,2) OR Not(V2,1)
G{A2,C2} = Not(V1,2) OR Not(V2,2) OR  5 <= 2 OR 5 <= 3 // clause for A(3,5) C(2,5)
         = Not(V1,2) OR Not(V2,2) OR false = 
         = Not(V1,2) OR Not(V2,2)
G{A3,C1} = Not(V1,3) OR Not(V2,1) OR  4 <= 4 OR 6 <= 1 //clause for A(4,6) C(1,4)
         = Not(V1,3) OR Not(V2,1) OR true= 
         = true
G{A3,C2} = Not(V1,3) OR Not(V2,2) OR  6 <= 2 OR 5 <= 4 // clause for A(4,6) C(2,5)
         = Not(V1,3) OR Not(V2,2) OR false = 
         = Not(V1,3) OR Not(V2,2)

现在我们可以展示我们的最终公式：

    F = (V1,1 OR V1,2 OR V1,3) AND (V2,1 OR V2,2) 
        AND  Not(V1,1) OR Not(V2,1) AND Not(V1,1) OR Not(V2,2)
        AND  Not(V1,2) OR Not(V2,1) AND Not(V1,2) OR Not(V2,2)
        AND  true AND Not(V1,3) OR Not(V2,2)

以上仅满足：

V1,1 = false
V1,2 = false
V1,3 = true
V2,1 = true
V2,2 = false

代表时间表：Algebra=(4,6);微积分=(1,4)，随心所欲。

(1)可以很容易地计算为公式的常数，这样的常数有多项式。

Class 布尔可满足性调度 [多项式时间缩减]

Class Scheduling to Boolean satisfiability [Polynomial-time reduction]

c

algorithm

scheduling

reduction

sat