# Combinatorial Optimisation, Allocation problem

I am trying to solve a problem (in pyspark/ python) where I need to find two distinct values to allocate, and how to allocate them in a network of stores.

The two distinct values can only be integer values and constrained within a lower and upper bound. For each such distinct value pair, say 4 and 8, each store can get either 4 or 8 giving a total of 2n different ways of allocation if there are n stores (n is close to 1000).

The objective function is a complex one and uses predictive models to give the impact of a particular value pair corresponding to its allocation in the network.

I was hoping if I could create a cost function of the form:

Cost  = f( variant1, variant2, store_1_variant, store_2_variant, ..., store_n_variant)


where

• variant1 = 4 (integer, constrained within a max value)
• variant2 = 8 (integer, constrained within a max value)
• store_1_variant, ..., store_n_variant are binary [0,1] to suggest whether they receive variant_1 or not (not receiving variant1 would mean receiving variant2)

I could solve for the n + 2 parameters that minimize the cost (there is another constraint that needs to keep in check the impact of a certain allocation)

I have looked at various combinatorial optimisation techniques but none that seem to allow me a user defined function as a cost function.

I have no prior experience in to this area so any direction/ assistance is appreciated.

Edit

To add some information on the current form of cost function, continuing with the example of two variants being 4 and 8 with say 5 stores, f(4, 8, 0, 1, 1, 0, 0) will have an associated cost of the form

a*s11*(s12/8)b + a*s21*(s22/4)b + a*s31*(s32/4)b + a*s41*(s42/8)b + a*s51*(s52/8)b

where s11 and s12 are store level metrics for store 1 and so on.

Parameters a and b are regressed coefficients from historic data, but this is just a good starting point and will eventually evolve into a more complex functional form (might be predictions from an ML algorithm)

Constraints:

variant1 <= k1
variant2 >= k1 and <= k2
(s13/8) + (s23/4) + (s33/4) + (s43/8) + (s53/8) should lie between [ (0.95/k1) * (s13 + s23 + s33+ s43+ s53), (1.05/k1) * (s13 + s23 + s33+ s43+ s53) ] (5% deviation)
where k1, k2, variant1 and variant2 are integers

• Is the objective function (f, generated by the predictive models) explicit or black box? Do you know any properties about it? – dhasson Sep 3 '20 at 21:23
• Currently explicit but might evolve into something more complex. I have made some edits to the post to add additional information about the current form of cost function – bb.jose Sep 3 '20 at 23:49

Addendum: Based on comments below, I tried both a genetic algorithm and a greedy heuristic. The greedy heuristic consistently outperformed the GA (better answer in must less time). Coded in R and run a PC with made up data for 1,000 stores (using $$k_1=6$$ and $$k_2=12$$), the greedy heuristic typically took under 0.2 seconds. The greedy heuristic loops through all possible values of variant1 and variant2. For each combination, it initially assigns the cheaper of the two to all stores, then checks whether the balance constraint is met. If not, it loops through the stores in a "biggest bang for the buck" order, switching stores from the cheaper variant to the more expensive one, until balance is (hopefully) met. Of course, larger values of $$k_1$$ and $$k_2$$ will lead to more processing time, but I think this is still a very practical route to take.