0
$\begingroup$

I have an optimisation problem to solve but I can't model it correctly. Any insight is welcome :)

It has been a few years since my optimisation classes in university, and while I have forgotten a lot of tricks, I remember some others.

The Problem:

I have a set of resources and each resource has a set of associated availabilities (times during which they are available).

Domain constraints:

  1. The value of a resource may vary over time (values are non-negative and constant over a certain time interval).
  2. Bookings may not overlap except for start/end time-point (in case a booking $p_1=[p^s_1,p^e_1]$ and a booking $p_2=[p^s_2,p^e_2]$ are on the same resource and $e_1=b_2$, they will be combined into a single booking $p'_1=[p^s_1,p^e_2]$ in a post-processing step, but there can never be 2 bookings $p_1, p_2$ with $p^s_1 < p^s_2 < p^e_1$).
  3. A booking may not be shorter than a fixed threshold.
  4. I have a maximum time budget to use over all bookings.
  5. A booking can only cover a single resource.

I want to book time on the resources in a way as to optimise the total value. I am aware that this has to be transformed into an equivalent minimisation function for most solvers, but that is easy.

We can assume that the time interval we optimise over always starts with an availability.

Example:

enter image description here

The following chart shows the value per hour of each segment in brackets (e.g. for segment v2,1, the value of selecting the complete segment would be 5, since the segment is only 30 minutes long, but we are not interested in selecting segments but time intervals, so showing the value per hour seems to make more sense).

Let the "minimum time per booking" (3) be 1h, the "maximum total booking time"(4) be 4h and the availability values as displayed below,

enter image description here

then the section values above lead to the optimum selection (in red) below:

enter image description here

In addition to the 3 red bookings above which are clearly optimal (selecting v2,1 and a portion of v2,2 instead of book2 would only), result in a total value of 10/2 + 5/2 = 7.5 instead of 9 for selecting v3,2; also note the "no overlap" constraint (2) which prevents us from selecting both v2,1 and v3,2), and we are free to choose a forth booking of 1h length in either section v1,2 or v2,2 or to extend book1 by 1 hour to obtain an optimal solution.

My attempts so far:

I do not know in advance how many bookings are required for an optimal solution, but we can easily determine an upper limit by dividing the maximum booking time (4) by the minimum booking duration (3): $n^b$ = floor(max_booking_time / min time per booking); so in our example $n_b = 4$.

I chose to model a booking "i" through 2 variables $p^s_i$ (booking i start) and $p^s_i$ (booking i end) which are bounded by $[0, \max_{j=1..n_a}{v^e_j}]$ which would be $0 \leq p^s_i, p^e_i \leq 12$ in our example. This leads to the following set of model constraints:

(A1) $\sum_{i=1}^{nb} p^e_i - p^s_i \leq \text{max_booking_time}$ "maximum budget constraint (4)"

(A2) $\forall i \in \{1..n^b\}: p^s_i \leq p^s_i$ "start before end constraint"

(A3) $\forall i \in \{1..n^b - 1\}: p^e_i \leq p^s_{i+1}$ "no overlap constraint (2)"

(A4) $\forall i \in \{1..n^b\}: p^e_i > 0 \Rightarrow p^e_i - p^s_i > 1$ "minimum duration constraint (3)" enabled by (a2) and (A3).

In addition, I introduce a set of decision variables $x^j_i \in \{0, 1\}$ defining which availability $j$ a booking $i$ belongs to; let $n_a$ denote the number of availabilities:

(E1) $\forall i \in \{1..n^b\}: \sum_{j=1}^{n_a} x^j_i = 1$ "bookings cannot overlap resources constraint (5)"

(A5) $\forall i \in \{1..n^b\} \forall j \in \{1..n^a\}: x_i^j = 1 \Rightarrow p^e_i \leq v^e_j$ where $v^e_j$ denotes the end of visibility $j$

(A6) $\forall i \in \{1..n^b\} \forall j \in \{1..n^a\}: x_i^j = 1 \Rightarrow v^s_j \leq p^s_i$ where $v^s_j$ denotes the start of visibility $j$

I believe that the constraints actually reflect my use-case's constraints and as far as I remember, implications can be expressed using decision variables.

The above said, I have difficulties defining the objective function.

One attempt is to use $$\max \sum_{i=1}^{n_b} \sum_{j=1}^{n_a} x_i^j (f_j(p^e_i) - f_j(p^s_i))$$ where $f_j(t)$ is a monotonous, continuous function describing the accumulated value of availability $j$ up to time $t$; the multiplication with $x_i^j$ is necessary to avoid double-scoring for overlapping availabilities (e.g. v2,1 and v3,2 in our example). In our example, we would define \begin{equation} f_2(t) = \begin{cases} 0 &\text{ for } t \leq 5 \\ 10 (t-5) &\text{ for } 5 \leq t \leq 5.5 \\ 5 + 5 (t-5.5) &\text{ for } 5.5 \leq t \leq 10 \\ 27.5 &\text{ for } 10 \leq t \end{cases} \end{equation} However, the objective function is definitely not linear and I am not sure how to define $f_j$ to a (Python) solver.

Question:

  1. Can the objective function above be expressed as a linear function or an equivalent linear objective function be defined ?
  2. If not, is there a more elegant way to model the problem, e.g. by modifying/adding constraints but simplifying the objective function ?

I thank you all in advance for your insights and help :) Edit 1: Corrected (E1) missing $x^j_i$ variables in sum.

$\endgroup$
8
  • $\begingroup$ or.stackexchange.com/search?q=%22piecewise+linear%22 $\endgroup$
    – RobPratt
    Commented Mar 30, 2023 at 14:46
  • $\begingroup$ You mentioned a time budget. Does this mean the sum of all booking durations cannot exceed the time budget? Also, do you have a fixed set of things (tasks, clients, ...) that need to be booked, each with a given duration, or can you book things arbitrarily (including double-booking with the same start/end) as long as you satisfy the time budget and the min/max booking duration limits? $\endgroup$
    – prubin
    Commented Mar 30, 2023 at 15:37
  • $\begingroup$ @prubin: 1. Yes, the sum of all booking durations cannot exceed a fixed maximum, constraint (A1). 2. No, the set of things to be booked is variable/for me to decide and there is a minimum duration per booking which needs to be respected. Bookings on different resources cannot overlap, but can be "back-to-back" (i.e. $p^e_i = p^s_{i+1}$. $\endgroup$
    – Roegel
    Commented Mar 31, 2023 at 6:39
  • $\begingroup$ @RobPratt: Thank you as well for the link. Some reading (and detours) lead me to gurobi.com/documentation/9.5/refman/cpp_model_setpwlobj.html which seems worth a try from a first look. $\endgroup$
    – Roegel
    Commented Mar 31, 2023 at 7:01
  • $\begingroup$ You said "in case 2 bookings of the same resource share a start and end time, they will be combined into a single booking". Suppose you double booked v2,1. Would the objective contribution be 10 (the same as a single booking) or 20? $\endgroup$
    – prubin
    Commented Mar 31, 2023 at 16:22

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.