0

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^S{\sum_h^H{Amount_{s, h} \cdot Used_{s, h} \cdot Price_s}} $$ st: $$ \sum_h^H{Used_{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.

Santi Peñate-Vera
  • 161
  • 10
  • Most commercial solvers have free trial licenses with no size restrictions. If you only need to solve the problem few times go for that. Otherwise look for open source solvers https://projects.coin-or.org/Bonmin or https://projects.coin-or.org/Cbc depending on whether you solve a MILP or MINLP. – AndreaCassioli May 03 '17 at 09:54
  • Have a look at https://sourceforge.net/directory/os:windows/?q=mixed+integer+nonlinear+programming%3FSetFreedomCookie – Claude Leibovici May 03 '17 at 09:56

1 Answers1

1

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,h}\cdot$ 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^S{\sum_h^H{z_{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.

YukiJ
  • 2,529