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]
Topic
NOTICE: developerWorks Community will be offline May 2930, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
This topic has been locked.
5 replies
Latest Post
 20141027T18:03:56Z by ChrisBr
ACCEPTED ANSWER
Pinned topic Indexing a set, cannot extract expression in objective function
20121011T10:31:39Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Updated on 20121011T12:51:46Z at 20121011T12:51:46Z by salais

ACCEPTED ANSWER
Re: Indexing a set, cannot extract expression in objective function
20121011T12:07:45Z in response to salaisHello.
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 
ACCEPTED ANSWER
Re: Indexing a set, cannot extract expression in objective function
20121011T12:42:40Z in response to salaisHi,
the documentation of element constraint explains why your code cannot execute :
Element constraints
The following subscripting operators return constrained integer or floatingpoint 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 workarounds : 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 biindexed by nodes. Then you can query the element constraint directly (meaning you can access to
directly )dist2[i][S[i]]
I attach these two modifications in a file
Hope it helps
DavidAttachments

ACCEPTED ANSWER
Re: Indexing a set, cannot extract expression in objective function
20121011T12:51:46Z in response to davidoffHi,
Indeed your suggestions proved helpful for the objective function. Thank you very much!
Marking question as answered.
ACCEPTED ANSWER
Re: Indexing a set, cannot extract expression in objective function
20141024T22:38:04Z in response to salaisHi,
How could you codes the 4th constraint?

ACCEPTED ANSWER
Re: Indexing a set, cannot extract expression in objective function
20141027T18:03:56Z in response to nonelessHello Hadi,
I think that you want to model a subtour 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.


