Optimizing Warehouse Space with Constraint Programming: Reducing Compute Time

[Luís Santos]

Hi,

This code above models and solves a warehouse space optimization problem using constraint programming. It aims to minimize the unused width in the warehouses by efficiently assigning orders to warehouses while respecting their capacities. The results are then printed, showing how the orders are distributed among the warehouses and the total unused width.

However, when I add more warehouse widths, the computation time increases significantly, and I don’t understand why. Can someone give me some tips on how to reduce the computation time?

This is the code I'm using:

# Importing the OR-Tools library

from ortools.sat.python import cp_model

def optimize_warehouse_usage(warehouse_widths, orders):

model = cp_model.CpModel() # Creates an instance of the constraint programming model

num_orders = len(orders) # Number of orders

num_warehouse_types = len(warehouse_widths) # Number of warehouse types

max_warehouses = num_orders # Upper limit for the number of warehouses needed

# Variables

used = [[[model.NewBoolVar(f'used_{o}_{t}_{w}') for w in range(max_warehouses)] for t in range(num_warehouse_types)] for o in range(num_orders)]

# Creates boolean variables used[o][t][w] indicating if order o is in warehouse w of type t

warehouse_used = [[model.NewBoolVar(f'warehouse_used_{t}_{w}') for w in range(max_warehouses)] for t in range(num_warehouse_types)]

# Creates boolean variables warehouse_used[t][w] indicating if warehouse w of type t is used

total_order_width = model.NewIntVar(0, sum(warehouse_widths) * num_orders, 'total_order_width')

# Variable for the total width used

# Constraints

for o in range(num_orders):

model.Add(sum(used[o][t][w] for t in range(num_warehouse_types) for w in range(max_warehouses)) == 1)

# Each order must be placed in exactly one warehouse

for t in range(num_warehouse_types):

for w in range(max_warehouses):

model.Add(sum(used[o][t][w] * orders[o][1] for o in range(num_orders)) <= warehouse_widths[t])

# Warehouse capacity constraints

for t in range(num_warehouse_types):

for w in range(max_warehouses):

for o in range(num_orders):

model.Add(used[o][t][w] <= warehouse_used[t][w])

# Link the use of a warehouse to the use of the orders

total_order_area = sum(used[o][t][w] * orders[o][1] for o in range(num_orders) for t in range(num_warehouse_types) for w in range(max_warehouses))

model.Add(total_order_width == total_order_area)

# Calculate the total width used by the orders

total_warehouse_area = sum(warehouse_used[t][w] * warehouse_widths[t] for t in range(num_warehouse_types) for w in range(max_warehouses))

total_unused_area = total_warehouse_area - total_order_width

# Calculate the total available area in used warehouses and the unused area

model.Minimize(total_unused_area)

# Objective: minimize the unused width

solver = cp_model.CpSolver() # Creates an instance of the solver

status = solver.Solve(model) # Solves the model

# Check the solution status and display the results

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:

print('Total order width used:', solver.Value(total_order_width))

print('Total unused width:', solver.Value(total_unused_area))

print('Total unused width:', solver.Value(total_unused_area) / solver.Value(total_order_width), "%")

print("")

warehouse_counter = [[0] * max_warehouses for _ in range(num_warehouse_types)] # Counters for each type of warehouse

warehouse_loads = [[0] * max_warehouses for _ in range(num_warehouse_types)] # Sum of order widths in each warehouse

warehouse_number = 1

for t in range(num_warehouse_types):

for w in range(max_warehouses):

if solver.BooleanValue(warehouse_used[t][w]):

warehouse_counter[t][w] += 1

print(f'Warehouse width: {warehouse_widths[t]} mm (Warehouse number: {warehouse_number}) used:')

for o in range(num_orders):

if solver.BooleanValue(used[o][t][w]):

print(f' Order number: {orders[o][0]}, width: {orders[o][1]}, Warehouse type: {t}, Warehouse number: {warehouse_number}')

warehouse_loads[t][w] += orders[o][1]

warehouse_number += 1

print("")

warehouse_number = 1

for t in range(num_warehouse_types):

for w in range(max_warehouses):

if warehouse_loads[t][w] > 0:

print(f'Total load in warehouse type {t} number {warehouse_number}: {warehouse_loads[t][w]} (Capacity: {warehouse_widths[t]})')

warehouse_number += 1

else:

print('No solution found.')

# Example usage

warehouse_widths = [1500, 1000, 500, 768] # Widths of warehouse types in mm

# Orders: (Order number, width, length in mm)

orders = [

(1, 375, 40000), (2, 430, 40000), (3, 333, 40000), (4, 485, 40000), (5, 375, 40000), (6, 430, 40000),

(7, 510, 40000), (8, 442, 40000), (9, 520, 40000), (10, 333, 40000), (11, 540, 40000), (12, 1000, 40000)

]

optimize_warehouse_usage(warehouse_widths, orders)

[JGL]

What is the hardware you are using? Maybe also share some logs of problems of different sizes --> shows the number of variables, time before first solution etc.

Op vrijdag 14 juni 2024 om 18:12:21 UTC+2 schreef luiscl...@gmail.com: