使用 cplex-opl 的最小生成树

Question

我对 CPLEX 的编码感到困惑，网上没有任何帮助。请帮助我。

这是我的代码。我对 constraint2 有疑问，我不知道如何在 constraint2 求和之前定义 3 个条件。附上MST1配方图

这是我的代码。

range i= 1..7;
range j= 1..7;
range node=1..7;
{int} v= {1,2,3,4,5,6,7};   
{int} E={{1,2},{1,4},{1,6},{2,1},{2,4},{2,3},{2,5},{3,2},{3,5},{3,7},{4,1},{4,2},
{4,5},{4,7},{5,2},{5,3},{5,4},{5,7},{6,1},{6,4},{6,7},{7,3},{7,5},{7,6}};

float Q[node][node]=[[0,5,0,6,0,7,0,0],[5,0,5,5,4],[0,5,0,0,3,0,3],
[6,5,0,0,2,2],[0,4,3,2,0,0,1],[7,0,0,2,0,0,2],[0,0,3,0,1,2,0]];

dvar boolean x[i][j];


dexpr float w= sum(i,j in E)Q[node][node]*x[i][j];
minimize w;

/*****************constraint******************/
subject to {
cons1:
sum(i,j in E)x[i][j]==6;

cons2:
forall (s in sub[v]:{s}!={v}{s}!={})sum(i,j in E(s))x[i][j]<=abs(s)-1
  ;
}

Answer 1

我在 https://www.linkedin.com/pulse/tips-tricks-opl-cplex-alex-fleischer/

中发布了示例

minimum spanning tree

tuple edge
    {
        key int o;
        key int d;
        int weight;
    }

    {edge} edges=...;

    {int} nodes={i.o | i in edges} union {i.d | 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)};

    dvar boolean x[edges];

    minimize sum (e in edges) x[e]*e.weight;
    subject to
    {
    sum(e in edges) x[e]==card(nodes)-1;

    // Subtour elimination constraints.
       
    forall(k in r)  // all subsets but empty and all
        sum(e in edges:(e.o in nodes2[k]) && (e.d in nodes2[k])) x[e]<=card(nodes2[k])-1;  
       
    }

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

    execute
    {
    writeln("minimum spanning tree ",solution);
    }


/*
which gives
    minimum spanning tree  {<1 4 8> <2 3 3> <3 5 2> <4 5 8> <4 7 7> <5 6 2> <7 8 4>
         <8 9 1> <9 10 3>}
         
         */

Answer 2

我的一个同学编写了这个问题，我喜欢它并附在下面。

int numnod=8;
range nod=1..numnod;
int M=100;
float Q[nod][nod]=[[M,4,6,16,M,M,M,M],[4,M,M,M,M,M,24,M],
[6,M,M,8,5,M,23,M],[16,M,8,M,10,M,M,21],[M,M,5,10,M,11,18,M],
[M,M,M,M,11,M,9,7],[M,24,23,M,18,9,M,M],[M,M,M,21,M,7,M,M]];
range SS=1.. ftoi(round(2^numnod));
{int} Sub [s in SS]={i| i in 1..numnod: (s div ftoi(round(2^(i-1)))) mod      2==1};

dvar boolean x[nod][nod];
dexpr float objective=sum(i,j in nod)Q[i][j]*x[i][j];

minimize objective;
subject to{
sum(i,j in nod)x[i][j]==numnod-1;
forall(s in SS : 0<card(Sub[s])<numnod)Cons2:sum(i,j in Sub[s])x[i][j]<=card(Sub[s])-1;
}

使用 cplex-opl 的最小生成树

Min Spanning tree with cplex-opl

tree

cplex

minimum-spanning-tree