4
$\begingroup$

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];
$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.