I need support in setting constraints for a linear optimization problem modelled in PuLP.
Background:
There is a product that has a label. The label space is different depending on the product size - max space is known and set.
Each label has languages that are linked to certain countries. So a label = cluster of language country relations. (Currently number of clusters is manually pre-set for simplification, and can be changed to meet a feasible solution. However, ideally the model needs to identify minimum number of clusters to fulfil stated criteria.)
Languages need different amount of space on the label.
Furthermore, each country has a set of requirements such as:
Countries cannot be linked to more than one cluster.
Countries that do not share the same requirements cannot be clustered together (this is where I get stuck) e.g.:
The task is to create an optimization model that will group countries in clusters based on stated constraints. Eventually some clusters will always have one or two countries due to constraints no matter the label space available. At the same time 80% of the countries share the requirements and those need to be clustered based on the limited label space and other maximization goals (like volume per country), at the same time not have the 20% unique clusters mixed in.
The objective will be set to maximize each cluster based on country volume, or number of selling units, or sales share, etc. (not included in the question).
I need help or hint on how to only cluster countries with shared requirements. I am able to group countries under different clusters, meeting space constraint and maximizing toward whatever, but they are all mixed from requirements perspective. Below are data elements and their relations and part of my code. Thanks in advance!
CTY=["SG", "AT", "BE", "BG", "CH", "CY", "CZ", "DE", "DK", "DO", "ES", "FI", "FR", "GR", "HR", "HU", "IE", "IS", "IT", "LT", "LV", "NL", "NO", "PL", "PT", "RO", "RS", "SE", "SI", "SK", "RU", "US", "PR", "CA", "AU", "NZ", "JP", "IN", "PH", "GB", "CN"]
language=["EN_GB", "BG_BG", "CS_CZ", "DA_DK", "DE_DE", "EL_GR", "EN_GB", "ES_ES", "FI_FI", "FR_FR", "HR_HR", "HU_HU", "IT_IT", "LT_LT", "LV_LV", "NL_NL", "NO_NO", "PL_PL", "PT_PT", "RO_RO", "SK_SK", "SL_SI", "SR_RS", "SV_SE", "RU_RU", "EN_US", "EN_CA", "FR_CA", "EN_AU", "JA_JP", "EN_AU", "EN_IN", "EN_PH", "ZH_CN"]
BBD=["DD-MM-YYYY", "DD-ABC-YYYY", "YYYY/AB/DD", "YYYY-MM-DD"]
production_date=["DD-MM-YYYY", "YYYY-MM-DD", "NO"]
origin=["FP", "PI", "NO"]
space=[1, 2, 3]
max_language_space=5 #Main constraint - maximum allowed space for label. Value can change depending on the size of product.
clusters=np.arange(1, 12) #Number of clusters are a consequence to meet an optimal solution - aim to have as little number of clusters as possible at an optimal solution.
CTY_BBD={"SG":"DD-MM-YYYY", "AT":"DD-MM-YYYY", "BE":"DD-MM-YYYY", "BG":"DD-MM-YYYY", "CH":"DD-MM-YYYY", "CY":"DD-MM-YYYY", "CZ":"DD-MM-YYYY", "DE":"DD-MM-YYYY", "DK":"DD-MM-YYYY", "DO":"DD-MM-YYYY", "ES":"DD-MM-YYYY", "FI":"DD-MM-YYYY", "FR":"DD-MM-YYYY", "GR":"DD-MM-YYYY", "HR":"DD-MM-YYYY", "HU":"DD-MM-YYYY", "IE":"DD-MM-YYYY", "IS":"DD-MM-YYYY", "IT":"DD-MM-YYYY", "LT":"DD-MM-YYYY", "LV":"DD-MM-YYYY", "NL":"DD-MM-YYYY", "NO":"DD-MM-YYYY", "PL":"DD-MM-YYYY", "PT":"DD-MM-YYYY", "RO":"DD-MM-YYYY", "RS":"DD-MM-YYYY", "SE":"DD-MM-YYYY", "SI":"DD-MM-YYYY", "SK":"DD-MM-YYYY", "RU":"DD-MM-YYYY", "US":"DD-ABC-YYYY", "PR":"DD-ABC-YYYY", "CA":"YYYY/AB/DD", "AU":"DD-MM-YYYY", "NZ":"DD-MM-YYYY", "JP":"YYYY-MM-DD", "IN":"DD-MM-YYYY", "PH":"DD-ABC-YYYY", "GB":"DD-MM-YYYY", "CN":"YYYY-MM-DD"}
language_space={"EN_GB":1, "BG_BG":1, "CS_CZ":1, "DA_DK":1, "DE_DE":1, "EL_GR":1, "EN_GB":1, "ES_ES":1, "FI_FI":1, "FR_FR":1, "HR_HR":1, "HU_HU":1, "IT_IT":1, "LT_LT":1, "LV_LV":1, "NL_NL":1, "NO_NO":1, "PL_PL":1, "PT_PT":1, "RO_RO":1, "SK_SK":1, "SL_SI":1, "SR_RS":1, "SV_SE":1, "RU_RU":3, "EN_US":1, "EN_CA":1, "FR_CA":1, "EN_AU":1, "JA_JP":3, "EN_AU":1, "EN_IN":1, "EN_PH":1, "ZH_CN":2}
CTY_language={"SG":["EN_GB"], "AT":["DE_DE"], "BE":["FR_FR", "NL_NL"], "BG":["BG_BG"], "CH":["DE_DE", "FR_FR"], "CY":["EL_GR"], "CZ":["CS_CZ"], "DE":["DE_DE"], "DK":["DA_DK"], "DO":["ES_ES"], "ES":["ES_ES"], "FI":["FI_FI"], "FR":["FR_FR"], "GR":["EL_GR"], "HR":["HR_HR"], "HU":["HU_HU"], "IE":["EN_GB"], "IS":["FI_FI", "SV_SE"], "IT":["IT_IT"], "LT":["LT_LT"], "LV":["LV_LV"], "NL":["NL_NL"], "NO":["NO_NO"], "PL":["PL_PL"], "PT":["PT_PT"], "RO":["RO_RO"], "RS":["SR_RS"], "SE":["SV_SE"], "SI":["SL_SI"], "SK":["SK_SK"], "RU":["RU_RU"], "US":["EN_US"], "PR":["EN_US"], "CA":["EN_CA", "FR_CA"], "AU":["EN_AU"], "NZ":["EN_AU"], "JP":["JA_JP"], "IN":["EN_IN"], "PH":["EN_PH"], "GB":["EN_GB"], "CN":["ZH_CN"]}
CTY_production_date={"SG":"DD-MM-YYYY", "AT":"DD-MM-YYYY", "BE":"DD-MM-YYYY", "BG":"DD-MM-YYYY", "CH":"DD-MM-YYYY", "CY":"DD-MM-YYYY", "CZ":"DD-MM-YYYY", "DE":"DD-MM-YYYY", "DK":"DD-MM-YYYY", "DO":"DD-MM-YYYY", "ES":"DD-MM-YYYY", "FI":"DD-MM-YYYY", "FR":"DD-MM-YYYY", "GR":"DD-MM-YYYY", "HR":"DD-MM-YYYY", "HU":"DD-MM-YYYY", "IE":"DD-MM-YYYY", "IS":"DD-MM-YYYY", "IT":"DD-MM-YYYY", "LT":"DD-MM-YYYY", "LV":"DD-MM-YYYY", "NL":"DD-MM-YYYY", "NO":"DD-MM-YYYY", "PL":"DD-MM-YYYY", "PT":"DD-MM-YYYY", "RO":"DD-MM-YYYY", "RS":"DD-MM-YYYY", "SE":"DD-MM-YYYY", "SI":"DD-MM-YYYY", "SK":"DD-MM-YYYY", "RU":"DD-MM-YYYY", "US":"NO", "PR":"NO", "CA":"NO", "AU":"NO", "NZ":"NO", "JP":"NO", "IN":"DD-MM-YYYY", "PH":"NO", "GB":"NO", "CN":"YYYY-MM-DD"}
CTY_origin:{"SG":"FP", "AT":"PI", "BE":"PI", "BG":"PI", "CH":"PI", "CY":"PI", "CZ":"PI", "DE":"PI", "DK":"PI", "DO":"PI", "ES":"PI", "FI":"PI", "FR":"PI", "GR":"PI", "HR":"PI", "HU":"PI", "IE":"PI", "IS":"PI", "IT":"PI", "LT":"PI", "LV":"PI", "NL":"PI", "NO":"PI", "PL":"PI", "PT":"PI", "RO":"PI", "RS":"PI", "SE":"PI", "SI":"PI", "SK":"PI", "RU":"NO", "US":"FP", "PR":"FP", "CA":"FP", "AU":"NO", "NZ":"NO", "JP":"FP", "IN":"NO", "PH":"NO", "GB":"NO", "CN":"FP"}
prob=LpProblem('RU per cluster') #Eventually it is a LpMaximize optimization. The objective will be set to maximize CTY volume, or number of selling units, or sales share, etc. per cluster
x_cr=LpVariable.dicts('x',[(c, r) for c in clusters for r in CTY], 0, 1, LpBinary)
prob+=lpSum([language_space[l]*x_cr[(c, r)] for c in clusters for r in CTY for l in language if l in CTY_language[r]])
for c in clusters:
prob+=lpSum([language_space[l]*x_cr[(c, r)] for r in CTY for l in language if l in CTY_language[r]])<=max_language_space
for r in CTY:
prob+=lpSum(x_cr[(c, r)] for c in clusters)==1
OK. Now that we have a better idea of the structure of the problem, here is a framework that I think will help you out.
The first part of the code makes groups from your data, excluding language. The model portion assigns countries and groups to labels, with some constraints that are labeled. Basically only 1 group is allowed per label and I put in an artificial constraint so that each group can only be used once to force the model to use multiple groups.
You didn't have any info in your model about why you would prefer one country over the other on any particular label (I'm assuming that is going to be handled elsewhere), so I just put in an objective to maximize the number of countries placed. Seems to work, it draws from the biggest group to fit the biggest label, etc.
from collections import defaultdict
from pulp import *
CTY=["SG", "AT", "BE", "BG", "CH", "CY", "CZ", "DE", "DK", "DO", "ES", "FI", "FR", "GR", "HR", "HU", "IE", "IS", "IT", "LT", "LV", "NL", "NO", "PL", "PT", "RO", "RS", "SE", "SI", "SK", "RU", "US", "PR", "CA", "AU", "NZ", "JP", "IN", "PH", "GB", "CN"]
language=["EN_GB", "BG_BG", "CS_CZ", "DA_DK", "DE_DE", "EL_GR", "EN_GB", "ES_ES", "FI_FI", "FR_FR", "HR_HR", "HU_HU", "IT_IT", "LT_LT", "LV_LV", "NL_NL", "NO_NO", "PL_PL", "PT_PT", "RO_RO", "SK_SK", "SL_SI", "SR_RS", "SV_SE", "RU_RU", "EN_US", "EN_CA", "FR_CA", "EN_AU", "JA_JP", "EN_AU", "EN_IN", "EN_PH", "ZH_CN"]
BBD=["DD-MM-YYYY", "DD-ABC-YYYY", "YYYY/AB/DD", "YYYY-MM-DD"]
production_date=["DD-MM-YYYY", "YYYY-MM-DD", "NO"]
origin=["FP", "PI", "NO"]
space=[1, 2, 3]
max_language_space=5 #Main constraint - maximum allowed space for label. Value can change depending on the size of product.
#clusters=np.arange(1, 12) #Number of clusters are a consequence to meet an optimal solution - aim to have as little number of clusters as possible at an optimal solution.
CTY_BBD={"SG":"DD-MM-YYYY", "AT":"DD-MM-YYYY", "BE":"DD-MM-YYYY", "BG":"DD-MM-YYYY", "CH":"DD-MM-YYYY", "CY":"DD-MM-YYYY", "CZ":"DD-MM-YYYY", "DE":"DD-MM-YYYY", "DK":"DD-MM-YYYY", "DO":"DD-MM-YYYY", "ES":"DD-MM-YYYY", "FI":"DD-MM-YYYY", "FR":"DD-MM-YYYY", "GR":"DD-MM-YYYY", "HR":"DD-MM-YYYY", "HU":"DD-MM-YYYY", "IE":"DD-MM-YYYY", "IS":"DD-MM-YYYY", "IT":"DD-MM-YYYY", "LT":"DD-MM-YYYY", "LV":"DD-MM-YYYY", "NL":"DD-MM-YYYY", "NO":"DD-MM-YYYY", "PL":"DD-MM-YYYY", "PT":"DD-MM-YYYY", "RO":"DD-MM-YYYY", "RS":"DD-MM-YYYY", "SE":"DD-MM-YYYY", "SI":"DD-MM-YYYY", "SK":"DD-MM-YYYY", "RU":"DD-MM-YYYY", "US":"DD-ABC-YYYY", "PR":"DD-ABC-YYYY", "CA":"YYYY/AB/DD", "AU":"DD-MM-YYYY", "NZ":"DD-MM-YYYY", "JP":"YYYY-MM-DD", "IN":"DD-MM-YYYY", "PH":"DD-ABC-YYYY", "GB":"DD-MM-YYYY", "CN":"YYYY-MM-DD"}
language_space={"EN_GB":1, "BG_BG":1, "CS_CZ":1, "DA_DK":1, "DE_DE":1, "EL_GR":1, "EN_GB":1, "ES_ES":1, "FI_FI":1, "FR_FR":1, "HR_HR":1, "HU_HU":1, "IT_IT":1, "LT_LT":1, "LV_LV":1, "NL_NL":1, "NO_NO":1, "PL_PL":1, "PT_PT":1, "RO_RO":1, "SK_SK":1, "SL_SI":1, "SR_RS":1, "SV_SE":1, "RU_RU":3, "EN_US":1, "EN_CA":1, "FR_CA":1, "EN_AU":1, "JA_JP":3, "EN_AU":1, "EN_IN":1, "EN_PH":1, "ZH_CN":2}
CTY_language={"SG":["EN_GB"], "AT":["DE_DE"], "BE":["FR_FR", "NL_NL"], "BG":["BG_BG"], "CH":["DE_DE", "FR_FR"], "CY":["EL_GR"], "CZ":["CS_CZ"], "DE":["DE_DE"], "DK":["DA_DK"], "DO":["ES_ES"], "ES":["ES_ES"], "FI":["FI_FI"], "FR":["FR_FR"], "GR":["EL_GR"], "HR":["HR_HR"], "HU":["HU_HU"], "IE":["EN_GB"], "IS":["FI_FI", "SV_SE"], "IT":["IT_IT"], "LT":["LT_LT"], "LV":["LV_LV"], "NL":["NL_NL"], "NO":["NO_NO"], "PL":["PL_PL"], "PT":["PT_PT"], "RO":["RO_RO"], "RS":["SR_RS"], "SE":["SV_SE"], "SI":["SL_SI"], "SK":["SK_SK"], "RU":["RU_RU"], "US":["EN_US"], "PR":["EN_US"], "CA":["EN_CA", "FR_CA"], "AU":["EN_AU"], "NZ":["EN_AU"], "JP":["JA_JP"], "IN":["EN_IN"], "PH":["EN_PH"], "GB":["EN_GB"], "CN":["ZH_CN"]}
CTY_production_date={"SG":"DD-MM-YYYY", "AT":"DD-MM-YYYY", "BE":"DD-MM-YYYY", "BG":"DD-MM-YYYY", "CH":"DD-MM-YYYY", "CY":"DD-MM-YYYY", "CZ":"DD-MM-YYYY", "DE":"DD-MM-YYYY", "DK":"DD-MM-YYYY", "DO":"DD-MM-YYYY", "ES":"DD-MM-YYYY", "FI":"DD-MM-YYYY", "FR":"DD-MM-YYYY", "GR":"DD-MM-YYYY", "HR":"DD-MM-YYYY", "HU":"DD-MM-YYYY", "IE":"DD-MM-YYYY", "IS":"DD-MM-YYYY", "IT":"DD-MM-YYYY", "LT":"DD-MM-YYYY", "LV":"DD-MM-YYYY", "NL":"DD-MM-YYYY", "NO":"DD-MM-YYYY", "PL":"DD-MM-YYYY", "PT":"DD-MM-YYYY", "RO":"DD-MM-YYYY", "RS":"DD-MM-YYYY", "SE":"DD-MM-YYYY", "SI":"DD-MM-YYYY", "SK":"DD-MM-YYYY", "RU":"DD-MM-YYYY", "US":"NO", "PR":"NO", "CA":"NO", "AU":"NO", "NZ":"NO", "JP":"NO", "IN":"DD-MM-YYYY", "PH":"NO", "GB":"NO", "CN":"YYYY-MM-DD"}
CTY_origin={"SG":"FP", "AT":"PI", "BE":"PI", "BG":"PI", "CH":"PI", "CY":"PI", "CZ":"PI", "DE":"PI", "DK":"PI", "DO":"PI", "ES":"PI", "FI":"PI", "FR":"PI", "GR":"PI", "HR":"PI", "HU":"PI", "IE":"PI", "IS":"PI", "IT":"PI", "LT":"PI", "LV":"PI", "NL":"PI", "NO":"PI", "PL":"PI", "PT":"PI", "RO":"PI", "RS":"PI", "SE":"PI", "SI":"PI", "SK":"PI", "RU":"NO", "US":"FP", "PR":"FP", "CA":"FP", "AU":"NO", "NZ":"NO", "JP":"FP", "IN":"NO", "PH":"NO", "GB":"NO", "CN":"FP"}
# group the countries by key properties
groupings = defaultdict(list)
# and the space required, indexed by country
space_reqd = dict()
for c in CTY:
# get the language... Not clear what to do with multiple languages
# as the language affects the space requirement. We'll just pick the "first"
language = CTY_language[c][0]
space_reqd[c] = language_space[language]
# gather the properties as a key
properties = (CTY_BBD[c], CTY_origin[c], CTY_production_date[c])
# add this country to the list with these properties
groupings[properties].append(c)
print(f'Grouping resulted in {len(groupings)} groups')
# let's make some fake labels with space parameter
label_sizes = { 'soda': 3,
'salad': 4,
'bread': 2,
'cereal': 7}
M = max(len(v) for v in groupings.values())
# now we can set up the problem
prob = LpProblem('label_maker', sense=LpMaximize)
# some convenience sets
grps = groupings.keys()
lbls = label_sizes.keys()
ctry_lbl = [(ctry, lbl) for ctry in CTY for lbl in lbls]
grp_lbl = [(grp, lbl) for grp in grps for lbl in lbls]
place = LpVariable.dicts('place', ctry_lbl, cat=LpBinary) # place country on label
assign_group = LpVariable.dicts('group', grp_lbl, cat=LpBinary) # assign group to label
# keep within max size, for each label
for lbl in lbls:
prob += lpSum(place[ctry, lbl] for ctry in CTY) <= label_sizes[lbl]
# only 1 group per label
for lbl in lbls:
prob += lpSum(assign_group[grp, lbl] for grp in grps) <= 1
# link the selection of a country to the group, for each label
for grp, lbl in grp_lbl:
prob += assign_group[grp, lbl] * M >= lpSum(place[ctry, lbl] for ctry in groupings[grp])
# some fake constraint to not reuse groups...this is just to exercise the model
for grp in grps:
prob += lpSum(assign_group[grp, lbl] for lbl in lbls) <= 1
# objective: maximize the countries placed
prob += lpSum(place[ctry, lbl] for (ctry, lbl) in ctry_lbl)
#print(prob)
solution = prob.solve()
print(solution)
for ctry, lbl in sorted(ctry_lbl, key = lambda x: x[1]):
if place[ctry, lbl].varValue:
print(f'place {ctry} on label {lbl}')
for grp, lbl in sorted(grp_lbl, key = lambda x: x[1]):
if assign_group[grp, lbl].varValue:
print(f'label {lbl} utilizes group format: {grp}')
Result - Optimal solution found
Objective value: 14.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.01
Time (Wallclock seconds): 0.01
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.01 (Wallclock seconds): 0.01
1
place US on label bread
place PR on label bread
place GR on label cereal
place HR on label cereal
place HU on label cereal
place IS on label cereal
place IT on label cereal
place PL on label cereal
place SI on label cereal
place RU on label salad
place IN on label salad
place AU on label soda
place NZ on label soda
place GB on label soda
label bread utilizes group format: ('DD-ABC-YYYY', 'FP', 'NO')
label cereal utilizes group format: ('DD-MM-YYYY', 'PI', 'DD-MM-YYYY')
label salad utilizes group format: ('DD-MM-YYYY', 'NO', 'DD-MM-YYYY')
label soda utilizes group format: ('DD-MM-YYYY', 'NO', 'NO')