I am working two create a new set of constraints, which I've discovered are non-convex. These are derived from a problem such that given two populations, each with a defined subset, ensure that items picked from each subset are within a specified percentage of their respective superset, e.g. maximum difference between (sum(PopSubA) / sum(PopA)) and (sum(PopSubB) / sum(PopB)) would be 0.10 or 10%.
After some work and a few iterations, I was able to discover a handful of ways to formulate this into a set of constraints that involved minimal quadratic terms - declare a variable within the model to act as a target percentage, which yields the non-convex constraints. The formulation with a maximum range of 10%:
sum(popSubA) <= sum(popA) * (target + 5%)
sum(popSubA) >= sum(popA) * (target - 5%)
sum(popSubB) <= sum(popB) * (target + 5%)
sum(popSubB) >= sum(popB) * (target - 5%)
Note that all variables from popA and popB are binary integers to denote whether or not these are picked, and we have tried declaring target as an integer variable with bounds [5, 95], as well as a continuous variable with bounds [0.05, 0.95]
My original attempts to create the constraints involved a formula with large matrix multiplication:
sum(popSubA) * sum(popB) - sum(popSubB) * sum(popA) <= 0.10 * sum(popA) * sum(popB)
sum(popSubB) * sum(popA) - sum(popSubA) * sum(popB) <= 0.10 * sum(popA) * sum(popB)
I have not been able to find another way to maintain a percentage relationship between two groups in a non-convex way. Is there something I'm overlooking?
Thanks for any and all advice,
Trey
------------------------------
Trey Westrich
------------------------------