英文:
Constraint Programming, how to add x[i] <= (max(x[:i]) + 1)
问题
我正在使用or-tools CP工具构建一个模型。我想要找到的值放在一个向量X中，我想要添加一个约束条件，即对于X的每个位置，下一个位置的值不能大于在X[:i] + 1中找到的最大值。
它可能是这样的：
X[i] <= (max(X[:i]) + 1)
当然，我不能使用max()来将这个约束添加为线性约束，为每个X的值创建一个额外的上界特征似乎过于冗余，而且我还需要将每个值最小化以使其成为“最大值”，否则这些只是可能非常大的上界，不能剪枝我的搜索空间（而且我已经有一个目标函数）。
我已经有一个目标函数。
我知道一个添加例如min-max (min(max(x[i])) 问题的技巧是创建另一个变量，它是每个x的上界，并将其最小化。可能是这样的：
model = cp_model.CpModel()
lb = 0
ub = 0
model.NewIntVar(z, lb, ub)
for i in domain(X):
model.NewIntVar(X[i], lb, up)
model.Add(X[i] <= z)
model.Minimize(z)
如果您不想编写代码，您可以使用or-tools中的方法：
model.AddMaxEquality(z, X)
现在我想添加一个约束条件，对X的每个值设置一个上限，该上限是在前一个x之前找到的最大值。可能是这样的：
X[i] <= max(X[:i]) + 1
我正在考虑复制之前的想法，但这将需要为每个x创建一个“z”... 不确定这是否是最佳方法以及它将减少我的解空间多少。与此同时，我找不到or-tools中执行此操作的方法。
有什么建议吗？
PS：我已经将min(z)作为目标函数，就像在示例中所示。
示例：
例如，模型的结果可能是：
[0, 1, 2, 0, 2, 3]
但你不应该有：
[0, 1, 1, 2, 4]
因为在X[:3]之前的最大值是2，所以X[4]的上界应该是2 + 1。
谢谢！
英文:
I'm building a model using or-tools CP tools. The values I want to find are placed in a vector X, and I want to add a constraint that says up to each position of X, the next position cannot have as a value something bigger than the maximum found until X[:i] + 1
It would be something like this:
X[i] <= (max(X[:i]) + 1)
Of course, I cannot add this as a linear constraint with a max(), and creating one extra feature for each value of X upper bound seems excessive and also I would need to minimize each one to make it the "max", otherwise those are just upper bounds that could be huge and not prune my search space (and I already have an objective function).
I already have an objective function.
I know that one trick to add for instance a min-max (min(max(x[i])) problem is to create another variable that is an upper bound of each x and minimize that one. It would be sth like this:
model = cp_model.CpModel()
lb =0; ub=0
model.NewIntVar(z, lb, ub)
for i in domain(X):
model.NewIntVar(X[i], lb, up)
model.Add(X[i] <= z)
model.Minimize(z)
In case you don't want to program this you can use the method in or-tools:
model.AddMaxEquality(z, X)
Now I want to add a constraint that at each value of X sets an upper limit which is the maximum value found until the previous x. It would be something like this:
X[i] <= max(X[:i]) + 1
I was thinking of replicating the previous idea but that would require creating a "z" for each x... not sure if that is the best approach and how much it will reduce my space of solutions. At the same time couldn't find a method in or-tools to do this.
Any suggestions, please?
PS: I already have as an objective function min(z) like it is in the example presented.
Example:
For instance, you can have as a result of the model:
[0, 1, 2, 0, 2, 3]
But you shouldn't have:
[0, 1, 1, 2, 4]
Since the max until X[:3] is 2, so the ub of X[4] should be 2 + 1.
Thanks!
答案1
得分: 1
我没有具体的提示，除非：
- 你需要进行实验。一个建模技巧可能对一种模型有效，但对另一种模型无效。
- 确保在索引 i - 1 处重复使用最大变量。使用
X作为变量数组，M作为最大值数组，即M[i] = max(X[0], .., X[i - 1])
M[i] = max(M[i - 1], X[i - 1])
X[i] <= M[i] + 1
英文:
I have no specific hints except:
- you need to experiment. One modeling trick may work on one kind of model and not on the other
- make sure to use reuse the max variable at index i - 1. With
Xthe array of variables andMthe array of max, i.e.M[i] = max(X[0], .., X[i - 1])
M[i] = max(M[i - 1], X[i - 1])
X[i] <= M[i] + 1
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论