首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >为什么CPLEX将无关变量设置为1?

为什么CPLEX将无关变量设置为1?
EN

Stack Overflow用户
提问于 2020-06-18 11:05:41
回答 1查看 183关注 0票数 0

我一直在研究一个组合优化问题,它可以建模为整数线性规划。我将其作为一个c++项目在VisualStudio2017和CPLEX1271中实现。由于有许多成倍的约束,所以我通过IloCplex::LazyConstraintCallbackI实现了惰性约束。在我看来,下面的步骤是如何产生最优解:每次确定整数解时,LazyConstraintCallbackI将检查它,并在模型中添加一些违反的约束,直到得到最优整数解为止。

然而,我的实现给出的不同输入的客观值并不总是正确的。经过近一年的间歇调试和测试,我终于找出了原因,这是一个与问题相关的问题,但可以(希望地)用下面的小例子来解释:一个包含四个布尔变量x1、x2、x3和x4的整数线性规划。

代码语言:javascript
运行
复制
minimize x1
subject to: 
x1  ≥  x2
x1  ≥  x3
x1  ≥  x4
x2  + x3  ≥ 1
x1, x2, x3 and x4  ∈ {0, 1}​

cplex给出的结果是:

代码语言:javascript
运行
复制
Solution status = Optimal
Objective value = 1
x1 = 1
x2 = 1
x3 = 1
x4 = 1​

毫无疑问,目标值是正确的,.The奇怪的是,cplex设置x4 = 1。尽管X4 the =1或0对该规划中的目标值没有影响。但是,当使用惰性约束回调时,可能会通过添加一些不正确的约束来解决问题,而整数规划则通过迭代添加违反的约束来解决。我想知道:

  1. 为什么cplex将“不相关的”变量x4设置为1,而不是0?
  2. ,我应该如何告诉CPLEX,我想留下像0?

这样的“无关”变量。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-06-19 04:49:30

由于没有什么可以强制x4=0在最优解决方案中使用,所以不能保证CPLEX将设置x4=0?为什么要这么做?为什么0优先于1?该模型有两个最优解,一个x4=0最优解和一个x4=1最优解,两者都有一个目标值1,CPLEX完全可以自由选择其中一个。

正如sascha在他的评论中所说的,强制x4=0在一个最优解中的唯一方法是将这个约束添加到模型中,例如,将目标系数设置为一个小的正值。

但是,奇怪的是,惰性约束回调会从整数可行的解决方案中生成无效的约束。这看起来像一个bug:要么回调对模型做出无效的假设(即在任何最优解决方案中的x4=0 ),要么在回调的逻辑中有一个bug。请注意,在手头的模型中,回调用x4=1切断解决方案实际上是很好的,因为这仍然留下了x4=0和CPLEX的等效最优解,最终会发现这一点。

票数 5
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/62448542

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档