# How to Group IDs Based on the Difference of Each ID’s Min and Max Value?

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!

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 where $$m_i$$ and $$M_i$$ are the min and max, respectively, for id $$i$$.
• 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$?
• @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. Commented Jan 26 at 19:05