12
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • $\begingroup$ 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? $\endgroup$
    – Antarctica
    Commented Feb 3, 2020 at 1:03
  • 1
    $\begingroup$ adapted my answer $\endgroup$
    – Marco Lübbecke
    Commented Feb 3, 2020 at 4:47
  • $\begingroup$ 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! $\endgroup$
    – Antarctica
    Commented Feb 3, 2020 at 5:01
  • 1
    $\begingroup$ yes, precisely, this "only the cost changes" appears to drastically change the solvability of the problem, from polynomial time to NP-hard. $\endgroup$
    – Marco Lübbecke
    Commented Feb 3, 2020 at 5:41
  • 1
    $\begingroup$ @AmiraZarglayoun I wanted to contrast this to the minimum cost flow problem (your case 1), which can be solved by a combinatorial algorithm $\endgroup$
    – Marco Lübbecke
    Commented Feb 3, 2020 at 15:29

Your Answer

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

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