IBM Cplex中对称旅行商的子消除约束

1 回答

• 1

  有人可以用这个代码行的等效数学公式帮助我吗？

  

  哪里：

  xij = 1 if the the salesman traverses the link from city i to city j, 0 otherwise
  S = a subtour, which is a subset of cities (which in turn is an ordered set).
  i, j = two cities that belong to the subtour
  

  该公式取自here并且指的是对称旅行商问题（从 i 到 j 的成本与从 j 到 i 的成本相同） . 因此，变量 xij 仅针对 i < j 定义 .

  我不是一个期望，但会解释如下代码：

  subtours 是一个元组，就像一个C / C struct ：

  tuple Subtour { int size; int subtour[Cities]; }
  {Subtour} subtours = ...;
  

  我知道 subtours 被定义为类型 Subtour ，它包含一个在城市上定义的数组，但是由 size 变量指向的大小（因为并非所有城市都可能是给定子区的一部分） .

  forall (s in subtours) 是不言自明的，对应于制剂的每个部分 .

  sum (i in Cities : s.subtour[i] != 0)

  我在源代码中看到 subtour 是一个数组，每个城市 i ， subtour[i] 是 i 的后继者 . 因此，给定一个小计，这条线将所有拥有后继城市的城市相加 .

  x[<minl(i, s.subtour[i]), maxl(i, s.subtour[i])>] <= s.size-1;

  这是指变量 xij ，但是要注意事实 i < j ，因为在对称TSP中没有必要为 i < j 和 j < i 定义变量 .

  在源代码中动态添加了子树消除约束（在大多数实现中，因为它们的数量是指数的，所以 O(2^n) ） .

  在逻辑术语中，约束条件表示应该连接任何给定的城市集，并且不允许任何小计 .

  我希望这有帮助！

  回复于 2024-04-29T05:10:47+08:00