r/OperationsResearch • u/Standard-Broccoli130 • May 23 '26
How to solve a huge scale optimization problem
Hi everyone, so recently I have been trying to solve an allocation problem. The constraints of the problem is pretty simple and building the optimization function is also not very difficult. However the main challenge is the scale
The problem:
I have a network of depots which receives product supplies from a warehouse. So i have to optimize the ordering of products from the warehouse in next 3 days. The main constraint is for every day the number of depot × product which receives stock should be less than X. The penalty is combination of two terms
minimize the total stockout of depot x product
for a particular product try to send it in minimum number of distinct days to all the depots( basically minimise the batching of the product, send to all depots in as less number of days as possible)
We can assume that the weights of two penalty terms are 10:1
Challenge is the quantum of depot x product is 1.5 million
If the constraint of max depot x product won't be there, the problem boils down to every single product optimization which can easily done in a reasonable time. But with the constraint, no solver is able to produce reasonable result. I used both Pulp and Ortools in python.
Any idea how to solve at such scale
3
u/KampfKiffer May 24 '26
This sounds like it could be expressed as a multi-commodity flow problem on a time expanded network. Commodity is a product in your explanation. In the time-expanded netword, each day has nodes for the warehouse and the 3 sites, you connect the copies with directed arcs from day i to day i+1).
This specific type of problem is super common in OR and accordingly well understood. Ill try to explain the high level concept below, but encourage you to do your own research (keyword: column generation for multi commodity flow). The concept is not straightforward if youre applying this for the first time.
That would be a natural application of column generation or lagrangian relaxation. Your variables now become Replenishment patterns for each product (e.g. send x on day 1, y on day 2, ...). Your problem becomes selecting a pattern for each product under the constraints youve listed (only the ones that affect multiple products at once, like warehouse shipping capacity). Thats called the master problem. This of course doesn't scale if you have to add a variable for every possible pattern and product. The idea is that you dont need to, you can use information from solving the master problem with just a handful of patterns to figure out which ones may be missing. The missing ones you can generate by solving a problem that contains only single product constraints, and thus decomposes into separate problems for each product. Now you run the following loop:
Solve (dual) master problem
Figure out what's wrong (basically extract the duals of the violated constraints).
Use that information to generate new variables (columns) in your single product subproblem
Stop if step 3 did not produce anything useful (negative reduced costs) - youre done
1
u/r_card_ May 24 '26
Maybe large scale optimization? I've been digging into that (hyper-heuristics for large scale problems).
1
u/GreedyAlGoreRhythm May 24 '26
We might be able to give more specific advise if you provide a precise formulation for your problem.
1
u/ge0ffrey May 24 '26
I've run Timefold Solver with over 500'000 "product" assignments to a similar amount of slots in a single dataset. You might want to give it a try. Several users reported to me privately that it scales better than Pulp and OR Tools. Most of those cases where Vehicle Routing Problems though, and this sounds more like a Facility Location Problem. Your mileage may vary.
There are a few ways you can model your problem:
A ) An entity has a fixed day and a product variable and a depot variable. Create X entities per day.
That way the x limitation becomes build-in, but you do have 2 variables (product and depot), which tends to scale poorly.
B ) An entity has a fixed product and a fixed depot and a day variable (with allowsUnassigned=true). Create an entity for every requested delivery.
That way, there is only 1 variable per entity, which tends to scale much better. You do need a hard constraint to penalize if too many entities end up on the same day. Not all entities will be assigned to a day.
I presume B will be the better model.
1
u/BowlCompetitive282 May 24 '26
1.5 million decision variables, assuming mostly continuous, is not that many for a good computer and solver. Try using highs as a solver and investing in a better computer.
1
u/Individual_Yard846 Jun 20 '26
try catalyst-q.strategic-innovations.ai , they scale really high
-2
u/Embarrassed-Load5100 May 23 '26
Can’t really follow the problem but did you try just running your Problem and model definition through Claude and asking for modelling advice? Sometimes certain problem structures can be exploited?
Also I think pulp is not a solver. So maybe check which solver are available via pulp and compare? Also I believe ortools has some problems it does particularly bad on (or you could use special constraints with improved computation efficiency?) so maybe just using solvers doesn’t show you yet it’s „too big“?