12

I have a set of sources and a set of sinks.

Each source $s$ can produce a set of different products $P_s$.

The transportation inter-sources and inter-sinks are allowed.

The sources do not necessarily produce the same products, but they may have products in common.

The same thing for sinks, a sink $t$ can absorb more than a single type of product (i.e., each sink has a set $D_t$ of demanded products), two sinks do not necessarily absorb exactly the same type of products, but they may have products in common though.

First case:

There are:

  • Transportation costs on arcs

  • Production costs on source nodes

  • Maximal production capacity on each node

  • Sinks have demands.

N.B. There are no maximal capacities on edges.

The decision is 1) which quantity to produce on each source for each product and 2) on which arcs to send the produced quantities? The objective is to reduce the total cost while satisfying the demand for each sink for each product. N.B. The transportation costs have an influence on the decision of how much quantity we produce in each source.

How do we call this problem in the literature? As far as I know, it's not a multi-commodity flow since in a multi-commodity flow we assume that each source(respectively sink) produce(respectively absorb) a different and unique commodity $k$, i.e, we have different pairs $(s_1,t_1), ..,(s_k,t_k)$ (thus the quantity produced in each source is simply equal to the quantity demanded by the sinks for the commodity $k$ but in my problem, it's part of the decision). Is there a paper that model/solve a similar problem? How to model it? I am also curious about the different approaches to solve it(exactly or not). Feel free to suggest any approach if you have an idea.

EDIT : The answer of @marco shows how to do some tricks in order to reduce the problem into a multi-commodity flow. (actually, a mincost flow, as the different commodities do not have a capacity on a common arc)

Second case:

What if the transportation costs defined on arcs and the production costs defined on source nodes are of the type fixed_cost + cost/unit instead of a cost/unit as in case 1. Is this still a multi-commodity flow problem? I think that the transformations described by @marco are still valid since only the costs change but the problem still have the same structure. But how this change can affect the hardness of the problem?

Antarctica
  • 2,917
  • 15
  • 34

1 Answers1

12

Your first case can be modeled as a minimum cost flow problem. You can

  1. split sinks with demands for more than one type into as many nodes as there are demanded types; make copies of incident arcs accordingly (this step results in sinks that have exactly one type of demand).

  2. split source nodes $i$ into copies $i'$ and $i''$, connect the copies with an arc $(i',i'')$ that receives the production capacity of sink $i$ (in mincost flow, you can only have capacities on arcs, not on nodes; this is the standard trick to transfer node to arc capacities). These arcs also receive the per unit production cost.

  3. if there is more than one source/sink per type, introduce a supersource that is connected to the original sources, with a supply equal to the total demand for this type.

  4. since you have no capacities, the problem should be solvable by sending a mincost flow separately for each type; in particular, this is doable in polytime.

All these are standard transformations, you can find them e.g., in the fabulous book Network Flows: Theory, Algorithms, and Applications by Ahuja, Magnanti, and Orlin (1993).

Your second case makes the problem a fixed-charge network flow problem which is NP-hard (see e.g., here), so for exact solutions you will probably resort to formulating the problem as a MILP.

rowtricker
  • 83
  • 4
Marco Lübbecke
  • 5,919
  • 22
  • 64
  • Sorry, I forgot about a maximal capacity production for each source. In this case, for each edge going out from an artificial source node(defined for a single product type) to a real source that produce this type of product, there is a maximal capacity tat is equal to the production capacity of the source. On the other edges there is no capacities. Am I right? If it's the case, I don't think that the problem is still solvable in polynomial time. What do you think? – Antarctica Feb 03 '20 at 01:03
  • 1
    adapted my answer – Marco Lübbecke Feb 03 '20 at 04:47
  • Another consideration: what if the costs are not defined per unit but have two terms : a fixed cost term paid whatever the quantity+ a per-unit term ? Is there a trick to do this? Thanks for the reference! – Antarctica Feb 03 '20 at 05:01
  • two things: 1. when you have a fixed cost component, things change; the you have fixed charge network flow; 2. if you really have that problem, then this evolution of the question is a good lesson in "be precise in stating the question" ;) – Marco Lübbecke Feb 03 '20 at 05:03
  • Okay, I apdated my question in order to include the second case. I took a look into the a "fixed charge network flow" problem. I think that the trasformations still valid since only the costs change but the problem still have the same structure. However, the solutions approaches may be quite different. – Antarctica Feb 03 '20 at 05:35
  • 1
    yes, precisely, this "only the cost changes" appears to drastically change the solvability of the problem, from polynomial time to NP-hard. – Marco Lübbecke Feb 03 '20 at 05:41
  • This is helpful. Thank you! – Antarctica Feb 03 '20 at 05:50
  • A fixed charge network problem has already a natural MILP formulation using arcs, so what did you mean by "resort to formulating the problem as a MILP" ? – Antarctica Feb 03 '20 at 14:59
  • 1
    @AmiraZarglayoun I wanted to contrast this to the minimum cost flow problem (your case 1), which can be solved by a combinatorial algorithm – Marco Lübbecke Feb 03 '20 at 15:29
  • Is there a way to know, a priori , if using a fixed-charge network problem formulation will be better in a MILP solver than using a straightforward formulation (where the produced quantity of each product is a decision variable on its own) – Antarctica Feb 06 '20 at 01:29
  • @AmiraZarglayoun I don't understand the question, what is a straightforward formulation in contrast to a MILP formulation? – Marco Lübbecke Feb 06 '20 at 01:34
  • I meant a straightforward MILP formulation. Instead of seeing the problem as a network flow where the produced quantities are consequence of the flow quantities, we forget about constructing a network using the tricks you mentioned and we introduce $y_{ik}$ which is the produced quantity in source node $i$ of product type $k$ and another variable $f_{ek}$ for the quantity to send on arc $e$ of product type $k$. The "straightforward" formulation seems to have more variables, is this sufficient to conclude that it would be better to use the fixed charge network flow formulation? – Antarctica Feb 06 '20 at 01:45
  • for me, there is no difference between a "network formulation" and a MILP formulation, just a different representation of the same thing. I can use a MILP to model the network flow and for everything more complicated this is exactly what I would do. MILP is the most flexible I know. – Marco Lübbecke Feb 06 '20 at 08:58