1
$\begingroup$

There are $n$ sources with the following positive volumes: $p_1, ..., p_n$ and there are $m$ destinations with the following positive volumes: $q_1, ..., q_m$. It is known that $p_1+ ...+ p_n=q_1+ ...+ q_m$. Each source is going to use its volume to fill up one or more destination(s). If a source fills one destination, we are paying $1$ for it. If it fills $k$ destinations we are paying $k$ for it. The problem is to fill destinations using the sources so that the price is the smallest possible.

I need a help coming up with the algorithm for the problem.

Frankly speaking I am very lost here and can not come up with the algorithm which would be at least constantly better than going over all the possible fillings and choosing the one with the smallest price.

The thing I pondered over was sorting the sources in the ascending order and then taking the sources one by one, but I can not prove the correctness of such an approach.

$\endgroup$
  • $\begingroup$ This sounds like a homework problem, which you should disclose if it is the case since this isn't a site for others to do your homework. That being said, my hint is that this can be formulated as a mixed integer linear program. These problems are generally solved using a branch-and-bound algorithm. $\endgroup$ – Tyler Olsen Apr 13 '18 at 20:43
  • $\begingroup$ @TylerOlsen, no, it is not a homework problem. Though I had a similar one once, but it was a transportation problem. $\endgroup$ – ggghahaha Apr 13 '18 at 20:50
3
$\begingroup$

Let your decision variables be $X \in \mathbb{R}^{n\times m}$ and $Z \in \{0,1\}^{n\times m}$, where $X_{ij}$ is the amount produced by producer $i$ sent to consumer $j$. $Z_{ij}$ is a binary variable which is 1 if producer $i$ sends any thing to consumer $j$, 0 otherwise.

Your objective is to minimize the cost function: $$ c(X,Z) = \sum_{i,\,j}Z_{ij} $$ Subject to the following constraints: \begin{align} \sum_i X_{ij} &= q_j \;\; \forall j\in\{1...m\} \;\; \text{(Demand satisfied)} \\ % \sum_j X_{ij} &\le p_i \;\; \forall i\in\{1...n\}\;\;\text{(Producer supply constraint)} \\ % X_{ij} &\ge 0 \;\;\text{(Nonnegative production)}\\ X_{ij} &\le Z_{ij}p_i \;\; \text{($Z_{ij}$ must equal 1 if $X_{ij} \neq 0$)}\\ Z_{ij} &\in \{0,1\} \end{align}

In general, integer programs require you to use a branch-and-bound algorithm. However, since the only integer variables in this problem are restricted to be binary variables, I believe that you can treat $Z_{ij}$ as continuous and solve the problem using a linear programming solver.

If you're specifically interested in algorithms used to solve linear programs, you should google around for the "Dantzig's simplex algorithm," which is the most common way to solve modest-to-moderate-sized linear programs. For larger scale problems, "interior point" solvers tend to perform better than simplex-based solvers.

$\endgroup$
  • $\begingroup$ So, the thing you did is just reduced the problem to a linear problem which is easy to solve. Am I right? $\endgroup$ – ggghahaha Apr 13 '18 at 21:13
  • $\begingroup$ I think that Producer supply constraint should have an equal sign instead of less or equal sign. Am I right? $\endgroup$ – ggghahaha Apr 13 '18 at 21:18
  • 1
    $\begingroup$ Yes, I just re-stated the problem as one that I know how to solve (and for which there is a great deal of high-quality software available). As for the producer supply constraint, it should work either way. In my experience, solvers behave much more nicely if you use as few equality constraints as possible, since it gives them a bit of "wiggle room" in which to operate. $\endgroup$ – Tyler Olsen Apr 13 '18 at 21:23
  • 1
    $\begingroup$ You run the risk of over-constraining your problem by using all equality constraints, which will make good solvers error out and tell you that your problem is infeasible. In most cases, you would not know that the producers and consumers have perfectly balanced supply/demand, so an inequality constraint is more general. $\endgroup$ – Tyler Olsen Apr 13 '18 at 21:23
  • $\begingroup$ I am very stuck. I can easily solve the problem using branch-and-bounds approach if the volumes are integers. But I can not solve the problem if the volumes are real numbers. Should I learn about linear programming? Will it help? $\endgroup$ – ggghahaha Apr 15 '18 at 8:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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