A model with semi-continuous variables

In [1], a selection problem is posted, that turns out to be an easy MIP. The problem is:

From a (large) collection of products select those products with the highest unit return (or value) subject to:

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

This can be modeled using so-called 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} \]

We can simulate semi-continuous behavior with binary variables:

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} \]

The poster asked for a polynomial algorithm. This model, like other non-trivial MIP models, has exponential complexity. However, even if worst-case behavior has exponential run times, this does not say anything about the performance of the actual model under consideration. This is often not taught properly (or maybe just misunderstood by students).

Here are some performance figures using a model with random data:

n (number of products)	solution time (seconds)
1,000	0.02
10,000	0.36
100,000	2.17

This is great performance. Not so easy to beat, even with a polynomial algorithm (if that exists).

Sorting

Is sorting an alternative? Just sort the data on the rate and parcel out from the orders with the largest value. See the comments for this suggested approach. This seems true at first sight. However, we have lower bounds to deal with, which makes the problem non-convex. 

A counter-example can look like:

----     23 PARAMETER data  

           min         max        rate

i1                   1.000       3.000
i2       2.000       2.000       2.000

Assume we have a budget of 2. Then the sorting approach would use 1 unit of type i1 (objective: 3). The optimal solution is to use 2 units of type i2 (objective 4).

References

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

Appendix: GAMS model

$ontext    See: https://stackoverflow.com/questions/73184010/portfolio-optimization-problem-improving-the-on-solution $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'; equations    obj    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;