Indexing variables in sets in Xpress Mosel

Question

I'm trying to solve a linear relaxation of a problem I've already solved with a Python library in order to see if it behaves in the same way in Xpress Mosel.

One of the index sets I'm using is not the typical c=1..n but a set of sets, meaning I've taken the 1..n set and have created all the combinations of subsets possible (for example the set 1..3 creates the set of sets {{1},{2},{3},{1,2},{2,3},{1,2,3}}).

In one of my constraints, one of the indexes must run inside each one of those subsets. The respective code in Python is as follows (using the Gurobi library):

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()

(In case the code above is confusing, which I suspect it to be)The constraint I'm trying to write is:

z(i,j)>= sum_{h in C1}(x(i,h)-x(j,h)) forall C1 in C

in which the C1 is each of those subsets.
Is there a way to do this in Mosel?

Susanne Heipcke · Answer 1 · 2021-04-21T08:51:11.577

You could use some Mosel code along these lines (however, independently of the language that you are using, please be aware that the calculated 'set of all subsets' very quickly grows in size with an increasing number of elements in the original set C, so this constraint formulation will not scale up well):

  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))

Giving this some more thought, the following version working with lists in place of sets is more efficient (that is, faster):

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))

Thank you so much for your help! It says that I don't have enough reputation to cast a vote on your answer but if I could, I would have because this is exactly what I was looking for! — Scarlett.R, Apr 21 '21 at 10:33

Indexing variables in sets in Xpress Mosel

1 Answers1