[Python] Suggestion needed for enhancing problem formulation for constraint programming

I'm trying to formulize a constraint programming solution for item allocation on shelf. The goal is simple items belonging to same brand should be kept as close as possible and should maintain a decent square or rectangular block.

for this, the approach we have taken is we have divided the whole available space on planogram into smaller partition of smaller granularity and did the same with every individual item, for e.g. If there are 3 shelf on my planogram each of 10 cm then my partition count will be 30 considering granularity of 1.

Once partitioned it'll look like this:



where each (x,y) point denotes x -> partition number on shelf, y -> shelf number. Now, I do this also for every item as well, so if there's a item whose width is 3, there will be 3 partition where it'll be kept.

Now, I want for all of my items belonging to same brand to be kept together and for that I defined a few constraints.

1. All Items should take their required space on planogram.
2. Every partition point should be assigned to one item only.
3. All the partition of an item should be on the same shelf.
4. All the partition of same item should be together.
5. All the item partition of same brand connected to each other will have a adjacency score, I'm trying to maximize this score.

Here, the code is working really well for small planogram with less number of items but as the size and item count is increasing, The code is searching forever and we also saw performance is also not improving better.

Below's my code:

import cpmpy as cp
import numpy as np
import pandas as pd
import seaborn as sns
import networkx as nx

import matplotlib.pyplot as plt
from collections import defaultdict
from GridGraph_mod import process_group

from concurrent.futures import ProcessPoolExecutor, as_completed

pd.set_option("display.max_rows", 500)
pd.set_option("display.max_columns", 500)


def create_mapping(brand_shelf_allowded_mapping, pog_df, shelf_count):

remaining_brand = set(pog_df.brand_nm.unique()) - set(brand_shelf_allowded_mapping["brand_nm"])
brand_shelf_allowded_mapping['brand_nm'].extend(remaining_brand)
for _ in range(len(remaining_brand)):
brand_shelf_allowded_mapping['shelf_allowed'].append([x for x in range(shelf_count)])

return brand_shelf_allowded_mapping


def parallel_creator(key, idx_df):
node_dict = {}
with ProcessPoolExecutor() as executor:
futures = {executor.submit(process_group, level, data): level for level, data in idx_df.groupby(key)}
for future in as_completed(futures):
level, var_dict = future.result()
node_dict[level] = var_dict
return node_dict


if __name__ == "__main__":

bay_count = 3
granularity = 1
shelf_count = 7
section_width = 133

grid_width = int(section_width * bay_count / granularity)
grid_height = shelf_count

pog_df = pd.read_csv("data_temp/N3ADAA.csv")

pog_df['linear'] = pog_df.linear.apply(np.ceil)
pog_df['gridlinear'] = pog_df.linear//granularity

G = nx.grid_2d_graph(int(section_width * bay_count/granularity),int(shelf_count))
pos = {(x, y): (x, y) for x, y in G.nodes()}

products = pog_df[['tpnb', 'gridlinear']].astype(str)
locations = pd.Series([str(s) for s in G.nodes()], name='location')
locations = pd.concat([locations,locations.to_frame().location.str.strip("() ").str.split(',', expand=True).rename(columns={0: 'x', 1: 'y'})], axis=1)

pog_df = pd.merge(pog_df,
pog_df.groupby("brand_nm", as_index=False).agg(gridlinear_brand = ("gridlinear", "sum")),
on = "brand_nm")


l_c_idx = pd.merge(pog_df.reset_index(drop=True),
locations,
how='cross')[['tpnb', 'brand_nm', 'gridlinear', 'gridlinear_brand', 'location', 'x', 'y']]

l_c_idx["x"] = l_c_idx["x"].astype("int32")
l_c_idx["y"] = l_c_idx["y"].astype("int32")

brand_shelf_allowded_mapping = {
"brand_nm": ['TESCO ESSENTIALS', 'TESCO PROFORMULA', 'PRONAMEL', 'FIXODENT', 'MACLEANS', 'ARM & HAMMER', 'TEPE', 'POLIGRIP', 'STERADENT', 'PRO FORMULA', 'ORAL-B', 'COLGATE', 'LISTERINE', 'SENSODYNE','CORSODYL', 'AQUAFRESH'],
"shelf_allowed": [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0,1], [2,3,4,5], [2,3,4,5], [2,3,4,5], [0,1], [6], [6]]
}

brand_shelf_allowded_mapping = create_mapping(brand_shelf_allowded_mapping, pog_df, shelf_count)

brand_shelf_allowded_mapping_df = pd.DataFrame(brand_shelf_allowded_mapping)
brand_shelf_allowded_mapping_df = brand_shelf_allowded_mapping_df.explode("shelf_allowed")
brand_shelf_allowded_mapping_df.shelf_allowed = brand_shelf_allowded_mapping_df.shelf_allowed.astype("int32")

l_c_idx = pd.merge(l_c_idx, brand_shelf_allowded_mapping_df, left_on=["brand_nm", "y"], right_on=["brand_nm", "shelf_allowed"], how="inner")[l_c_idx.columns]
l_c_idx['Var'] = l_c_idx.apply(lambda x: cp.boolvar(name=x['location']+'-'+str(x['tpnb'])+'-'+x["brand_nm"]), axis=1)

# model_initiation
m = cp.Model()

# 1. Every Item should take whatever space is needed by them
l_c_idx.groupby('tpnb', as_index=False).agg({'Var':cp.sum, 'gridlinear': 'unique'}).apply(lambda x: m.constraints.append(x['Var']==int(float(x["gridlinear"]))), axis=1)

# 2. All location should take distinct items only
l_c_idx.groupby('location', as_index=False).agg({'Var':cp.sum}).apply(lambda x: m.constraints.append(x['Var']<=1), axis=1)

# 3. All Item partitions should be on the same shelf
l_c_idx["y"] = l_c_idx["y"].astype("int32")
l_c_idx["x"] = l_c_idx["x"].astype("int32")
shelf_var = {tpnb: cp.intvar(0, max(l_c_idx["y"])) for tpnb in l_c_idx["tpnb"].unique()}
l_c_idx.apply(lambda row: m.constraints.append(
(row['Var'] == 1).implies(row['y'] == shelf_var[row['tpnb']])
), axis=1)

# 4. All the item partition should be together
node_p_var_dict = parallel_creator('tpnb', l_c_idx)

for p in l_c_idx['tpnb'].unique():
for shelf in sorted(l_c_idx[l_c_idx.tpnb == p].y.unique()):
m.constraints.append(
cp.sum([(node_p_var_dict[p][(level, shelf)] != node_p_var_dict[p][(level+1, shelf)])
for level in range(section_width*bay_count - 1)]) <= 2
)
m.constraints.append(node_p_var_dict[p][(0, shelf)] + node_p_var_dict[p][((section_width*bay_count)-1, shelf)] <= 1)



adj_var = dict()
for brand in l_c_idx['brand_nm'].unique():
if brand in ['ORAL-B']:
brand_neighbors = []
temp = defaultdict(dict)
brand_df = l_c_idx[l_c_idx['brand_nm'] == brand].copy()
brand_df['x'] = brand_df['x'].astype(int)
brand_df['y'] = brand_df['y'].astype(int)
for _, r in brand_df.iterrows():
temp[(int(r['x']), int(r['y']))][r['tpnb']] = r['Var']

for (x, y), curr in temp.items():

for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
neighbor_pos = (x+dx, y+dy)
if neighbor_pos in temp:
neighbor = cp.any(temp[neighbor_pos].values())
brand_neighbors.append(cp.any(curr.values()) & neighbor)

adj_var[brand] = cp.intvar(0, len(brand_neighbors), name=f"adj_score_{brand}")

#print(len(brand_neighbors), int(brand_df.gridlinear_brand.unique()[0]), len(brand_neighbors)/int(brand_df.gridlinear_brand.unique()[0]) * 10)

m += (adj_var[brand] == (cp.sum(brand_neighbors)//int(brand_df.gridlinear_brand.unique()[0])) * 10)
#m += (adj_var[brand] == cp.sum(brand_neighbors))
#m += (cp.sum(brand_neighbors)//int(brand_df.gridlinear_brand.unique()[0])) * 10 > 10

print("total constraints added = ", len(m.constraints))

m.maximize(sum(adj_var.values()))

print("All constraint added, now trying to solve !!!")

if m.solve(time_limit=500, num_search_workers=8, log_search_progress=True):

sum_ = 0
for k,v in adj_var.items():
sum_ += v.value()
print("Solution found with adjacency value = ", sum_)
l_c_idx['value'] = l_c_idx.Var.apply(lambda x : x.value())
selected_items = l_c_idx[l_c_idx["value"] == True]
unique_items = selected_items["brand_nm"].unique()
palette = sns.color_palette("Spectral", len(unique_items))
color_map_dict = {item: palette for i, item in enumerate(unique_items)}

# Create grid graph
G_temp = nx.grid_2d_graph(int(section_width * bay_count / granularity), int(shelf_count))
G_temp.remove_edges_from(list(G_temp.edges))

# Set positions for each node
pos = {(x, y): (x, y) for x, y in G_temp.nodes()}

# Assign colors based on item placement
node_colors = []
for x, y in G_temp.nodes():
item_at_loc = selected_items[selected_items["location"] == str((x, y))]
if not item_at_loc.empty:
node_colors.append(color_map_dict[item_at_loc["brand_nm"].values[0]])
else:
node_colors.append("white")

# Plot graph
plt.figure(figsize=(20, 15))
nx.draw(G_temp, pos, node_size=50, node_color=node_colors, with_labels=False)
else:
print("No solution found")



GridGraph_mod.py

import networkx as nx


def process_group(level, data):
return level, {eval(row['location']): row['Var'] for _, row in data.iterrows()}


Data: Sample

tpnb,linear,item_height,item_width,item_depth,brand_nm
61452116,16.1,3.6,15.0,3.0,AQUAFRESH
62977195,14.0,4.5,13.0,3.7,SENSODYNE
81116754,17.2,4.6,17.0,3.8,AQUAFRESH
85988423,16.0,3.6,15.0,3.0,COLGATE
85992262,9.0,14.9,3.5,3.5,TESCO PROFORMULA
85992832,9.8,18.9,4.5,2.5,TESCO PROFORMULA
86016064,11.4,23.0,10.5,2.4,TESCO ESSENTIALS
88903192,17.2,4.6,17.0,3.8,AQUAFRESH
91256336,17.8,23.2,4.2,3.0,AQUAFRESH
51769631,19.5,4.2,19.0,3.5,MACLEANS
52098829,19.5,4.2,19.0,3.5,MACLEANS
76956089,19.7,4.3,18.9,3.8,AQUAFRESH
79360074,35.0,4.5,17.3,4.0,COLGATE
84928779,18.4,3.3,18.0,3.3,TESCO ESSENTIALS
93038799,19.4,4.5,18.7,3.7,AQUAFRESH
51164799,19.5,21.2,9.0,4.6,COLGATE
51257776,19.5,21.2,9.0,4.6,COLGATE
73385394,19.5,21.3,9.0,4.5,COLGATE
85290842,34.0,22.5,8.4,5.0,TESCO ESSENTIALS
85290856,17.4,22.1,8.5,4.8,PRO FORMULA
86006295,13.5,16.2,6.4,6.4,TESCO PROFORMULA
61489561,21.0,16.0,7.0,4.8,AQUAFRESH
74168299,8.9,23.0,4.2,2.5,AQUAFRESH
80184938,26.0,23.0,5.5,2.8,COLGATE
81116731,35.0,4.6,17.0,3.8,AQUAFRESH
84538526,17.5,3.8,16.9,1.3,AQUAFRESH
91713372,12.3,23.9,11.0,5.0,ORAL-B
92000950,6.8,21.6,6.0,1.0,ORAL-B


Please help how can I make this work for large inputs as well.

Continue reading...