Simultaneously maximize and minimize

Question

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!

Answer 1

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.