I have a discrete optimisation problem. I suspect the answer will be use some kind of combinatorial optimisation approach, but I don't have significant enough experience to determine this.
My problem is as follows:
For a given day I have 48 half hour periods for which I can sell a service, $s_n$, to a counterparty (where there are $n$ different services).
There are several different types of service, $s_n$, each service comprising a set of time periods that the service is active.
- So for example, $s_1$ is offered between the hours of 1am and 7am, then 5pm and 9pm; a total of 10 hours
- $s_2$ is offered between the hours of 1am and 7am only; a total of 6 hours
- $s_3$ is offered between the hours of 6pm and 9pm; a total of 3 hours.
It is not possible to part schedule a service. So for example, it is not possible to offer $s_1$ for the hours of 1am to 5am only.
Having delivered the service at the required periods, each $s_n$ has a specific commercial profit associated with it, with some services being more valuable then others. So in the above example, if $s_1$ has a value of 4, $s_2$ value 3, $s_3$ value 3, then the most profitable combination of services is $s_2$ and $s_3$.
There is a hard constraint in that during each period, $p$, only one service can be provided to the counterparty.
- So it's not possible to have two services concurrently between 7pm and 9pm, for example. Or for one service to run from 7pm to 9pm and another to run from 7pm to 7.30pm, concurrently.
Given a set of $s_n$ possible services, what subset maximises the total profit between the periods of 1 to 48?
I have two questions: firstly, how should I approach the formulation of this in a formal way? I have read this https://en.wikipedia.org/wiki/Optimization_problem and it's still to abstract to help me articulate the problem so that I can usefully solve it.
Secondly, any pointers as to what optimisation techniques are the best to solve this problem, would be greatly appreciated
This is called the linear assignment problem and it is not hard at all. One solution approach is https://en.wikipedia.org/wiki/Hungarian_algorithm / https://www.youtube.com/watch?v=dQDZNHwuuOY
Put the services $s_n^k$ vertically and the 48 time periods horizontally (and extra dummy columns to make the system square). Each cell has the profit in it, or $0$ if the permutation not offered at a specific time. If you solve it, every service $s_n^k$ is either assigned to one of 48 time periods, or to a dummy time period (which means it is not offered).