I need to withdraw the maximum amount from different accounts under the following conditions:
The following are the conditions:
1.) Minimum withdrawal is $\$1$.
2.) Amount can be transferred from one account to other account and this can be done multiple times.
3.) Minimum amount that can be transferred from one account to other account is $\$0.5$.
4.) The percentage amount that will be deducted for transferring the amount from one account to other account is 5%.
I would like to know the best possible algorithm that can be used here in order to withdraw the maximum amount from all the accounts.
Examples:
Account1 - $\$1.23$
Account2 - $\$0.34$
Account3 - $\$0.67$
Account4 - $\$0.05$
Account5 - $\$0.12$
Account6 - $\$0.78$
Account7 - $\$0.45$
Account8 - $\$0.34$
Account9 - $\$0.25$
Account10 - $\$0.14$
Detailed Explanation below:
1.) Account1 can be withdrawn directly since it is greater than $\$1$.
2.) Account2 cannot be withdrawn directly but can be combined with Account3 or Account6 since they are above $\$0.5$. It can only be withdrawn when the amount is greater than or equal to $\$1$.
If we transfer the amount from Account3 to Account2 it will sum upto $\$0.9765$ since 5% is deducted when transferring from Account3 to Account2. So, this cannot be withdrawn since the total is less than $\$1$.
If we transfer the amount from Account6 to Account2 it will sum upto $\$1.081$ since 5% is deducted from Account6 while transferring. This can be withdrawn directly, since the amount is greater than $\$1$.
3.) If we withdraw the amounts initially which are greater than $\$1$, we will be left with accounts which are less than $\$0.5$ and they cannot be combined in order to withdraw. So we need to combine the amount with account greater than 1$ to withdraw.
The challenging task is to optimize the selection in such a way that we withdraw the maximum amount after multiple combinations considering the 5% deduction when transferring. The amount when transferred should be the most profitable. As an example if the accounts have values $\$0.5$ and $\$0.6$, it would be profitable if the amount is transferred from $\$0.5$ account to $\$0.6$ account since the 5% is deducted when transferring. 5% of $\$0.5$ is less when compared to 5% of $\$0.6$.
Lets say all the accounts sum upto $\$300$, then what is the maximum amount that can be withdrawn by combining them and the corresponding combinations for transferring the amount.
Thank you
You can solve this as a generalized maximum flow problem with semicontinuous flows. Let $a_i$ be the initial amount in account $i$, and let $M=\sum_i a_i$. Let continuous decision variable $t_{ij} \ge 0$ be the amount transferred from account $i$ to account $j$, and let binary decision variable $x_{ij}$ indicate whether $t_{ij} > 0$. Let continuous decision variable $w_i \ge 0$ be the amount withdrawn from account $i$, and let binary decision variable $y_i$ indicate whether $w_i > 0$. The problem is to maximize $\sum_i w_i$ subject to linear constraints \begin{align} \sum_j t_{ij} + w_i - 0.95 \sum_j t_{ji} &\le a_i &&\text{for all $i$} \tag1\label1 \\ 0.5 x_{ij} \le t_{ij} &\le M x_{ij} &&\text{for all $i\not= j$} \tag2\label2 \\ y_i \le w_i &\le M y_i &&\text{for all $i$} \tag3\label3 \end{align} Constraint \eqref{1} enforces generalized flow balance. Constraint \eqref{2} enforces semicontinuity of $t_{ij}$; that is, $t_{ij}>0 \implies t_{ij} \ge 0.5$. Constraint \eqref{3} enforces semicontinuity of $w_i$; that is, $w_i>0 \implies w_i \ge 1$.
The optimal objective value turns out to be $4.13$, attained as follows (but there are also alternative optimal solutions): \begin{matrix} t_{ij} & i \backslash j &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 \\ \hline &1 && 0.73 & 0 & 0 & 0.5 & 0 & 0 & 0 & 0 & 0 & \\ &2 & 0 && 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\ &3 & 0 & 0 && 0.67 & 0 & 0 & 0 & 0 & 0 & 0 & \\ &4 & 0 & 0 & 0 && 0 & 0 & 0 & 0 & 0 & 0.6865 & \\ &5 & 0 & 0 & 0 & 0 && 0 & 0.595 & 0 & 0 & 0 & \\ &6 & 0 & 0 & 0 & 0 & 0 && 0 & 0.78 & 0 & 0 & \\ &7 & 0 & 0 & 0 & 0 & 0 & 0 && 0 & 0 & 0 & \\ &8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 && 0 & 0 & \\ &9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 && 0 & \\ &10 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.79217 && \\ \end{matrix} \begin{matrix} i & w_i & y_i \\ \hline 1 &0 &0 \\ 2 &1.0335 &1 \\ 3 &0 &0 \\ 4 &0 &0 \\ 5 &0 &0 \\ 6 &0 &0 \\ 7 &1.0153 &1 \\ 8 &1.0810 &1 \\ 9 &1.0026 &1 \\ 10 &0 &0 \\ \end{matrix}