How to force minimum number of groups in linear programming problem using ompr

Question

The following problem seeks to maximize the weight across any 3 items while being under a cost of 20. I gave group "a" a large weight so that the model will only select the 3 items from group "a". How do I force the model to include at least 2 groups?

library(ompr)
library(ROI.plugin.glpk)
library(ompr.roi)
library(dplyr)

set.seed(1)
d <- data.frame(
  id = seq_len(10),
  weight = c(rep(100, 3), runif(7, 1, 50)),
  cost = runif(10, 1, 10),
  group = c(rep("a", 3), rep("b", 3), rep("c", 3), "d")
)

m <- ompr::MIPModel() %>%
  
  ompr::add_variable(x[i],
                     i = d$id,
                     type = "binary") %>%
  
  # set objective to maximize the weight
  ompr::set_objective(
    ompr::sum_over(d$weight[i] * x[i],
                   i = d$id), "max"
  ) %>%
  
  # cost must be less than 20
  ompr::add_constraint(
    ompr::sum_over(d$cost[i] * x[i],
                   i = d$id) <= 20
  ) %>% 
  
  # can only include 3 items
  ompr::add_constraint(
    ompr::sum_over(
      x[i],
      i = d$id
    ) == 3
  )

res <- ompr::solve_model(m, ompr.roi::with_ROI(solver = "glpk"))

res %>%
  ompr::get_solution(x[i]) %>% 
  dplyr::filter(.data$value > 0) %>% 
  dplyr::inner_join(d, by = c("i" = "id"))
#>   variable i value weight     cost group
#> 1        x 1     1    100 6.947180     a
#> 2        x 2     1    100 6.662026     a
#> 3        x 3     1    100 1.556076     a

^{Created on 2023-02-05 with reprex v2.0.2}

Giovanni Colitti · Accepted Answer · 2023-02-07T01:56:08.863

Here is one way to do it:

library(ompr)
library(ROI.plugin.glpk)
library(ompr.roi)
library(dplyr)

set.seed(1)
d <- data.frame(
  id = seq_len(10),
  weight = c(rep(100, 3), runif(7, 1, 50)),
  cost = runif(10, 1, 10),
  group = c(rep("a", 3), rep("b", 3), rep("c", 3), "d")
)

m <- ompr::MIPModel() %>%
  
  ompr::add_variable(x[i],
                     i = d$id,
                     type = "binary") %>%
  
  ompr::add_variable(group[j],
                     j = unique(d$group),
                     type = "binary") %>%
  
  # set objective to maximize the weight
  ompr::set_objective(
    ompr::sum_over(d$weight[i] * x[i],
                   i = d$id, j = unique(d$group)), "max"
  ) %>%
  
  # cost must be less than 20
  ompr::add_constraint(
    ompr::sum_over(d$cost[i] * x[i],
                   i = d$id) <= 20
  ) %>% 
  
  # can only include 3 items
  ompr::add_constraint(
    ompr::sum_over(
      x[i],
      i = d$id
    ) == 3
  ) %>% 
  
  # force group binary variables to be 1 if item is in group
  ompr::add_constraint(
    ompr::sum_over(
      x[i],
      i = d$id[which(d$group == j)]
    ) - 10000 * group[j] <= 0,
    j = unique(d$group)
  ) %>% 
  
  # force at least one binary variable for item inclusion to be 1 across all items in group
  # if group binary is 1
  ompr::add_constraint(
    group[j] - 10000 * ompr::sum_over(
      x[i],
      i = d$id[which(d$group == j)]
    )  <= 0,
    j = unique(d$group)
  ) %>%
  
  # force at least two groups
  ompr::add_constraint(
    ompr::sum_over(
      group[j],
      j = unique(d$group)
    ) >= 2
  )

res <- ompr::solve_model(m, ompr.roi::with_ROI(solver = "glpk"))

res %>%
  ompr::get_solution(x[i]) %>% 
  dplyr::filter(.data$value > 0) %>% 
  dplyr::inner_join(d, by = c("i" = "id"))
#>   variable  i value    weight     cost group
#> 1        x  1     1 100.00000 6.947180     a
#> 2        x  3     1 100.00000 1.556076     a
#> 3        x 10     1  47.28909 7.458567     d

^{Created on 2023-02-05 with reprex v2.0.2}

The key is to link group[j] variables to the decision variables, x[i], by setting constraints such that if any x[i] inside group[j] is 1 then group[j] is 1. And when group[j] is one, then at least one x[i] in that group must also be 1. Then it's straightforward to set another constraint that the sum of group[j] is greater than or equal to 2.

How to force minimum number of groups in linear programming problem using ompr

1 Answers1