1
$\begingroup$

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:

  1. 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).

  2. 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.

  1. 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$.

  2. 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

$\endgroup$
  • $\begingroup$ You say there are half hour periods, so if only one service can be actively offered to the counterparty, why can a service block out others between 7pm-9pm and not just 7-7.30pm? $\endgroup$ – LinAlg Oct 12 '16 at 15:52
  • $\begingroup$ That's a valid point. I will edit my original post. Thank you $\endgroup$ – Anthony W Oct 12 '16 at 16:56
  • $\begingroup$ Ok, I've updated the question as you suggested. Hopefully that's clearer. A service earns equal amounts in each period. Once delivery starts, it cannot be stopped half way; it's all or nothing. $\endgroup$ – Anthony W Oct 13 '16 at 13:29
  • $\begingroup$ A service can be offered for all 48 periods or any variation thereafter. Each service is typically offering something different, so 3 hours of one service in the afternoon might be significantly more valuable than six hours of a different service in the morning. $\endgroup$ – Anthony W Oct 13 '16 at 13:39
  • $\begingroup$ The half hour periods are not relevant at all, are they? $\endgroup$ – LinAlg Oct 13 '16 at 13:58
1
$\begingroup$

Take $ s_{ik} $ to be the binary variable taking value $1$ if $i^{th}$ service is offered in the period $k$. So if the service $i$ can not be offered during a certain period this should take value $0$. Since only one service can be provided during any period $k$ therefore $$ s_{ik} \leq 1 - s_{jk} \hspace{1cm} \forall \hspace{0.2cm} j \neq i $$ Next to ensure that, as in example above, if the service $s_{1}$ is being offered then it has to be offered continuously during the period 1 AM to 7 PM you can have all variables $ s_{1k}$ equal for $ 1 AM < k < 7 PM$. Similarly for other services.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Can I ask if the linear assignment problem captures the dependency between a sequence of half hour periods? So if a service from 7pm to 9pm is run, all 4 half hour periods must be included, not just the most profitable service for a given individual half hour. That is, a service is represented by a sequence of half hours, and the goal is to establish that this service is more profitable than all services within the same time range. I note that the definition of the assignment problem is to minimise the the cost of assigning the j-th job to the i-th worker, which I think is different? $\endgroup$ – Anthony W Oct 13 '16 at 8:25
  • $\begingroup$ Every job (worker) will be assigned to at most one time slot (job). When you talk about "a sequence", do you mean that $s_n^2$ cannot be delivered before $s_n^1$? If the answer is "no", my solution is the correct one. $\endgroup$ – LinAlg Oct 13 '16 at 11:49
  • $\begingroup$ I think I haven't explained the problem sufficiently. I have updated the question so that hopefully it's clearer. The key thing is that services must be delivered in full for all periods for which they are specified. It is not possible to pick specific periods within different services. $\endgroup$ – Anthony W Oct 13 '16 at 13:14

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.