3
$\begingroup$

I've tried Or-Tools and MILP solvers a couple of different ways on this, but they take a surprisingly long time to realize that the solution they generated fairly quickly is in fact minimal. Is there a better way? Does this problem have a name?

Problem

Given a fixed set of meetings, their dates, start times and end times, an individual is required to attend a subset of the meetings respecting some (pseudo-)Boolean constraints (e.g., at least $k$ of a subset of $m$ meetings must be attended; if a particular meeting is attended, a selection of other meetings must be attended). In particular, the individual cannot attend two meetings at once.

Goal

Choose a set of meetings to attend that meets the Boolean constraints and minimizes the total time the individual spends both in meetings and waiting for the next meeting on the same day.

More precisely, minimize the sum of the day lengths, where the length of a day is the duration from the start of the day's earliest attended meeting to the end of the latest attended. (A solution with meetings on Monday at 9am-12pm, 3pm-5pm, and on Wednesday 10am-11am, 3pm-4pm has a total day length of 8 + 6 = 14hrs.)


To simplify, consider one day in isolation, and on it a set $M_D$ of possible meetings $\{m_1, \dots, m_n\}$, with functions $\mathrm{start_D}, \mathrm{end_D} : M_D \to \{0, 1, \dots, 24\}$, where $\mathrm{start_D}(m_i) \lt \mathrm{end_D}(m_i)$.

Assume all meeting times are unique, i.e., $\mathrm{start_D}(m_i) = \mathrm{start_D}(m_j) \implies i = j$ or $\mathrm{end_D}(m_i) \neq \mathrm{end_D}(m_j)$.

Denote by $S_D$ the solution: the (possibly empty) subset of $M_D$ chosen for that day.

Then the objective to minimize is

$$\begin{equation} \mathrm{length_D} = \begin{cases} \max_{m_i \in S_D}\{\mathrm{end_D}(m_i)\} - \min_{m_i \in S_D}\{\mathrm{start_D}(m_i)\} & \text{if $S_D$ is non-empty}\\ 0 & \text{otherwise}\\ \end{cases} \end{equation}$$

Attempt 1 (slower)

Boolean variables: $m_1, \dots, m_n, dayNotEmpty$

Integer variables: $dayLength$, $latestEnd$, $earliestStart$, $earliestStart'$

Objective: $\text{minimize $dayLength$}$

Constraints:

$$\begin{align}&\text{[... other Boolean constraints...]}\\\\ m_i + m_j &\leq 1 \text{ if $m_i$ and $m_j$'s times overlap} & \forall_{i, j}, i \neq j\\\\ dayLength &= latestEnd - earliestStart\\\\ latestEnd &\geq \mathrm{end_D}(m_i) \cdot m_i & \forall_{i} \\\\ earliestStart' &\geq 24 - \mathrm{start_D}(m_i) \cdot m_i & \forall_{i}\\ earliestStart &= (24 - earliestStart') - 24 \cdot (1 - dayNotEmpty)\\\\ (dayNotEmpty &\equiv \bigvee_i m_i)\\ dayNotEmpty &\leq \sum_i m_i\\ dayNotEmpty &\geq m_i &\forall_{i} \end{align}$$

(So that, when no meetings are in the solution, $earliestStart' = 0$ and $dayLength = 0 - ((24 - 0) - 24 \cdot 1) = 0$.)

Attempt 2 (faster)

Boolean variables: $m_1, \dots, m_n, and_{1,2}, \dots, and_{1,n}, \dots, and_{n-1, n}$

Integer variables: $dayLength$

Objective: $\text{minimize $dayLength$}$

Constraints:

$$\begin{align}&\text{[... other Boolean constraints...]}\\\\ m_i + m_j &\leq 1 \text{ if $m_i$ and $m_j$'s times overlap} &\forall_{i, j}, i \neq j\\\\ dayLength &\geq (\mathrm{end_D}(m_i) - \mathrm{start_D}(m_i)) \cdot m_i &\forall_{i}\\ dayLength &\geq (\mathrm{end_D}(m_j) - \mathrm{start_D}(m_i)) \cdot and_{i,j} &\forall_{i, j}, i \neq j, \mathrm{end_D}(m_i) \leq \mathrm{start_D}(m_j)\\\\ (and_{i,j} &\equiv m_i \wedge m_j) & \forall_{i, j}, i \neq j\\ and_{i,j} &\geq m_i + m_j - 1 &\forall_{i, j}, i \neq j \\ and_{i,j} &\leq m_i &\forall_{i, j}, i \neq j\\ and_{i,j} &\leq m_j &\forall_{i, j}, i \neq j \end{align}$$

$\endgroup$
1
  • $\begingroup$ Your problem space would fit RAM? If yes, an exact cover formulation that memorizes and trim on best partial solutions may be feasible. $\endgroup$ Dec 9, 2021 at 14:00

3 Answers 3

3
$\begingroup$

I recommend using a network formulation, as I have done for the traveling baseball fan problem. The nodes are the meetings, and the arcs represent transitions between consecutive meetings, with an arc cost that captures the additional time incurred until the end of the next meeting.

$\endgroup$
2
  • $\begingroup$ The arbitrariness of the problem's Boolean constraints probably rules out the network formulation for me. The big-M formulation of $\mathrm{min}$ in the MILP section of the linked paper is presumably elementary but already an improvement over my attempts. Thanks. $\endgroup$
    – triskett
    Dec 9, 2021 at 13:05
  • $\begingroup$ It is a side-constrained network formulation, and the side constraints can be arbitrary. $\endgroup$
    – RobPratt
    Dec 9, 2021 at 13:58
3
$\begingroup$

Another possibility might be column generation. The master problem would start with a predefined collection of feasible schedules for each day, where feasible means (a) no time conflicts and (b) satisfying any "if this meeting then that meeting" or "at least one of these meetings" constraints that involve only meetings on that day. There's a binary variable for each such schedule, and the master problem chooses schedules (one per day) to minimize the sum of their (known) durations subject to the remaining logical constraints (those that span days).

For an exact solution, you'll end up using branch and price, which is not known for its speed (but might be faster than your models ... only testing will tell). For an approximate solution, you can apply a variant of the Gilmore-Gomory heuristic for the one-dimensional cutting stock problem. You solve the LP relaxation of the initial master (which starts with a handful of "obvious" schedules), use the dual solution to calibrate the objective function of a subproblem that generates a new schedule (one that would have a negative reduced cost in the master LP), add that column, rinse and repeat. When no new columns are found, you revert the master to an integer program and solve.

Getting away from branch and price/column generation, you might also consider using a constraint programming (CP) model rather than a MIP model. Some constraint solvers are pretty good at handling scheduling models. They typically have "global" constraints for non-overlap (you can't be in two places at once), and they are adept at handling logic constraints ("if this then that", "at least one of these", "at most $k$ of these").

$\endgroup$
2
$\begingroup$

This might be a silly question, but what is the incentive to attend the meetings at all? I don't see any constraints considering that. You just want to minimize the time spent on meetings and waiting on them. Solution: do not go to any meetings :) You'd have to constrain your "Boolean constraints" in the description themselves a little. Any possible constraint that could be formulated is a bit too much to be able to say anything about how that problem could be tackled. If the boolean constraint would simply say "you have to attend meeting $m$" then the problem just gets easier, because it's one variable less - but you could formulate all sorts of stuff, so that info is not really helpful.

But let's say there was a constraint saying, that you have to attend at least $k$ meetings, then i also would suggest modelling the meetings as nodes, with arcs between them with outgoing arcs having the time the meeting took + the time it takes for the next meeting to start. Then you start from a depot and come back there, with the depot having no waiting time and/or process time itself. What you would look for then, would be the shortest tour from the depot, over the nodes, and back to the depot, with the number of visited nodes >= k. Considering the constraints, that you can only attend certain meetings, if you attended other ones (not necessarily directly after one another): you could look at the "SOP (Sequential Ordering Problem)" which is a generalization of the TSP and derive the cuts from there and only cut those off in the callback if they are actually violated.

$\endgroup$
4
  • $\begingroup$ The directed acyclic network formulation I suggested, with separate source and sink nodes, does not require subtour elimination. $\endgroup$
    – RobPratt
    Dec 8, 2021 at 15:24
  • $\begingroup$ Unfortunately, I cannot say from the outset what the Boolean constraints would look like in the future. (I've edited my post to try to give more specific examples.) But I think I can assume they could be formulated in ILP. Another issue is that the minimum day length would be just one objective in a multi-objective problem, and I assume that means formulating all the objectives as network problems, which could be a problem... $\endgroup$
    – triskett
    Dec 8, 2021 at 15:33
  • $\begingroup$ I'll be honest, i just glanced over your work on the traveling baseball fan. I'm not entirely sure though, that you can incorporate the SOP-Constraints into the network formulation - but you could probably still cut solutions that violate them as you get them so if everything else fits, that's probably a better way, since the time constraints are also being taken care of :) $\endgroup$
    – azaryc2s
    Dec 8, 2021 at 15:43
  • $\begingroup$ @triskett: Well if you do not know how generalized the problem could become, it's hard - if not impossible - to map it to another already well studied problem. You might need to "go with the flow" as the constraints come in. Another approach would be: restrain the main problem to the core characteristics (time-windowed schedule) and the very restrictive constraints and cut off otherwise invalid solutions as they come in a callback function (sort of a benders decomposition). Chances are, that those "niche" constraints won't even be violated. $\endgroup$
    – azaryc2s
    Dec 8, 2021 at 15:56

Your Answer

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

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