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$ Commented Sep 7, 2020 at 13:54

1 Answer 1

Reset to default
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$ 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$ 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$ Commented Sep 7, 2020 at 14:05

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.