Need help to add a constraint to a MIP model in R

Question

I'm trying to build a model to optimize steel production. The objective is to reduce the amount of waste (leftover material after the steel has been cut). The code below is what I have so far. It is lacking a constraint to make sure that each item in work_tbl is fulfilled from a single item in inventory_tbl (but several items from work_tbl can be fulfilled by one item in inventory_tbl, given that there is enough length available).

code/reproducible example:

# Load required packages
library(dplyr)
library(ompr)
library(ompr.roi)
library(ROI)


# Define the problem data
work_tbl <- data.frame(length = c(2500, 500, 700, 1200, 1500, 2000, 2500, 3000, 4000, 5250))
inventory_tbl <-
  data.frame(length = c(1300, 2000, 1800, 2600, 3000, 2000, 5000, 6000, 7000, 9000, 2000, 500, 4000, 12000, 7400, 13000))

# Define variables to be used 

work_count <- nrow(work_tbl)
invent_count <- nrow(inventory_tbl)
big_M <- sum(work_tbl$length) * 1.1

# Initialize the model

steel_model <- ompr::MIPModel() %>% 
  
  # Binary decision variable - steel to be cut
  add_variable(steel_cut[work, inventory],
               work = 1:work_count,
               inventory = 1:invent_count,
               type = "binary") %>% 
  
  # Binary decision variable: Take new item from inventory?
  add_variable(take_item[inventory],
               inventory = 1:invent_count,
               type = "binary") %>% 
  
  # Constraint 1: Each item in work_tbl must be cut
  add_constraint(sum_over(steel_cut[work, inventory],
                          inventory = 1:invent_count) == 1,
                 work = 1:work_count)  %>% 
  
  # Constraint 2: The sum of each item used to cut from needs to be equal to or smaller than the work item
  add_constraint(sum_over(steel_cut[work, inventory] * work_tbl$length[work],
                          work = 1:work_count) <= inventory_tbl$length[inventory],
                 inventory = 1:invent_count, work = 1:work_count) %>% 
  
  # Constraint 3: big_M constraint to activate take_item whenever a length is cut
  add_constraint(
    sum_over(steel_cut[work, inventory],
             work = 1:work_count) <= big_M * take_item[inventory],
    inventory = 1:invent_count
  ) %>% 
  
  # Set objective function to minimize scrap / waste 
  set_objective(
    sum_over(
      take_item[inventory] * inventory_tbl$length[inventory],
      inventory = 1:invent_count
    ) - sum_over(steel_cut[work, inventory] * work_tbl$length[work],
                 work = 1:work_count,
                 inventory = 1:invent_count), sense = "min"
  )

# View the model
steel_model

# Solve the model

solution <- ompr::solve_model(steel_model, with_ROI(solver = "glpk", verbose = TRUE))  

# Check objective value
solution$objective_value

# Get the solution 
steel_model_soln <-
  ompr::get_solution(solution, steel_cut[work, inventory]) %>% filter(value > 0) %>% 
  mutate(cut_length = work_tbl$length[work])

# View the solution
steel_model_soln

Answer 1

My r syntax is pretty rusty, but... Your model is close. Why don't you:

1. Change cut_order to a binary variable, indicating that you are cutting work from inventory.

2. 'take_item' looks good as a binary also...leave it.

3. Change constraint 1 to a loop because you need a "for each work item".... You need a summation constraint for each item in work. It is minimization, so don't fret the >=. In pseudocode:

for each work:
    add_constraint(sum(cut_order[work, inventory] over inventory) >= 1)

4. change constraint 2 to loop over each inventory to again create a constraint "for each" inventory piece and multiply the selection variable by the work length in the constraint

for each inventory:
    add_constraint(sum(cut_order[work, inventory]*work_length[work]) <= inventory_length[inventory])

5. Constraint 3 looks good

6. Change your objective to accumulate the scrap...

sum(take_item[inventory]*inventory_length[inventory] - sum(cut_order[work, inventory]*work_length[work] over work) over inventory)

Another alternative that you might consider is just minimizing(take_item) to use the minimal number of sticks consumed, or penalizing slightly with a weight the use of longer sticks, to help consume the short stuff first, etc. All that is gravy after you get the model breathing...

Edit: An (untested) stab at the r code:

# Load libraries

# Load required packages
library(dplyr)
library(ompr)
library(ompr.roi)
library(ROI)


# Define the problem data
work_tbl <- data.frame(length = c(2500, 500, 700))
inventory_tbl <-
  data.frame(length = c(1300, 2000, 1800, 2600, 3000))

work_count <- nrow(work_tbl)
invent_count <- nrow(inventory_tbl)
big_M <- (work_tbl$length) * 1.1

# initialize the model

steel_model <- ompr::MIPModel() %>% 
  
  # How much steel to be cut for each item
  add_variable(steel_cut[work, inventory],
               work = 1:work_count,
               inventory = 1:invent_count,
               type = "binary") %>% 
  
  # Take new item from inventory?
  add_variable(take_item[inventory],
               inventory = 1:invent_count,
               type = "binary") %>% 
  
  # Constraint 1: each work item must be fulfilled
  # You need to make a sum over all work FOR EACH inventory item, so inventory should be outside the sum
  add_constraint(sum_over(steel_cut[work, inventory], inventory = 1:invent_count ) == 1,
                work = 1:work_count)  %>% 
  
  # Constraint 2: for each item, ensure lengths cut is less than or equal to length of item
  # Again, here the summation of stuff used is compared to EACH inventory item, so that
  # needs to be outside the summation, but WORK is alread summed inside and should not be included...
  # you are basically saying, for each inventory item, sum up all of the work assigned to it and compare it
  # to the length of that inventory item
  add_constraint(sum_over(steel_cut[work, inventory] * work_tbl$length[work], work = 1:work_count) <= inventory_tbl$length[inventory],
                inventory = 1:invent_count) %>% 

  
  # Constraint 3: big_M to activate take_item whenever a length is cut
  add_constraint(sum_over(steel_cut[work, inventory], work = 1:work_count) <= big_M * take_item[inventory],
                inventory = 1:invent_count) %>% 
  
  # needed to multiply the steel_cut selection variable by the length of the work
  set_objective(sum_over(take_item[inventory] * inventory_tbl$length[inventory], inventory = 1:invent_count) 
              - sum_over(steel_cut[work, inventory] * work_tbl$length[work], work = 1:work_count, inventory = 1:invent_count), sense = "min")

steel_model

solution <- ompr::solve_model(steel_model, with_ROI(solver = "glpk", verbose = TRUE))  

solution$objective_value

steel_model_soln <-
  ompr::get_solution(solution, steel_cut[work, inventory]) %>% filter(value > 0)