0

使用 cplex，我想多次解决 SAT 问题，并通过更改变量的方向 (IloCplex.BranchDirection.Up | IloCplex.BranchDirection.Down) 和优先级来获得不同的解决方案。但是，我总是得到相同的解决方案（存在数千个）。

我或多或少做了以下事情：

IloCplex solver = new IloCplex();
solver.addEq(...);
solver.addGe(...);
solver.addLe(...);

while (true) {
  Collections.shuffle(vars);

  for (IloIntVar var : vars) {
    solver.setDirection(variables.get(object), random.nextBoolean() ? IloCplex.BranchDirection.Up : IloCplex.BranchDirection.Down);
    solver.setPriority(variables.get(object), vars.indexOf(var));
  }

  solver.solve();

  for (IloIntVar var : vars) {
      value = solver.getValue(var);
  }
}

我想在每次迭代中为每个变量获得不同的（如果可行的话）值。有人知道我的错在哪里吗？我尝试了所有solver.clear* 方法来重置它，但这并没有帮助。

4

2 回答 2

1

分支优先级改变了哪些节点在分支切割树上得到扩展。虽然您可能会通过更改它们获得不同的解决方案，但不能保证。事实上，很可能在根节点上使用启发式方法找到的第一个解决方案根本没有发生分支。在像你这样的纯 0-1 问题的情况下，你可以执行以下操作

  1. 求解第一个解 (x * )
  2. 设 y = x 的总和* [i]
  3. 添加约束总和 (2 x * [i] - 1) x[i] <= y
于 2013-01-17T19:39:00.603 回答
0

CPLEX 还具有用于在 MIP 优化期间累积多个解决方案的解决方案池功能。它具有控制细节的参数，因此您可以指示它仅接受最优百分比内的解决方案。由于解决方案池的底层一棵树算法只需要一个或两个分支定界通道来累积请求的解决方案，因此这可能比重复优化和添加约束以排除先前找到的解决方案运行得更快。有关更多信息，请参阅解决方案池和填充过程的 CPLEX 文档。

于 2013-05-17T19:58:28.823 回答