Originally posted by: mdmasbaul

Dear all

I am trying to model Golomb ruler problem in CPlex. The problem says the difference between all pair of numbers must be different. For example, 0 1 4 6 is a solution for size n=4. To model this, in SUBJECT TO section, i have written like this:

allDifferent(all(i,j in 1..n : i < j) (golombRuler[j] - golombRuler[i]));

but the error says, argument type mismatch. any suggestion? Note that here golombRuler is a dvar like following

dvar int+ golombRuler[1..n] in 0..m;

Hi,

allDifferent works with decision variables but not with expressions like x-y

Have a look at the nqueens example at https://www.ibm.com/developerworks/community/forums/html/topic?id=77777777-0000-0000-0000-000014424774

regards

Originally posted by: mdmasbaul

Thanks Alex for the reply. I have updated my code after looking into the NQueen code. My code now looks like the following:

int k=0;

SUBJECT TO

forall(i in 1..n-1) {
forall(j in i+1..n){
diffArray[k] == golombRuler[j] - golombRuler[i];
k==k+1;
};
};
allDifferent(diffArray);

However, now the diffArray comes up empty, so no solution. Can you please guide me what is it that I am doing wrong?

To be clear, here I am trying to store the difference of all pairs of numbers in k index of diffArray.

HI

k==k+1;

leads to infeasible since k is never equal to k+1

You mix constraints and imperative instructions

See https://www.ibm.com/developerworks/community/forums/html/topic?id=77777777-0000-0000-0000-000014700425&ps=25

regards

Originally posted by: mdmasbaul

<code>

using CP;

 
int n = 5;
int m = 11;
range marks = 1..n;
range positions = 0..m;

dvar int+ golombRuler[marks] in positions;
dvar int+ diffArray[1..m-1] in positions;

minimize golombRuler[n];

subject to {
golombRuler[1] == 0;
golombRuler[n] == m;
forall (i in 1..n-1) {
    golombRuler[i] < golombRuler[i+1];
};

forall(i,j in 1..n:j>i,k in 1..ftoi(n*(n-1)/2)){
  diffArray[k] == abs(golombRuler[i] - golombRuler[j]);
};  
allDifferent(diffArray);
}

execute{
  var ofile = new IloOplOutputFile("GolombRulerOutput.dat", true);
  ofile.writeln("Golomb Ruler(n, m)::");
  ofile.writeln("Golomb Ruler("+n+", "+m+"):");
  ofile.write("[");
  for(var i in thisOplModel.golombRuler){
     ofile.write(" "+thisOplModel.golombRuler[i]);
  }
  for(var i in thisOplModel.diffArray){
     ofile.write(" "+thisOplModel.diffArray[i]);
  }
  ofile.writeln(" ]");
  ofile.write("\n\n\n");
  ofile.close();
}

</code>

Yes, you are right, I understood it in a wrong way. However, I have updated the code but still it produces no solution. Can you please have a look at my code above.

Hi,

your constraint for diffarray is not good. You do not link k with i and j.

Let me fix your model:

using CP;

 
int n = 5;
int m = 11;
range marks = 1..n;
range positions = 0..m;

tuple ij
{
int i;
int j;
}

{ij} ijs={<i,j> | i,j in 1..n:i<j};

assert card(ijs)==n*(n-1)/2;

dvar int+ golombRuler[marks] in positions;
dvar int+ diffArray[ijs] in positions;

minimize golombRuler[n];

subject to {
golombRuler[1] == 0;
golombRuler[n] == m;
forall (i in 1..n-1) {
    golombRuler[i] < golombRuler[i+1];
};

//forall(i,j in 1..n:j>i,k in 1..ftoi(n*(n-1)/2)){
forall(k in ijs) {
  diffArray[k] == abs(golombRuler[k.i] - golombRuler[k.j]);
};  
allDifferent(diffArray);
}

execute{
  var ofile = new IloOplOutputFile("GolombRulerOutput.dat", true);
  ofile.writeln("Golomb Ruler(n, m)::");
  ofile.writeln("Golomb Ruler("+n+", "+m+"):");
  ofile.write("[");
  for(var i in thisOplModel.golombRuler){
     ofile.write(" "+thisOplModel.golombRuler[i]);
  }
  for(var i in thisOplModel.diffArray){
     ofile.write(" "+thisOplModel.diffArray[i]);
  }
  ofile.writeln(" ]");
  ofile.write("\n\n\n");
  ofile.close();
}

regards

https://www.linkedin.com/pulse/what-optimization-how-can-help-you-do-more-less-zoo-buses-fleischer/

Originally posted by: mdmasbaul

Thanks so much Alex. I really appreciate your help.