Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
5 replies Latest Post - ‏2014-10-27T18:03:56Z by ChrisBr
salais
salais
3 Posts
ACCEPTED ANSWER

Pinned topic Indexing a set, cannot extract expression in objective function

‏2012-10-11T10:31:39Z |
Hello everyone,

I am completely new to OPL and am having a little trouble implementing a TSPTW model according to the paper "An exact constraint logic programming algorithm for the traveling salesman problem with time windows" (Pesant et al.)

However I am getting an error in the model and I don't really know why. I have a strong background in programming but I can't seem to figure this out. Note that this is a work in progress. Any suggestions will be greatly appreciated.

The model:
code
/*********************************************
* OPL 12.4 Model
* Author:
* Creation Date: 11.10.2012 at 10.35.01
*********************************************/

using CP;

// TSP Formulation alá Pesant et al.
int N = ...;
range Nodes = 1..N;

tuple edge {int i; int j;}
setof(edge) Edges = {<i,j> | i,j in Nodes};
int distEdges = ...;

range V = 2..N;
range Vo = 1..N;
range Vd = 2..(N+1);
range Vod = 1..(N+1);

// Dvar = list of successors
dvar int SNodes;

// MODEL (src: An exact constraint logic programming algorithm for the traveling salesman problem with time windows)
minimize sum (i in Vo) dist[<i, Si]>;
// The above statement yields an error message of "cannot extract expression: dist[<i, Si]>"

subject to
{
// (2)
forall (i,j in Vo : i != j)
S[i] != S[j];

// (3)
forall (i in Vo)
S[i] != i;
// (5)
forall (i in Vo)
1 <= S[i] <= (N+1);

};

execute
{
writeln("PostProc.");
writeln("Distances:");
for (var i in dist)
{
write(i);
write(": ");
writeln(dist[i]);
}

writeln("");
writeln("Successors:");
for (var j in S)
write(S[j]);
}
main
{
var opl = thisOplModel
var mod = opl.modelDefinition;
var dat = opl.dataElements;

var cp1 = new IloCP();
opl = new IloOplModel(mod,cp1);
opl.addDataSource(dat);
opl.generate();

// Solve problem with current constraints
if (!cp1.solve())
{
writeln("ERROR: could not solve");
status = 1;
opl.end();
}

opl.postProcess();
opl.end();
cp1.end();
}
[/code]

My data:
code

/*********************************************
* OPL 12.4 Data
* Author:
* Creation Date: 11.10.2012 at 10.35.08
*********************************************/

N = 4;

dist = [
0, 1, 3, 2,
1, 0, 1, 2,
3, 1, 0, 1,
2, 2, 1, 0];
[/code]
Updated on 2012-10-11T12:51:46Z at 2012-10-11T12:51:46Z by salais
  • SystemAdmin
    SystemAdmin
    623 Posts
    ACCEPTED ANSWER

    Re: Indexing a set, cannot extract expression in objective function

    ‏2012-10-11T12:07:45Z  in response to salais
    Hello.

    The problem is the indexing by tuple. It is allowed in constant expressions (that are evaluated by OPL language), but not in expressions that depends on decision variables (because underlying CP engine is not able to evaluate them). The error "cannot extract" basically means that the solver does not support this kind of expression.

    CP Optimizer understands though indexing by integer expressions. In your case, you can convert dist into two dimensional array and then use it in the objective like this:
    
    
    
    int dist2[Nodes][Nodes] = ...;   minimize sum (i in Vo) dist2[i][S[i]];
    

    That also requires a small change in data file:
    
    dist2 = [ [0, 1, 3, 2], [1, 0, 1, 2], [3, 1, 0, 1], [2, 2, 1, 0]];
    


    Best regards, Petr
  • davidoff
    davidoff
    51 Posts
    ACCEPTED ANSWER

    Re: Indexing a set, cannot extract expression in objective function

    ‏2012-10-11T12:42:40Z  in response to salais
    Hi,

    the documentation of element constraint explains why your code cannot execute :
    Element constraints
    The following subscripting operators return constrained integer or floating-point expressions, also known as element expressions.

    A[X], where A is an array of integer values (with one or several dimensions) and X is a dexpr int, returns a dexpr int such that: when X is fixed to the value i, the value of the expression is A[i].

    In your code, A is an array indexed by tuples.

    There are two work-arounds : the more general one is to use an allowedAssigments constraint that will match the distance with the successor of any given node. Then, you have a direct access to the distance to a successor of a node (e.g as an other decision variable)

    The easiest way here, noticing that your distance matrix is not sparse, is to define an other distance matrix which is bi-indexed by nodes. Then you can query the element constraint directly (meaning you can access to
    
    dist2[i][S[i]]
    
    directly )

    I attach these two modifications in a file

    Hope it helps

    David
    • salais
      salais
      3 Posts
      ACCEPTED ANSWER

      Re: Indexing a set, cannot extract expression in objective function

      ‏2012-10-11T12:51:46Z  in response to davidoff
      Hi,

      Indeed your suggestions proved helpful for the objective function. Thank you very much!

      Marking question as answered.
      • noneless
        noneless
        19 Posts
        ACCEPTED ANSWER

        Re: Indexing a set, cannot extract expression in objective function

        ‏2014-10-24T22:38:04Z  in response to salais

        Hi,

        How could you codes the 4th constraint?

        • ChrisBr
          ChrisBr
          40 Posts
          ACCEPTED ANSWER

          Re: Indexing a set, cannot extract expression in objective function

          ‏2014-10-27T18:03:56Z  in response to noneless

          Hello Hadi,

          I think that you want to model a sub-tour elimination constraint.
          I suggest you to have a look at the distributed sample "euler.mod".
          (..../IBM/ILOG/CPLEX_Studio126/opl/examples/opl/euler/euler.mod)

          I hope this helps.

          BTW, it would be better to open another thread if you want to follow this because the current subject of this one is about another question which moreover is considered as already answered.

          Regards,


          Chris.