时间戳

首页 > 解决方案 > 在 CPLEX 中生成所有子集（subtour 消除）

optimization - 在 CPLEX 中生成所有子集（subtour 消除）

问题描述

目前我正在尝试在 CPLEX 中对 Dantzig Fulkerson Johnson Subtour 消除约束进行建模。

我想在 ILOG 脚本中生成所有可能的客户子集 {"1", "2", "3", "4"}。

为此，首先我创建了一个元组结构，其中包含一组字符串，其中可以存储子游览中涉及的所有客户：

tuple subtour {
    {string} customers;
 }

现在，我可以创建一组 subtour 来存储所有 subtour：

{subtour} subtours;

我创建了一组空字符串来帮助执行块：

 {string} emptySet;

现在我创建我的执行块：（在这第一步中，我只是尝试用仅包含一个客户的子旅游填充子旅游作为第一次测试，例如在第一次迭代中 subtours = {<{"1"}>, < {"2"}>,...}

execute FillSubtours {
   for(var i in customers) {
     emptySet.add(i);
     subtours.add(emptySet);
     writeln(subtours);
     emptySet.clear();
   }     
 }

所以在这个过程之后，目标是有这样的子旅游：

 subtours = {<{"1"}>, <{"2"}>, <{"3"}>, <{"4"}>}

包含一个元素的所有可能的子旅游。

可悲的是，它看起来如下：

subtours = {<{"4"}>}

有谁知道哪里出了问题以及我该如何解决？

标签： optimizationsettuplescplexilog

解决方案

在如何使用 OPL 中，您可以查看powerset

然后你可以将你的模型重写为

{string} customers= {"1", "2", "3", "4"} ;

tuple subtour {
    {string} customers;
 }
 
 
 
 range r=1.. ftoi(pow(2,card(customers)));
 {string} s2 [k in r] = {i | i in customers: 
 ((k div (ftoi(pow(2,(ord(customers,i))))) mod 2) == 1)};
 
 
 {subtour} subtours={<s2[k]> | k in r};
 
 execute
 {
   writeln(subtours);
 }

这使

{<{"1"}> <{"2"}> <{"1" "2"}> <{"3"}> <{"1" "3"}> <{"2" "3"}>
     <{"1" "2" "3"}> <{"4"}> <{"1" "4"}> <{"2" "4"}>
     <{"1" "2" "4"}> <{"3" "4"}> <{"1" "3" "4"}> <{"2" "3" "4"}>
     <{"1" "2" "3" "4"}> <{}>}

推荐阅读