How to model balancing of distribution of resources to different buckets?
ユーザーの入力を待っています。Hi, I'm trying to model the following problem as a MIP: trying to distribute limited supply to a few different destinations, with consideration for balancing, proportional to each destination's demand. I'd like to know how to model this behavior efficiently.
For example, I have 100 units of item to distribute to 3 destinations, each destination has 40, 60, 100 units of demand correspondingly. To achieve the ideal balancing, the optimal solution would give them 20, 30, 50 units correspondingly.
However, there may be other factors limiting how many units each destination can actually receive. For example, if the first country is limited to only receive 10 units max, then to achieve balancing, the optimal solution would become 10, 34, 56 units.
I have tried minimizing the "max ratio" of distribution over demand, and is working as intended. However, this involves ranking the 3 ratios, which led to a lot of helper variables and causing the scale to blow up. It often gets stuck trying to improve the bound.
With the example above, the ratios would be (10/40, 34/60, 56/100), where 34/60 is the max ratio value among the 3. Every other solution would be less optimal, because if we shuffle one unit to the 3rd country, becoming (10, 33, 57), then the largest ratio value would become 57/100, which is greater than 34/60, making a less desirable distribution.
Thanks a lot!
-
Hi,
Are there any other constraints/decisions involved? Otherwise I feel the non-MIP-approach might be sufficient:
- calculate the "unconstrained" solution, e.g. 20/30/50 by simple math
- see which assignments violate a local constraint (e.g. the first country can receive max 10)
- just fix those violating countries to their bound
- calculate the remaining capacity (90) and demand (60+100)
- divide the remaining capacity based on remaining demand (60*90/160 / 100*90/160)
If you're still curious how to formulate this as a MIP - consider using the Gurobi "general constraints" to define a variable holding the maximum ratio. So you would have variables for the absolute quantities for each country, as well as variables for the ratio supply/demand per country, and a single helper variable representing the maximum ratio over all countries. You would use addGenConstrMax() to link the ratio variables to the max-ratio variable.
Kind regards,
Ronald0 -
Thank you Ronald!
We do have some other constraints that makes a heuristic approach quite challenging to implement. For example we have constraints saying item A, B & C going to the same country needs to be of equal quantity, and also something like item X and item Y going to the same country needs to add up to (or be less than or equal to) a certain number (basically X & Y being mutually exclusive), etc.
Thanks for pointing us to addGenConstrMax() function! We are already using some max_() within our formulation.
What we've tried to do is minimizing the max_() of these ratios for each item. However, we've found edge cases that only looking at the 1st max couldn't handle. For example we have 1 item going to 3 countries J, K, L. If for some reason country J cannot receive fewer than a certain quantity, forcing their ratio to be very big (let's just say 100%), the process then basically stops balancing between the other two countries K and L, because the 2nd and 3rd largest ratios don't count towards the objective. Essentially we had to factor in the 2nd and 3rd largest ratios into account which really created a lot of trouble
0 -
Hi,
Ah, understood - then MIP becomes an attractive option.
Indeed addGenConstrMax() and max_() essentially provide the same functionality.
Would it be an option to try and minimize variability between the supply/demand ratios over all countries? In theory we want them to be close to totalSupply/totalDemand, so you could minimize the sum of squared differences between actualSupply[i]/actualDemand[i] and totalSupply/totalDemand across all countries i. Although this makes the model non-linear, Gurobi might be able to solve it without problems.
Kind regards,
Ronald0
サインインしてコメントを残してください。
コメント
3件のコメント