# 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

## 1 Answer

Given what appears to be a nonlinear constraint (the 5% deviation constraint) and a nonlinear (and apparently arbitrarily complex) objective function, I would not be optimistic about finding a provably optimal solution. If you are willing to settle for a "good" solution, there are a variety of metaheuristics that might be applicable. Recommendation of a particular metaheuristic would depend on the specifics of the constraints and the religious tendencies of the person making the recommendation.

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.

• I have tried reading up on a few mixed-integer programming algorithms but haven't made any real inroads yet. Could you direct me to some specific class of techniques that could be fit for purpose here? The constraints are as in the question and I'm currently flexible with exploring all options – bb.jose Sep 14 '20 at 9:53
• Just to be clear, you are minimizing a cost function? Am I right that the larger variant will always be preferable at every store (so that, in the absence of the 5% deviation constraint, you would just go with the biggest possible value everywhere)? – prubin Sep 15 '20 at 15:19
• That is correct, minimizing the cost function. Since the regressed coefficient b is negative in all but few cases, lower variant will be preferred in all the stores if there's no deviation constraint. – bb.jose Sep 16 '20 at 8:01
• OK. I think you could get a good (not provably optimal) solution very quickly using a simple greedy heuristic. See the addendum to my answer. – prubin Sep 16 '20 at 20:15
• I tried the approach you suggested and it's giving me quite decent results. Just out of curiosity and also for the lack of being not well read with genetic algorithms, how would the steps for genetic algorithm have been different from the greedy heuristic? – bb.jose Sep 22 '20 at 9:39