Originally posted by: salais

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]
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

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
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: davidoff

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
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: salais

Hi,

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

Marking question as answered.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: noneless

Hi,

How could you codes the 4th constraint?

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: ChrisBr

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.
 

#DecisionOptimization
#OPLusingCPOptimizer