用分支和绑定和CPLEX C＆＃x2B;＆＃x2B求解ILP
我想使用分支和绑定算法解决图形标记问题的ILP。我的ILP对图表中的每对节点具有目标函数和约束。因此，我有n^2/2可能的约束，并且约束具有以下形状：
对于两个顶点i，j \ in v（g）中添加约束： | x_i -x_j | ＆gt; = k + 1 -d（i，j）
显然这不是线性。因此，我想实现我的算法，该算法使用二进制分支并绑定：
- 仅带有目标函数的空LP启动
- ，其启动为空的分支树带有start node，
- 然后在分支树中的每个节点，创建两个子节点。
- 在第一个孩子节点中
- 添加约束x_i -x_j＆gt; = k + 1 -d（i，j）
- 和约束x_i＆gt; = x_j
- 第二个孩子节点
- 添加约束 - （x_i -x_j）＆gt; = k + 1 -d（i，j）
- 和约束x_j＆gt; = x_i
- 在第一个孩子节点中
- 重复此步骤并可能绑定，直到我们找到最佳解决方案，
如果我做这个分支并绑定了算法， ，并且要搜索最佳解决方案，我将获得最佳占用率，其中变量应大于哪个变量。 然后，我将获得一个有限限制的LP，并且我将获得最佳整数解决方案。
我现在的问题是，在C ++和CPLEX中这样做的最好方法是什么？ 我应该始终在CPLEX中创建一个新的ilomodel吗？还是我可以在同一iloenv中做到这一切？ 我知道有内置的选项，以指定分支并在CPLEX中绑定，但是我想“手动”进行操作，因此我还可以实现选择“最佳”下一个约束来添加的功能。
非常感谢您！
I want to solve an ILP using a branch and bound algorithm for a graph labelling problem. My ILP has an objective function and constraints for every possible pair of nodes from the graph. So I have n^2 / 2 possible constraints, and the constraints have following shape:
for two vertices i, j \in V(G) add the constraints:
|X_i - X_j| >= k + 1 - d(i,j)
its obvious that this isn't linear. So i want to implement my algorithm that uses binary branch and bound:
- start with empty LP only with the objective function
- start with empty branch tree with start node
- then at every node in the branch tree, create two child nodes.
- in the first child node
- add the constraints X_i - X_j >= k + 1 - d(i,j)
- and constraint X_i >= X_j
- for the second child node
- add the constraint -(X_i - X_j) >= k + 1 - d(i,j)
- and the constraint X_j >= X_i
- in the first child node
- repeat this step and possibly bound, until we find best solution
If I do this branch and bound algorithm, and search for the best solution, I would get the best occupancy of which variable should be greater than which.
Then I would get a LP, with constant constraints and I would get the optimal integer solution.
My question now is, what is the best way of doing that in c++ and cplex?
Should I always create a new IloModel in CPLEX? Or can I do it all in the same IloEnv?
I know that there are built in options, to specify the branch and bound in CPLEX, but I would like to do it "manually", so I can also implement functions that selects the "best" next constraint to add.
Thank you very much in advance!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
在CPLEX中，您还具有约束编程，例如，使用OPL，您可以直接编写
频率分配模型的一部分
，可以在C ++中完成。
Within CPLEX you also have Constraint Programmming and with OPL for example you can directly write
which is part of a frequency allocation model
The same can be done in C++