How do I find an optimal combination when an exhaustive search would take way too long?

Question

Disclaimer: I'm a complete amateur with no formal training who's just taught himself a bit of C# and Python

There 47 slots. Each one must be filled by one item. These slots are split into 8 groups. Items are categorized into the same 8 groups.
Each slot can only be filled by an item of the same group.
The same item can be be used to fill multiple slots.

Each item consists of a name, a group and 9 stats.

item ("name", "group", "stat1", "stat2", "stat3", ..., "stat9")

exampleItem (exampleName, groupA, 3, 8, 19, ..., 431)

Each slot consists of an ID and a group.

slot1 (1, groupC)

Have each slot filled with an item (following the rules above).

Then add up each different stat.

stat1Total=item1(stat1)+item2(stat1)+item3(stat1)+...+item47(stat1)

The goals are:
-have every slot filled with an item of the corresponding group. (no empty slots)
-have stat1Total, stat2Total and stat3Total reach a certain amount (stat1Goal, stat2Goal, stat3Goal)
-have stat1Total, stat2Total and stat3Total go over that amount as little as possible
-maximize all other statTotal with weightings each

Output the best possible combination of items that meet the goals above. (If 2 or more combinations are equally the best, output all of them.

I've tried to just search all possible combinations for the best output but in total that'd amount to 2.16x10^16 possible combinations so I don't think that's doable.
Now I have no clue how to approach this problem and the more I read about integer programming, the more confused I get.

To illustrate the problem I'll give a simplified example with 3 slots, 2 groups and 5 items:

SlotA, SlotB and SlotC have to be filled by one of the 5 items each.
Slot A and SlotB belong to group Group1 and SlotC belongs to Group2.
The items are categorized into the same groups. So we have Item1, Item2 and Item3 belonging to Group1 and Item4 and Item5 belonging to Group2.

That means that SlotA and SlotB can only be filled by Item1, Item2 and Item3. You can imagine the slots being holes of different shapes and the items having shapes fitting to those holes. You can't fit a star-shaped peg into a square hole and you can't fit Item5 into SlotB because it wouldn't fit.

The items themselves have different stats. For this example we assume each item only has the group it belongs to and 2 stats: StatDark, StatLight. These can take integer values between 0 and 10.

Item1(Group1, StatDark=3, StatLight=5)
Item2(Group1, StatDark=7, StatLight=1)
Item3(Group1, StatDark=2, StatLight=5)
Item4(Group2, StatDark=1, StatLight=6)
Item5(Group2, StatDark=2, StatLight=5)

The goals for this example are:
-to fill every slot with one item while respecting the grouping rules
-to have the sum of all StatDark across all chosen items be equal or greater than 9
-to minimize StatDark above 9 (every StatDark above 9 is useless and wasted)
-to maximize the sum of all StatLight across all chosen items

In this case the optimal solution would be:
SlotA & SlotB: Item2 & Item3
SlotC: Item4

Here is a link to the full table for this example: https://i.sstatic.net/TluHG.jpg

I hope this example makes the problem a bit more understandable.

Answer 1

Mathematical Model

I would introduce a binary variable:

x[i,j] = 1 if item i is assigned to slot j
         0 otherwise

Here is our first issue: there are many (i,j) combinations that are not allowed. A smart model would try not to generate the forbidden combinations. So we need to implement a sparse variable instead of a fully allocated one. We want to allocate and use x[i,j] only if allowed(i,j) is true.

Furthermore, introduce a continuous variable xstat[s] that calculates the total value for each stat.

Once we have this we can write down the constraints:

  sum( i | allowed(i,j),  x[i,j] ) = 1  for all slots j          (exactly one item in each slot)
  xstat[s] = sum( (i,j) | allowed(i,j),  x[i,j] * stat[i,s])     (calculate total stats)  
  xstat['StatDark'] >= 9                                         

The objective is a weighted sum of the two objectives:

  minimize xstat['StatDark'] - 9
  maximize xstat['StatLight']

so we do:

  maximize -w1*(xstat['StatDark'] - 9) +  w2*xstat['StatLight']

for user-provided weights w1 and w2.

These two issues make the problem a little bit more complicated. In addition, we need to do some work on the data to make it suitable for use in the optimization model.

Python Code

import pandas as pd
import pulp as lp
from io import StringIO

#----------------------------------------
# raw data
#----------------------------------------

itemData = pd.read_table(StringIO("""
Item   Group  StatDark StatLight
Item1  Group1    3        5
Item2  Group1    7        1
Item3  Group1    2        5
Item4  Group2    1        6
Item5  Group2    2        5
"""),sep="\s+")

slotData = pd.read_table(StringIO("""
Slot   Group
SlotA  Group1
SlotB  Group1
SlotC  Group2
"""),sep='\s+')

# minimum total of Dark
minDark = 9

# stats
stat = ['StatDark','StatLight']

# objective weights
# we have two objectives and there are trde offs between them.
# here we use a simple weighted sum approach. These are the weights.
w = {'StatDark':0.3, 'StatLight':0.7}

#----------------------------------------
# data prep
#----------------------------------------


# join on Group
# we need to know which (Item,Slot) combinations are allowed.
merged = pd.merge(itemData[['Item','Group']],slotData,on='Group').set_index(['Item','Slot'])
 
items = itemData['Item']
slots = slotData['Slot']


# we will use the convention:
#  i : items
#  j : slots
#  s : stats

# stat values
# easy lookup of statv[(i,s)]
itemData = itemData.set_index('Item')
statv = {(i,s):itemData.loc[i,s] for i in items for s in stat}

#----------------------------------------
# MIP model
#----------------------------------------

# x[(i,j)] = 1 if item i is assigned to slot j
#            0 otherwise
# only use combinations (i,j) that are allowed
x = lp.LpVariable.dicts('x', [(i,j) for i,j in merged.index], cat='Binary') 

# xstat[stat] = total accumulated values
xstat = lp.LpVariable.dicts('xstat', [s for s in stat], cat='Continuous', lowBound = 0)

prob = lp.LpProblem("assignItemsToSlots", lp.LpMaximize)

# objective: weighted sum
#----------
# 1. minimize statDark exceeding minDark
# 2. maximize statLight
prob +=  -w['StatDark']*(xstat['StatDark'] - minDark) + w['StatLight']*xstat['StatLight']

# constraints
# -----------

# each slot much have exactly one item
# (but the same item can go to different slots)
for j in slots:
  prob += lp.lpSum([x[(i,j)] for i,jj in merged.index if jj==j]) == 1

#  minimum total value for dark 
prob += xstat['StatDark'] >= minDark 

# calculate stat totals
for s in stat:
  prob += xstat[s] == lp.lpSum([x[(i,j)]*statv[i,s] for i,j in merged.index])


#----------------------------------------
# solve problem
#----------------------------------------

prob.solve()
# to show the log use 
# solve(pulp.PULP_CBC_CMD(msg=1))

print("Status:", lp.LpStatus[prob.status])
print("Objective:",lp.value(prob.objective))

#----------------------------------------
# solution
#----------------------------------------

assigned = []
for i,j in merged.index:
  if lp.value(x[(i,j)]) > 0.5:
    assigned += [[i, j]]
assigned = pd.DataFrame(assigned, columns=['item','slot'])
print(assigned)

Discussion

The table merged looks like:

Item   Slot   Group
-----------------------
Item1   SlotA   Group1
        SlotB   Group1
Item2   SlotA   Group1
        SlotB   Group1
Item3   SlotA   Group1
        SlotB   Group1
Item4   SlotC   Group2
Item5   SlotC   Group2 

The Item,Slot columns give us the allowed combinations.

The dict statv gives a convenient data structure to access the stat contributions:

{('Item1', 'StatDark'): 3,
 ('Item1', 'StatLight'): 5,
 ('Item2', 'StatDark'): 7,
 ('Item2', 'StatLight'): 1,
 ('Item3', 'StatDark'): 2,
 ('Item3', 'StatLight'): 5,
 ('Item4', 'StatDark'): 1,
 ('Item4', 'StatLight'): 6,
 ('Item5', 'StatDark'): 2,
 ('Item5', 'StatLight'): 5}

The generated MIP model looks like:

assignItemsToSlots:
MAXIMIZE
-0.3*xstat_StatDark + 0.7*xstat_StatLight + 2.6999999999999997
SUBJECT TO
_C1: x_('Item1',_'SlotA') + x_('Item2',_'SlotA') + x_('Item3',_'SlotA') = 1

_C2: x_('Item1',_'SlotB') + x_('Item2',_'SlotB') + x_('Item3',_'SlotB') = 1

_C3: x_('Item4',_'SlotC') + x_('Item5',_'SlotC') = 1

_C4: xstat_StatDark >= 9

_C5: - 3 x_('Item1',_'SlotA') - 3 x_('Item1',_'SlotB')
 - 7 x_('Item2',_'SlotA') - 7 x_('Item2',_'SlotB') - 2 x_('Item3',_'SlotA')
 - 2 x_('Item3',_'SlotB') - x_('Item4',_'SlotC') - 2 x_('Item5',_'SlotC')
 + xstat_StatDark = 0

_C6: - 5 x_('Item1',_'SlotA') - 5 x_('Item1',_'SlotB') - x_('Item2',_'SlotA')
 - x_('Item2',_'SlotB') - 5 x_('Item3',_'SlotA') - 5 x_('Item3',_'SlotB')
 - 6 x_('Item4',_'SlotC') - 5 x_('Item5',_'SlotC') + xstat_StatLight = 0

VARIABLES
0 <= x_('Item1',_'SlotA') <= 1 Integer
0 <= x_('Item1',_'SlotB') <= 1 Integer
0 <= x_('Item2',_'SlotA') <= 1 Integer
0 <= x_('Item2',_'SlotB') <= 1 Integer
0 <= x_('Item3',_'SlotA') <= 1 Integer
0 <= x_('Item3',_'SlotB') <= 1 Integer
0 <= x_('Item4',_'SlotC') <= 1 Integer
0 <= x_('Item5',_'SlotC') <= 1 Integer
xstat_StatDark Continuous
xstat_StatLight Continuous

Solution

The solution looks like:

Status: Optimal
Objective: 8.099999999999998
    item   slot
0  Item2  SlotB
1  Item3  SlotA
2  Item4  SlotC