- A product can only be ordered between a minimum and maximum amount
- There is a budget w.r.t. the total amount of products

**semi-continuous**variables: variables that can assume zero or a value between the constants \(\color{darkblue}L\) and \(\color{darkblue}U\). So we can write:

MIP model with semi-continuous variables |
---|

\[\begin{align} \max & \sum_i \color{darkred}x_i \cdot \color{darkblue}{\mathit{rate}}_i \\ & \sum_i \color{darkred}x_i \le \color{darkblue}{\mathit{budget}} \\ & \color{darkred}x_i \in \{0\}\cup [\color{darkblue}L_i,\color{darkblue}U_i] \end{align} \] |

MIP model with binary variables |
---|

\[\begin{align} \max & \sum_i \color{darkred}x_i \cdot \color{darkblue}{\mathit{rate}}_i \\ & \sum_i \color{darkred}x_i \le \color{darkblue}{\mathit{budget}} \\ & \color{darkblue}L_i \cdot \color{darkred}\delta_i \le \color{darkred}x_i \le \color{darkblue}U_i \cdot \color{darkred}\delta_i \\ & \color{darkred}x_i \in [\min\{0,\color{darkblue}L_i\},\max\{0,\color{darkblue}U_i\}] \\ & \color{darkred}\delta_i \in \{0,1\} \end{align} \] |

n (number of products) | solution time (seconds) |
---|---|

1,000 | 0.02 |

10,000 | 0.36 |

100,000 | 2.17 |

#### Sorting

---- 23 PARAMETERdatamin max rate i1 1.000 3.000 i2 2.000 2.000 2.000

**i1**(objective: 3). The optimal solution is to use 2 units of type

**i2**(objective 4).

#### References

- Portfolio optimization problem: improving the O(n!) solution, https://stackoverflow.com/questions/73184010/portfolio-optimization-problem-improving-the-on-solution

#### Appendix: GAMS model

$ontext $offtext *----------------------------------------------------* size of the problem*----------------------------------------------------set i 'orders' /i1*i100000/;*----------------------------------------------------* random data*----------------------------------------------------parameter data(i,*);data(i,'min') = uniformint(1,50); data(i,'max') = data(i,'min') + uniformint(1,50); data(i,'rate') = uniform(0,0.1); display$(card(i)<=50) data;*----------------------------------------------------* model*----------------------------------------------------semicont variable x(i) 'product use';x.lo(i) = data(i,'min'); x.up(i) = data(i,'max'); variable z 'objective';equationsobj budget ; obj.. z =e= sum(i, x(i)*data(i,'rate'));budget.. sum(i, x(i)) =l= 1000;model m /all/;option threads=0;solve m maximizing
z using mip;display x.l; |

Since this model allows fractional amounts for the variables, it can be solved in nlogn time by a simple greedy algorithm that sorts the items by rate in decreasing order and uses as much of possible of each item until the budget is used up. (Knapsack is only difficult because of the integer constraints.)

ReplyDeleteDon't think so. See my counter example.

Delete