# splittable multicommodity problem with CPLEX

I am working on a splittable multicommodity flow problem, where each commodity can be split into k orders. However, I don't know the value of k in advance. Here is my code.


{string} nodes=...;

tuple Arc {
string fromnode;
string tonode; }
{Arc} arcs=...;

tuple Commodity{
key int no;
string origin;
string dest;
int due_time;
int departure_time;
}

{Commodity} commodities =...;
{Commodity} orders =...; // there is something wrong



Actually, the tuple"orders" should be a subset of "commodities". I mean "orders" share the same characteristics with "commodities", while I don't know the volume of each commodity and how many orders consist of one commodity. All of them should be calculated by MCF.

So how should I express "orders"? I also want to find a suitable index of orders, like:

dvar demand[c in commodities][k in orders]
dvar arrival_time[c in commodities][k in orders];


Thanks!

Consider the LP arc-flow formulation of multi-commodity network flow; I won't repeat it here since it is very well known. The solution is expressed by flow variables $$x^b_{ij}$$, the flow of commodity $$b$$ on network directed arc $$(i,j)$$. Based on your description, each commodity $$b$$ has a single origin and destination. Thus, for each $$b$$, the arcs $$(i,j)$$ where $$x^b_{ij}>0$$ are such that one or more paths from $$orig(b)$$ to $$dest(b)$$ exist using only those arcs. Call this set of arcs $$A(b)$$. Now consider the idea of flow decomposition into paths for each commodity $$b$$ given a feasible multi-commodity flow solution; this is a well-known concept in network flows. The idea essentially is that you can sequentially find unique paths $$p$$ from $$orig(b)$$ to $$dest(b)$$ in $$A(b)$$ and assign a path flow $$x^b_p$$ equal to the minimum (remaining) flow $$x^b_{ij}$$ for all arcs $$(i,j) \in p$$. You then remove this flow from all arcs and repeat until you have assigned all commodity $$b$$ flow to paths.
In my view, you have now solved your problem! For each commodity $$b$$, each path flow $$x^b_p$$ represents a single order (in your terminology). The value of $$k$$ then is simply the maximum number of path flows you find for any commodity. Note that you could modify this approach even if you had a maximum size per order.