Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:
x1 -x2 ≤1
x1 -x4 ≤-4
x2 -x3 ≤2
x2 -x5 ≤7
x2 -x6 ≤5
x3 -x6 ≤10
x4 -x2 ≤2
x5 -x1 ≤-1
x5 -x4 ≤3
x6 -x3 ≤-8
(-5, -3, 0, -1, -6, -8)
Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:
x1 -x2 ≤4
x1 -x5 ≤5
x2 -x4 ≤-6
x3 -x2 ≤1
x4 -x1 ≤3
x4 -x3 ≤5
x4 -x5 ≤10
x5 -x3 ≤-4
x5 -x4 ≤-8
没有解,因为x4 -> x2 -> x3 -> x5 -> x1 -> x4形成了一个负权回路.
Can any shortest-path weight from the new vertex v0 in a constraint graph be positive? Explain.
不可能为正数,因为最大已经是0了.不可能大于0.
Express the single-pair shortest-path problem as a linear program.
将G视为约束图，得到差分约束Ax<=b。设起点为i，终点为j，求解目标为 (xj - xi) 的最大值。
Show how to modify the Bellman-Ford algorithm slightly so that when it is used to solve a system of difference constraints with m inequalities on n unknowns, the running time is O(nm).
V0这个顶点和他的n条权值为0的边其实是没有意义的,一开始初始化的时候可以对所有的点v,令d[v] = 0.
Suppose that in addition to a system of difference constraints, we want to handle equality constraints of the form xi = xj + bk. Show how the Bellman-Ford algorithm can be adapted to solve this variety of constraint system.
xi >= xj + bk
xi <= xj + bk
Show how a system of difference constraints can be solved by a Bellman-Ford-like algorithm that runs on a constraint graph without the extra vertex v0.
同练习24.4-5
Let Ax ≤ b be a system of m difference constraints in n unknowns. Show that the Bellman- Ford algorithm, when run on the corresponding constraint graph, maximizes x1+x2+...+xn subject to Ax≤b and xi ≤0 for all xi.
Bellman-Ford 处理线性规划问题的算法：添加虚拟的顶点v0到约束图，并设置该节点到其他节点的边权重均为0，之后以 v0 为源使用 Bellman-Ford 算法，得出的 v0 到各点的最小距离即为满足条件的解 xi，此结果已经最大化了x1+x2+...xn. 正确性证明：（反证法） 假设存在另一组解 (y1,y2...yn)，其和更大，则至少存在一个 yi>xi。由于xi对应了约束图上 v0 顶点到 vi 顶点的最小距离，我们设该最小路径通过的顶点分别是 v1,v2...vi，我们有： 不等式1: (根据 y 是满足约束条件的一组解) y2-y1 < w(v1,v2), y3-y2 < w(v2,v3) ... yi-yi-1 < w(vi-1,vi) 不等式2: (根据 y1<0 的约束) yi < yi-y1 等式: (根据 v1 到 vi 是求出的最短路径) xi = w(v0,v1)+w(v1,v2)+...+w(v(i-1),vi) 注意该等式右边第一项是0. 结合以上三个式子，我们有： yi < yi-y1 < yi-y_(i-1)+y_(i-1)...-y2+y2-y1 < w(v1,v2)+w(v2,v3)+...+w(v_(i-1),v_i) ＝ xi 与假设矛盾，因此 x 就是和最大的解，证毕。
Show that the Bellman-Ford algorithm, when run on the constraint graph for a system Ax ≤ b of difference constraints, minimizes the quantity (max {xi} - min {xi}) subject to Ax ≤ b. Explain how this fact might come in handy if the algorithm is used to schedule construction jobs.
根据上题，Bellman-Ford 算法在约束图上给出的解为 x1,x2...x3。设其中的最小值为 xi。依旧考虑 v0 到 vi 的这一情况下的最短路径，记路过的顶点为 v1, v2... vi-1。首先由于 w(v0,v1)=0, 则 x1=0。(因为最短路径的子路径仍旧是最短路径)。而由于距 v0 的最短距离不可能为正数，则 x1 即为解 x 中的最大值。此时我们有数据区间 x1-xi=-xi=-[w(v1,v2)+w(v2,v3)+...w(vi-1,vi)]。 考虑存在另一组满足约束的解 y1,y2...yi。那么 y1-yi = -(y2-y1)-(y3-y2)-...-(yi-yi-1) > -w(v1,v2)-w(v2,v3)-...-w(vi-1,vi) = -xi。解 y 的极差一定不小于 y1-yi，而该值大于原解 x。由此得证 x 已经是满足要求的极差最小的解。 考虑每个 x 是一个任务完成的时刻，在一定约束下，我们总是希望完成任务的总时长最小，此即为最小化极差的应用。
Suppose that every row in the matrix A of a linear program Ax ≤ b corresponds to a difference constraint, a single-variable constraint of the form xi ≤ bk, or a single-variable constraint of the form -xi ≤ bk. Show how to adapt the Bellman-Ford algorithm to solve this variety of constraint system.
新造一个节点u,令约束条件变成xi - xu ≤ bk.
并且初始化d(u) = 0.
Give an efficient algorithm to solve a system Ax ≤ b of difference constraints when all of the elements of b are real-valued and all of the unknowns xi must be integers.
把所有的b向下取整。因为 xi - xj ≤ b 同时 xi - xj 是整数，可得 xi - xj 一定小于等于b向下取整。
Give an efficient algorithm to solve a system Ax ≤ b of difference constraints when all of the elements of b are real-valued and a specified subset of some, but not necessarily all, of the unknowns xi must be integers.
仍然采用最短路径算法，在松弛过程中，若有必要（x.v为整数），取 v.d = {(u.d + w(u, v)) 向下取整}。 证明： 假设这个算法得出的解（最短路径）不满足约束条件，更具体的，xi - xj > bm。 因为我们在松弛过程中，由于向下取整，导致实际取的 v.d ≤ u.d + w(u, v)，而如果取 v.d = u.d + w(u, v) 结果是满足约束条件的，可知一定是j点得最短路径取小了。 另一方面，原来的约束 xi - xj ≤ bm 在约束图中是点j到点i的路径。如果i点在j点之前已经取得最短路径，对j点的循环过程会导致i点最短路径更短，可知i点一定在j点之后取得最短路径。根据松弛过程可知，算出的i点的最短路径一定满足约束，即 xi - xj ≤ bm。 与假设矛盾。 因此，按照该方法算出的结果一定是一个可行解。
Follow @louis1992 on github to help finish this task.
本节部分答案参考自这里