2
$\begingroup$

I have a dataset that contains IDs along with their corresponding minimum and maximum values.

Here’s a sample of the data:

id    min_value max_value
   <fct>     <int>     <int>
   1             1         6
   2             8        12
   3            15        19
   4            22        27
   5            32        36
   6            39        43
   7            45        49
   8            51        56
   9            57        60
   10           63        66

My goal is to group these IDs based on two conditions:

  1. For a given group, the difference between the minimum and maximum values of group IDs should exceed a certain threshold.
  2. Even if two IDs satisfy the first condition, they cannot be in the same group if the difference between their min and max values falls within the same multiple of a given integer.

To illustrate with an example:

For instance, let’s say the threshold is 7, and the given integer is 24. IDs 1 and 3 could be grouped together based on the first condition because the difference between their values (15-6) is 9, which is greater than 7. However, according to the second condition, they cannot be grouped together because both are less than 24. It will go on similarly for the other multiples of 24. Say if there are two values such as 32 & 41 etc., they can't be in the same group.

Only keeping the difference 24 is also not logical. Because, then say 22 and 33 can't be grouped.

I have successfully written down the 1st constraint. But struggling to accommodate the 2nd.

Here is a sample code in R:

library(ompr)
library(ompr.roi)
library(ROI.plugin.glpk)
diff <- 36

#dummy data
structure(list(id = structure(1:25, levels = c("1", "2", "3", 
"4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", 
"16", "17", "18", "19", "20", "21", "22", "23", "24", "25"), class = "factor"), 
    min_value = c(1L, 8L, 15L, 22L, 32L, 39L, 45L, 51L, 57L, 
    63L, 70L, 80L, 87L, 93L, 99L, 105L, 111L, 117L, 123L, 129L, 
    135L, 142L, 152L, 159L, 165L), max_value = c(6L, 12L, 19L, 
    27L, 36L, 43L, 49L, 56L, 60L, 66L, 75L, 84L, 91L, 98L, 104L, 
    108L, 114L, 121L, 128L, 132L, 139L, 147L, 156L, 162L, 166L
    )), class = c("tbl_df", "tbl", "data.frame"), row.names = c(NA, 
-25L))-> slot_id_min_max


nrow(slot_id_min_max)-> number_of_groups

# Define the model
model <- MIPModel() %>%
  # Binary variable x[i,j], 1 if id i is in group j
  add_variable(x[i, j], i = 1:number_of_groups, j = 1:number_of_groups, type = "binary") %>%
  # Each id must be in exactly one group
  add_constraint(sum_expr(x[i, j], j = 1:number_of_groups) == 1, i = 1:number_of_groups)

# Constraint: no two element ids in the same group can have a max min difference less than 'diff'

for (i in 1:(number_of_groups - 1)) {
  for (j in (i + 1):number_of_groups) {
    if ((slot_id_min_max$min_value[j] - slot_id_min_max$max_value[i] < diff)) {
      model <- model %>%
        add_constraint(x[i, g] + x[j, g] <= 1, g = 1:number_of_groups)
    }
  }
}


# Objective: minimize the number of groups
model <- model %>%
  set_objective(sum_expr(x[i, j], i = 1:number_of_groups, j = 1:number_of_groups), "min")

# Solve the model
result <- solve_model(model, with_ROI(solver = "glpk", verbose = TRUE))

# Get the solution
batch_merging_solution <- result %>% get_solution(x[i, j]) %>% filter(value>0)

print(batch_merging_solution)

Any help or nudge is appreciated!

$\endgroup$

1 Answer 1

3
$\begingroup$

Sounds like shift scheduling, where each id is a shift with start time equal to the min value and end time equal to the max value. Your first condition requires at least a certain amount of rest between shifts. Your second condition prevents more than one shift on the same day, and you can enforce it by imposing $$x_{ig} + x_{jg} \le 1 \quad \text{for all $g$ and all $i<j$ such that $\lfloor M_i/24 \rfloor = \lfloor m_j/24 \rfloor$},$$ where $m_i$ and $M_i$ are the min and max, respectively, for id $i$.

$\endgroup$
4
  • $\begingroup$ Should the last expression be looking at $\lfloor (M_i - m_i )/24\rfloor$ (and similarly for $j$) where $m_i$ and $M_i$ are the min respectively max for ID $i$? $\endgroup$
    – prubin
    Commented Jan 26 at 18:58
  • $\begingroup$ @prubin Yes, I have corrected my answer to use the min and max values, but I think the intent is that $M_i$ and $m_j$ should not be in the same day. $\endgroup$
    – RobPratt
    Commented Jan 26 at 19:05
  • $\begingroup$ That would make more sense. $\endgroup$
    – prubin
    Commented Jan 27 at 4:07
  • $\begingroup$ Thank you! Yes, it is related to scheduling. $\endgroup$ Commented Jan 29 at 4: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.