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.

$\endgroup$
1
  • $\begingroup$ I think you meant to minimize supply minus demand instead of the other way around. $\endgroup$
    – RobPratt
    Commented Sep 7, 2020 at 13:54

1 Answer 1

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.

$\endgroup$
3
  • $\begingroup$ Thanks. In fact, I am looking for some heuristic approach. $\endgroup$
    – KGM
    Commented Sep 7, 2020 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$
    – KGM
    Commented Sep 7, 2020 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
    Commented Sep 7, 2020 at 14:05

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.