2
$\begingroup$

I am virtually new to optimization (saw it years ago in a very shallow course) and now I came across a problem that I believe would require from it. The problem is I don't know exactly how to proceed.

The problem is as follows: Subject to some constrains I want to minimize a function $f(t) = c(t) * g(t)$, where $c(t)$ and $g(t)$ are functions that vary over time. At the same time I want to maximise another function $h(t)$. Moreover, there are some constraints but I don't think that is much of a problem.

In summary, I have two problems (1) to simultaneously minimize one function and maximise another one, and (2) one of the functions depend on the multiplication of other functions.

How should I proceed with this?

Thanks and sorry if this is too basic.

_________________ Edit _________________

I want to minimize the cost of using a service (e.g., CPU time in a Cloud computing service provider). The cost $c$ of the service depends on the demand of this service so I don't know in advance (but we can assume if follows a probability distribution based on previous observations). If at a particular time slot $t$ I use $x$ units of that service (say CPU cycles) that would cost me $x*c$, whatever is the value of $c$ at that particular time.

Nonetheless, I can decide not to use that service at some points in time to reduce the cost because I can get CPU cycles from my own computer or another computer. So, if I am not mistaken, the function I want to minimise would be:

$$ f(x, m, a) = x*c - (m + a) *c$$

Being $m$ and $a$ the number of CPU cycles I get from my own computer and from another computers. So if $f(x,m,a)$ is positive I would end up paying while if negative I am saving money.

Moreover, there are some restrictions. There is a given amount of CPU cycles that I need at every time period to fulfil my task. Again, as with the cost, this is dependent on time but I cannot know in advance (but I could somehow predict or consider it follows some probability distribution).

For now I have simplified the problem not to consider the other function that I need to simultaneously maximise. This is is just to make things easier and clearer.

Do you think the formulation of the problem is correct? Would you formulated it differently? If this is not the case, how do I deal with these variables that vary over time?

Sorry for my poor exposition before!

$\endgroup$
  • $\begingroup$ are $f$,$c$,$g$,$h$ only functions of time $t$? Are you optimizing only wrt to time? $\endgroup$ – Anton Menshov Jun 27 at 6:52
  • $\begingroup$ Well, actually not. I want to minimise the total value of f(t) while maximising the total value of h(t) for a period of time. So maybe I should've express it as the summation $\sum_{t=0}^{t=n} f(t)$ and similar for h(t). $\endgroup$ – rutex Jun 27 at 7:27
  • $\begingroup$ Still, I do not get it entirely. In order to do that, I think $f$ should be at least a function of something else (say, for example, $f(x,y,z,t)$). $\endgroup$ – Anton Menshov Jun 27 at 7:30
  • $\begingroup$ Probably it is not expressed in a good mathematical form because I am not very good at math. To give more details $c(t)$ is a value that varies with time and $g(t)$ is another value that varies with time but their values are given to me by a programming API (there is not an actual function that I know of). I guess this can be seen as random variables given by some sort of probability distribution $\endgroup$ – rutex Jun 27 at 7:42
  • $\begingroup$ Ok. That makes more sense. However, what are you optimizing with respect to? You have a function of time which you "integrate". Now, the "answer" from the optimizer is usually an "optimal" set of parameters that lead to maximization\minimization of the function. What is the output you expect to see from the optimizer? $\endgroup$ – Anton Menshov Jun 27 at 17:36
1
$\begingroup$

In a more general sense, you could formulate your problem as follows. Suppose you have a number of resources, i.e. places where you can find CPU clicks (I use clicks but depending on your granularity this could be hours, days, months). Number these resources $i=1, 2, \ldots$. All these resources have a price to pay. As you indicate in your post, these prices might vary in time. So write these costs as $c_i(t)$. The variables you want to optimize are when to use which resource, call them $x_i(t)$ where $x_i(t) \equiv 1$ when you use resource $i$ at time $t$ and $x_i(t)\equiv0$ if you don't use it. This leads to a cost function $$C(t) = x_1(t)\cdot c_1(t) + x_2(t)\cdot c_2(t)+\ldots x_N(t)\cdot c_N(t) = \sum_{i=1}^{N} x_i(t)\cdot c_i(t),$$ i.e. this is what you are paying at time $t$.

In the end, you are interested in your total cost: $$TC = \int_0^{T} C(t)dt$$ where $T$ is your total simulation time. This is what you want to minimize. But clearly, you need to get some work done. So you will have a constraint that you need to satisfy: the sum over all resources of the integral CPU time needs to be larger than a certain value, call that $CPU$. This can be written as $$\sum_{i=1}^{N} \int_{0}^{T} x_i(t) dt \geq CPU.$$

Another option could be that the $x$ represent certain resources and they can be used at a certain rate (for example, you reserve capacity but you don't use it always at its fullest). Then the $x_i$ represent the total CPU time for a certain resource and $c_i$ the proportional cost for that resource. This approach makes the $x_i$ continuous functions instead of Booleans.

The problem now is that you have continuous functions of time, integrals and so on. You could transform this problem into a linear programming problem by discretizing your time variable up to a certain granularity (for example hours). The continuous time $t$ is split in certain intervals $[t_j, t_{j+1}], j \geq 0$. So instead of $x_i(t)$ (am I using resource $i$ at time $t$), you work with $x_{i,j}$ where $x_{i,j} \equiv 1$ if you use resource $i$ in the time interval $[t_j, t_{j+1}]$. If you do the same with your cost function $c_{i}(t)$, you will see that the total cost $TC$ becomes a linear function of a (huge) number of $x_{i,j}$, each with a cost $c_{i,j}$ associated with it. This results in a massive linear programming problem that can be solved with open-source tools like GLPK or lp_solve or commercial tools.

Note that all of the above implies that your computational problems can be put on hold and restarted (i.e. you need a total of CPU time over a certain period, but not continuously). If you need to take into account that once a job is launched, it needs to finish, things get more complicated. For instance, I would assume that in this case, the price would be fixed at the time a certain job was launched. In this case, your problem becomes a kind of knapsack problem: you have a certain number of jobs, each with a cost, and a knapsack that can hold only so much jobs (a certain amount of money). What is the optimal loading of the knapsack (what jobs should be run)? So you would need knapsack items "job $i$ is launched at time $t_j$ at a cost $c_{j}$" but you would need to again to consider a large number of these (all possible combinations of jobs and starting times, i.e. costs) and then run the knapsack problem on all these. And this is computationally hard since the knapsack problem is a combinatorial problem so you'll quickly run into the curse of dimensionality.

$\endgroup$
  • $\begingroup$ Thanks for your contribution @gertvde! So if I understood correctly the problem could be formulated as: $$min \sum_{j=1}^{T} C(t) = \sum_{j=1}^{T}\sum_{i=1}^{N} x_{ij}(t)c_{ij}(t)$$ subject to: $$x_{ij} \in {0,1}$$ $$\sum_{j=1}^{T}\sum_{i=1}^{N} x_{ij} \geq CPU$$ I guess this works if at every time period I know in advance the amount of CPU cycles I need but what if I don't have that information? I may know on average the amount of CPU I need after $T$ periods but assume I cannot withhold tasks for too long. Similarly, for the price (but this is not a big issue since variance is very low). $\endgroup$ – rutex Jul 4 at 8:47
  • $\begingroup$ Yes. Another variant could be where you assume the resources to be available for a certain amount of their capacity. Updated my answer. But you cannot optimize for something you don't know... If you don't know how much CPU time you are going to need, it's going to be hard. The aim of the game is to try to translate your wording into equations. And if that is hard, then the optimisation process will be as well. And the conclusions you can draw from its results will be shaky... $\endgroup$ – GertVdE Jul 4 at 11:52
  • $\begingroup$ thanks again for your input @gertvde . Are you aware of robust optimization problems and more precisely stochastic programming? I think that's what I am looking for but not really sure how to express the problem mathematically and what tools may I use to solve it. If you have any ideas they are most welcome! $\endgroup$ – rutex Jul 4 at 14:28
  • $\begingroup$ no sorry, stochastic optimisation is not my field... I was hoping that @ArnoldNeumaier would pick up this question. But again, first focus on a correct translation of your problem into mathematical equations, then analyze those equations (and see what "problem class" they belong to) and only then select the tools to solve your problem... $\endgroup$ – GertVdE Jul 4 at 14:39
  • $\begingroup$ Once more, thank you for your time and effort in shedding some light into the problem! Hopefully @ArnoldNeumaier shows up :-) $\endgroup$ – rutex Jul 4 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.