Originally posted by: AsToN

Hi everyone,

 

I am working on a multi-commodity flow problem in path formulation. As such each binary decision variable x[p][k] indicates whether path p is used to deliver order k. Now in order to secure that sufficient transport capacity is available at each arc a, I have a constraint of the following type:

 subject to {
     forall(a in setArcs)
       sum(k in setOrders, p in setPaths) x[k][p] * alpha[a][k][p] - sum(v in setVehicles, r in setRoutes) capacity[v] * y[v][r] * beta[a][v][r] <= 0;

  }

This constraint specifies that for each arc the sum of the order demand routed over this arc must be smaller than the total capacity that is provided on this arc. As such alpha[a][k][p] is 1 if arc a is part of path p used for delivering order k. Similarly beta[a][v][r] is 1 if arc a is part of route r driven by vehicle v.

 

Now my problem is how to efficiently deal with the binary arrays alpha and beta. Considering that there are potentially thousands of possible paths and also a huge number of available arcs the resulting arrays would be very large but also extremely sparse. Is there an efficient way to evaluate whether an arc is part of a path (or route), e.g. by providing an edge list for each path instead of a array of zeros and ones indicating whether an arc has been used or not?

 

Currently my path and route data is stored in a format like in the table below (however, that could be changed easily). Each path has a integer ID, a list of the integer IDs of the used arcs and a list of the string IDs of the arcs as well as the total distance of the path.

 

intPathID	intArcList	strArcList	fltPathDist
1	26  32  37  42  47	A6A7 A7B1 B1B2 B2B3 B3B4	117.52
2	26  32  37  43  82	A6A7 A7B1 B1B2 B2C3 C3B4	321.8

 

Any ideas how to do this efficiently?

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

in documentation IDE and OPL > Optimization Programming Language (OPL) > Language User's Manual > Introduction to OPL > Modeling tips

you may find a sparsity section.

In your example, you wrote

alpha[a][k][p] is 1 if arc a is part of path p used for delivering order k

 

instead you could use a tuple set with arc, path and order as fields

regards

 

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: AsToN

Hi Alex,

 

I am well aware how to generally exploit sparsity using tuples. However, I can't see how your suggestion with creating a tuple of the form <k,p,a> with value 1 would help me with my specific problem. Value 0 wouldn't exist since tuples would only be created for used combinations, otherwise there would be an equal number of tulples as array elements, nullifying any efficiency gains. As such this tuple representation would involve having no tuples for the acrs that are not used in the respective paths.

But my constraint has to hold for all arcs a, as such it will often ask for a tuple <k,p,a> that is not existing making the model infeasible.

 

Or am I getting your comment wrong?

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

indeed "tuples would only be created for used combinations"

you may see https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.7.0/ilog.odms.ide.help/OPL_Studio/opllanguser/topics/opl_languser_app_areas_LP_sparsity.html

regards

PS: could https://www.ibm.com/developerworks/community/forums/html/threadTopic?id=e7552283-246d-4702-9d8a-6fbf6d6cd90c&ps=25

help ?

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: AsToN

Hi Alex,

first thanks for you quick help.

 

The topic in your second link (https://www.ibm.com/developerworks/community/forums/html/threadTopic?id=e7552283-246d-4702-9d8a-6fbf6d6cd90c&ps=25

is related to my problem but still a little different. Let me explain...

 

If I want to exploit sparsity with tuples in my problem then I would have to do something like this:

 

My data originally comes in such a form:

intPathID	intArcList	strArcList	fltPathDist
1	26  32  37  42  47	A6A7 A7B1 B1B2 B2B3 B3B4	117.52
2	26  32  37  43  82	A6A7 A7B1 B1B2 B2C3 C3B4	321.8

giving me a list of used arcs for each possible path.

 

Now I could rewrite my constraint in the form:

     forall(a in setArcs)
       sum(k in setOrders, p in setArcsInPaths[k][a]) x[k][p] - sum(v in setVehicles, r in setArcsInRoutes[v][a]) capacity[v] * y[v][r] <= 0;

 

In this case I could get rid of my indicator variables alpha[a][k][p] and beta[a][v][r] by summing over new sparse sets setArcsInPaths and setArcsInRoutes. For this to work I need to create or import those arrays of sets which is also proving tricky.

 

What I want is an array of sets like this:

arcID / pathID	1	2	3	4	5
1	4	10	15	5	6
2	1	6	11	16
3	31	61	86
4	136	241	316	366	396
5	416	696

Each row gives the set of paths which uses a specific arc. Then I know that I just have to sum over those paths without the need to create indicator variables.

Now I even have those arrays ready in excel/matlab but I am unable to import them into my model. Since each arc has a different number of associated paths (and that number could be huge) I can't simply import it via a command like:

{tuple} arrArcsInPaths[setArcs] = ...; (since I can't define {tuple} appropriately).

 

So I am instead thinking about how to construct those arrays of sets inside of CPLEX via an execute block.

 

Any better suggestions or hints of how to implement the described approaches?

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

about " I even have those arrays ready in excel/matlab but I am unable to import them into my model. "

==> have you tried to use SheetRead in order to read that ?

about how to convert a set into an array you may adapt:

tuple t
{
int arc;
int path;
}

{t} s={

<1,4>,<1,10>,<1,15>,<1,5>,<1,6>,
<2,1>,<1,6>,
<3,31>,
<4,136>,
<5,416>
};

{int} arcs={i.arc | i in s};

{int} pathsPerArc[a in arcs]={i.path | i in s : i.arc==a};

execute
{
writeln(pathsPerArc);
}

which gives

[{4 10 15 5 6} {1} {31} {136} {416}]

regards

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: AsToN

That brought me on the right track. I had to reconstruct my input data a little but then it worked out. Thank you Alex!

#DecisionOptimization
#OPLusingCPLEXOptimizer