Я написал следующий код:
Как интерпретировать вспомогательные ограничения и ограничения исключения субтуров в следующей формулировке?
Я написал следующий код:
Как интерпретировать вспомогательные ограничения и ограничения исключения субтуров в следующей формулировке?
Интерпретация подхода исключения субтуров MTZ на самом деле довольно проста. Назначьте номера u(i)
каждому узлу в порядке их посещения. Ограничение
u(i) - u(j) + n x(i,j) <= n - 1
можно интерпретировать как
u(j) >= u(i) + 1 - M*(1-x(i,j))
or
x(i,j) = 1 ==> u(j) >= u(i) + 1
Если у вас есть подтур, скажем, 2-3-2, это не может состояться:
2-3 means u(3) >= u(2)+1
3-2 means u(2) >= u(3)+1
Поскольку весь тур должен быть разрешен, мы просто удаляем первый узел из этой проверки.
это похоже на ограничение MTZ. Позвольте мне скопировать то, что я опубликовал на сайте developerworks.
очень эффективная модель является частью примеров OPL по адресу https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.ide.help/examples/html/opl/models/TravelingSalesmanProblem/tsp.mod.html
но некоторым пользователям нужно больше по разным причинам:
Вы можете найти модель, основанную на планировании 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);
}
Позвольте мне предложить здесь больше вариантов, и я буду полагаться на тот же формат .dat, что и в примере с tsp.
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 (формулировка Миллера-Такера-Землина)
// 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]];
}