algorithm - 当某些 x 必须是整数时，给定一种求解差分约束系统的有效算法

Question

这是 CLRS 24.4-12 的练习，（不是作业，我只是尝试解决 CLRS 中的所有练习）

当 b 的所有元素都是实值并且某些但不一定是所有未知数 xi 的指定子集必须是整数时，给出一个有效的算法来求解具有差异约束的系统 Ax ≤ b。

如果所有 xi 都是整数，我们可以让 b = floor(b) 并使用 Bellman-Ford 算法在约束图中找到解决问题的最短路径，但是 xi 有些是整数而有些不是呢？它类似于整数规划问题，但整数规划是NP-hard，这个问题的约束较少，有没有更高效的算法？

Answer 1

First find the element with minimum absolute value in vector b , multiply it by C to make all of the values in vector of b integer (e.g. if the minimum absolute value is 3.102, we can multiply vector b by 1000), then solve it by bellman-ford algorithm , and finally divide it by C !

Answer 2

你在线性优化中有类似的东西——唯一的区别是你没有最低或最高要求。也许你可以调整一些方法。从实值解开始，有 Gomory 算法添加额外的约束来强制整数 xi 变为整数，还有分支定界算法，试图尽快排除搜索空间的大部分。

Answer 3

出色地。伙计，这是算法导论的练习。我自己的方法是采用Bellman-Ford算法，基本就是根据不等式构造一个有向加权图，然后在放松边的时候，只允许整数作为节点的键值。我想它会起作用的。