Vtyjkyuk

I have a problem in which I need to allocate an amount of a service and each allocation consumes time.

The mathematical formulation would be something like:

$$
min: f=sum_s^Ssum_h^HAmount_s, h cdot Used_s, h cdot Price_s
$$
st:
$$
sum_h^HUsed_s, h cdot Time_s leq Max_usage_time_s quad forall s in S
$$

$Used_s, h$ is a integer variable that determines if the service $s$ is used in the hour $h$.

$Amount_s, h$ is the amount of service $s$ used in the hour $h$.

In the ideal situation, this problem requires the use of a Non-Linear Mixed Integer programming library.

However I don't have the budget to spend in Gurobi or alike to solve this.

Hence, which are reasonable methods that can be used for this problem instead of MINLP?

And if you know of open source implementations better.

I assume that the variable Used$_s,h$ is binary and determines if the service $s$ is used in hour $h$ if Used$_s,h=1$ and Used$_s,h=0$ otherwise.

If you have an upper bound to the variable Amount$_s,h$ then you can linearize the expression Amount$_s,hcdot$ Used$_s,h$ in the objective function to turn your problem into an LP which you can then solve with an ordinary LP-solver (by the cost of introducing additional variables).

In order to linearize the expression, let $A$ denote the upper bound to Amount$_s,h$ for all $s$ and $h$. Then you introduce a new variable $z_s,h$ and add the following constraints:

$$z_s,h leq A cdot Used_s,h$$
$$z_s,h leq Amount_s,h$$
$$z_s,h geq Amount_s,h - (1-Used_s,h)A $$
$$z_s,h geq 0$$

As objective function you now minimize

$$min: f=sum_s^Ssum_h^Hz_s, h cdot Price_s$$
If $Used_s,h=0$ for a given pair $(s,h)$, it follows from the first and fourth constraint that $z_s,h=0$. If $Used_s,h=1$, then constraints number 2 and 3 will force $z_s,h= Amount_s,h$.

Hence, you now have a linear model.