I have a number $W\in\mathbb{R}$ and a vector $w=\left[w_1,\dots,w_n\right]^T\in\mathbb{R}^n$ such that each $w_i=i\cdot g$ where $g=const$. Usually $n\leq4$. The goal is to find a vector $c=\left[c_1,\dots,c_n\right]^T\in\mathbb{Z}^n$ such that
- $\sum_1^nc_iw_i$ is as close as possible to $W$ but doesn't exceed it
- $\sum_1^nc_i$ is $\min$
- smaller $w_i$ are avoided as much as possible
Example:
$$W=100$$ $$g=10, n=3\Rightarrow$$ $$w=\left[1\cdot 10, 2\cdot 10, 3\cdot 10\right]^T=\left[10,20,30\right]^T$$ For this setup the best solution would be NOT $$c=\left[1,0,3\right]^T$$ $$\left(1\cdot10+0\cdot20+3\cdot30=100\right)$$ but rather $$c=\left[0,2,2\right]^T$$ $$\left(0\cdot10+2\cdot20+3\cdot30=100\right)$$
Once again, $W,w_i,g$ are real numbers, $c_i$ must be integers.
After some time of mental work, I'm stuck (I'm not a mathematician) in
- what type of problem it is? integer linear programming?
- point 1 in the list above: is the condition $\sum_1^nc_iw_i\leq W$ is enough to cover the as close as possible condition?
- point 3 in the list above: how to formulate this constraint? should I introduce value for each $w_i$ (like in the knapsack problem)?
- which programming package in python or R should I use
Thank you in advance!
Yes, this is integer linear programming, with multiple objectives. One way to handle multiple objectives is to blend them into a single objective, but it sounds like you have a ranking of importance. In that case, you would optimize the most important (primary) objective first: maximize $\sum_i c_i w_i$ subject to $\sum_i c_i w_i \le W$. Suppose this maximum is $z_1^*$. Then include an additional (objective cut) constraint $\sum_i c_i w_i \ge z_1^*$, and optimize the next (secondary) objective: minimize $\sum_i c_i$. Suppose this minimum is $z_2^*$. Then include a second (objective cut) constraint $\sum_i c_i \le z_2^*$, and optimize the third (tertiary) objective, which might be to minimize $\sum_i 2^{-i} c_i$.