2
$\begingroup$

I have a demand, $d$

I also have supply from 1000 sources. The supplies from those $N$ (for example, $N=1000$) sources are given by

$s_1,s_2,s_3,\cdots,s_N$. So,the total supply is : $s_1+s_2+\cdots+s_N$

How can I meet the demand with least amount of resources wasted?

so, the objective is to have minimum $(d-supply)$. The supply can come from any number of sources.

A heuristic approach is welcome.

Improve this question
$\endgroup$
1
  • $\begingroup$ I think you meant to minimize supply minus demand instead of the other way around. $\endgroup$ – RobPratt Sep 7 '20 at 13:54
5
$\begingroup$

Introduce a binary variable $x_i$ for each supply and nonnegative waste variable $w$. The problem is to minimize $w$ subject to $\sum_i s_i x_i -w= d$.

A heuristic approach is to sort the supplies in decreasing order and greedily take the largest ones until the sum satisfies the demand. Then, if the demand is not met exactly, exchange the last added supply with the smallest remaining supply that satisfies the demand.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. In fact, I am looking for some heuristic approach. $\endgroup$ – dipak narayanan Sep 7 '20 at 13:59
  • $\begingroup$ will $\min\hspace{3mm}\sum_{n=1}^Nx_n$ subject to $d\le \sum_{n=1}^N s_nx_n$ do the job? $\endgroup$ – dipak narayanan Sep 7 '20 at 14:01
  • $\begingroup$ You need $s_n x_n$ in the summand for the objective. With that correction, this is equivalent to my suggestion but with more coefficients and objective parallel to the constraint. $\endgroup$ – RobPratt Sep 7 '20 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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