如何解释复杂旅行商问题中的子旅行消除约束？

Question

我写了下面的代码：

如何解释下面公式中的辅助约束和子游消除约束？

Answer 1

这看起来像 MTZ 约束。让我在 developerworks

中复制我 posted 的内容

一个非常有效的模型是 https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.ide.help/examples/html/opl/models/TravelingSalesmanProblem/tsp.mod.html

中 OPL 示例的一部分

但有些用户出于许多不同的原因需要更多：

他们不希望对带有额外约束的 cplex 进行多次调用，因为他们需要提供热启动或额外的特定约束
他们想尝试 CPO
许多其他原因

您可能会找到依赖于 CPO 调度的模型

using CP; 
int     n       = ...;
range   Cities  = 1..n;

int realCity[i in 1..n+1]=(i<=n)?i:1;



// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in 1..n};
setof(edge) Edges2       = {<i,j> | i,j in 1..n+1};  // node n+1 is node 1

int         dist[Edges] = ...;
int         dist2[<i,j> in Edges2]=(realCity[i]==realCity[j])?0:
((realCity[i]<realCity[j])?dist[<realCity[i],realCity[j]>]:dist[<realCity[j],realCity[i]>]);


dvar interval itvs[1..n+1] size 1;


dvar sequence seq in all(i in 1..n+1) itvs[i]; 

execute
{

cp.param.TimeLimit=60;
var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(seq));
}

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = { 
    <i-1,j-1,dist2[<i ,j >]>
           |  i,j in 1..n+1};


minimize endOf(itvs[n+1]) - (n+1);           
subject to
{
    startOf(itvs[1])==0; // break sym
    noOverlap(seq,Dist,true);   // nooverlap with a distance matrix
    last(seq, itvs[n+1]); // last node
}


 int  x[<i,j> in Edges]=prev(seq,itvs[i],itvs[j])+prev(seq,itvs[j],itvs[i]); 
 int  isPrevFromNPlus1[i in 1..n]=prev(seq,itvs[i],itvs[n+1]);
 int l=first({i | i in 1..n : isPrevFromNPlus1[i]==1});
 edge el=<1,l>;

 execute
 {
 isPrevFromNPlus1;
 x; 
 x[el]=1;
 }

 // Let us check here that the constraints of the IP model are ok
 assert forall (j in Cities)
        as:sum (<i,j> in Edges) x[<i,j>] + sum (<j,k> in Edges) x[<j,k>] == 2;

// Let us compute here the objective the IP way
int cost=sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>];

execute
{
writeln(cost);
}

让我在这里提供更多选项，我将依赖与 tsp 示例相同的 .dat 格式

1) 我们可以直接移除所有电路，但是这不是很有效，可以检查：

// Cities
int     n       = ...;
range   Cities  = 1..n;

// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in Cities};
int         dist[Edges] = ...;

// Decision variables
dvar boolean x[Edges];

 {int} nodes={i.i | i in Edges} union {i.j | i in Edges};

range r=1..-2+ftoi(pow(2,card(nodes)));


{int} nodes2 [k in r] = {i | i in nodes: ((k div (ftoi(pow(2,(ord(nodes,i))))) mod 2) == 1)};





/*****************************************************************************
 *
 * MODEL
 *
 *****************************************************************************/

// Objective
minimize sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>];
subject to {

   // Each city is linked with two other cities
   forall (j in Cities)
        sum (<i,j> in Edges) x[<i,j>] + sum (<j,k> in Edges) x[<j,k>] == 2;

   // Subtour elimination constraints.


forall(k in r)  // all subsets but empty and all
    sum(e in Edges:(e.i in nodes2[k]) && (e.j in nodes2[k])) x[e]<=card(nodes2[k])-1;  

 }

2) 更好并依赖于 CPLEX 的是 MTZ 模型（Miller-Tucker-Zemlin 公式）

// Cities
int     n       = ...;
range   Cities  = 1..n;

// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in Cities};
int         dist[Edges] = ...;

setof(edge) Edges2       = {<i,j> | i,j in Cities : i!=j};
int         dist2[<i,j> in Edges2] = (<i,j> in Edges)?dist[<i,j>]:dist[<j,i>];

// Decision variables
dvar boolean x[Edges2];

dvar int u[1..n] in 1..n;



/*****************************************************************************
 *
 * MODEL
 *
 *****************************************************************************/

// Objective
minimize sum (<i,j> in Edges2) dist2[<i,j>]*x[<i,j>];
subject to {

   // Each city is linked with two other cities
   forall (j in Cities)
     {
        sum (<i,j> in Edges2) x[<i,j>]==1;
        sum (<j,k> in Edges2) x[<j,k>] == 1;
   }  


 // MTZ

u[1]==1;
forall(i in 2..n) 2<=u[i]<=n;
forall(e in Edges2:e.i!=1 && e.j!=1) (u[e.j]-u[e.i])+1<=(n-1)*(1-x[e]);

};

{edge} solution={e | e in Edges2 : x[e]==1};

execute
{
writeln("path ",solution);
}

3) 没有安排的 CPO

using CP;
int     n       = ...;
range   Cities  = 1..n;

int realCity[i in 1..n+1]=(i<=n)?i:1;



// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in 1..n};
setof(edge) Edges2       = {<i,j> | i,j in 1..n};  // node n+1 is node 1

int         dist[Edges] = ...;
int         dist2[i in 1..n][j in 1..n] = (i==j)?0:((i<j)?dist[<i,j>]:dist[<j,i>]);

execute
{

cp.param.TimeLimit=60;

}

dvar int x[1..n] in 1..n;

dvar int obj;

minimize obj;

// x means who is on i th position
subject to
{
x[1]==1;
allDifferent(x);

obj==sum(i in 1..n-1) dist2[x[i]][x[i+1]]+dist2[x[1]][x[n]];


}

Answer 2

MTZ subtour消除方法的解释其实很简单。按访问顺序为每个节点分配数字 u(i)。约束

u(i) - u(j) + n x(i,j) <= n - 1

可以解释为

u(j) >= u(i) + 1 - M*(1-x(i,j))

或

x(i,j) = 1 ==>   u(j) >= u(i) + 1

如果你有一个 subtour 说 2-3-2 这不能成立：

2-3 means u(3) >= u(2)+1
3-2 means u(2) >= u(3)+1

由于应该允许整个巡回，我们只从该检查中删除第一个节点。

如何解释复杂旅行商问题中的子旅行消除约束？

How to interpret sub tour elimination constraint in travelling salesman problem in cplex?

linear-programming

cplex

traveling-salesman

mixed-integer-programming