splittable multicommodity problem with CPLEX

Question

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];

Answer 1

I think that there might be a straightforward approach here that requires only solving a linear program.

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.