Combinatorial Optimisation, Allocation problem

Question

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 2ⁿ 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*s₁₁*(s₁₂/8)^b + a*s₂₁*(s₂₂/4)^b + a*s₃₁*(s₃₂/4)^b + a*s₄₁*(s₄₂/8)^b + a*s₅₁*(s₅₂/8)^b

where s₁₁ and s₁₂ 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 <= k₁
variant2 >= k₁ and <= k₂
(s₁₃/8) + (s₂₃/4) + (s₃₃/4) + (s₄₃/8) + (s₅₃/8) should lie between [ (0.95/k₁) * (s₁₃ + s₂₃ + s₃₃+ s₄₃+ s₅₃), (1.05/k₁) * (s₁₃ + s₂₃ + s₃₃+ s₄₃+ s₅₃) ] (5% deviation)
where k₁, k₂, variant1 and variant2 are integers

Answer 1

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.