0

我正在尝试解决我已经用 Python 库解决的问题的线性松弛，以查看它在 Xpress Mosel 中的行为是否相同。

我使用的一个索引集不是典型的 c=1..n 而是一组集，这意味着我已经采用了 1..n 集并创建了所有可能的子集组合（例如集合1..3 创建集合集{{1},{2},{3},{1,2},{2,3},{1,2,3}}）。

在我的约束之一中，索引之一必须在这些子集中的每个子集中运行。Python中的相应代码如下（使用Gurobi库）：

cluster=[1,2,3,4,5,6]
cluster1=[]
for L in range(1,len(cluster)+1):
    for subset in itertools.combinations(cluster, L):
        clusters1.append(list(subset))
ConstraintA=LinExpr()
ConstraintB=LinExpr()
for i in range(len(nodes)):
    for j in range(len(nodes)):
        if i<j and A[i][j]==1:
            for l in range(len(clusters1)):
                ConstraintA+=z[i,j]
                for h in clusters1[l]:
                    restricao2B+=(x[i][h]-x[j][h])
                model.addConstr(ConstraintA,GRB.GREATER_EQUAL,ConstraintB)
                ConstraintA=LinExpr()
                ConstraintB=LinExpr()

（如果上面的代码令人困惑，我怀疑是这样）我要编写的约束是：

z(i,j)>= sum_{h in C1}(x(i,h)-x(j,h))C中的所有C1

其中 C1 是每个子集。
有没有办法在摩泽尔做到这一点？

4

1 回答 1

2

您可以沿这些行使用一些 Mosel 代码（但是，与您使用的语言无关，请注意，随着原始集合 C 中元素数量的增加，计算出的“所有子集的集合”的大小会迅速增长，所以这个约束公式不会很好地扩展）：

  declarations
    C: set of integer
    CS: set of set of integer
    z,x: array(I:range,J:range) of mpvar
  end-declarations

  C:=1..6
  CS:=union(i in C) {{i}}
  forall(j in 1..C.size-1) 
    forall(s in CS | s.size=j, i in C | i > max(k in s) k ) CS+={s+{i}}

  forall(s in CS,i in I, j in J) z(i,j) >= sum(h in s) (x(i,h)-x(j,h))

考虑到这一点，使用列表代替集合的以下版本更有效（即更快）：

uses "mmsystem"
declarations
  C: set of integer
  L: list of integer
  CS: list of list of integer
  z,x: array(I:range,J:range) of mpvar
end-declarations

C:=1..6
L:=list(C)
qsort(SYS_UP, L)          !  Making sure L is ordered
CS:=union(i in L) [[i]]
forall(j in 1..L.size-1) 
  forall(s in CS | s.size=j, i in L | i > s.last ) CS+=[s+[i]]

forall(s in CS,i in I, j in J) z(i,j) >= sum(h in s) (x(i,h)-x(j,h))
于 2021-04-20T18:14:14.827 回答