Large Batch Sizes
JeanFrancoisPuget 2700028FGP Comments (2) Visits (8228)
John D. Cook's Small batch sizes and the subsequent Small batch sizes II made me think. I may have got it wrong, but Cook seems to support the view that doing things bit by bit is often better than doing them all at once in a large batch. This seems counterintuitive to someone used to mathematical optimization like me.
More precisely, Cook cites Don Reinertsen's keynote address at YOW 2012. Cook writes:
When applied to software development, I tend to agree. I have been using agile methodologies for quite a long time, and they are much better than the traditional waterfall model. In the latter, all development is done at once, before testing occurs. Defaults are detected way after they were put in the code, which results in lengthy, ineffective, debugging sessions. In agile methodologies, development is cut in small pieces, and each piece is tested before moving to the next one. Defaults are detected when the new code is fresh in the memory of developers, leading to short and effective debugging. This seems in line with the idea of small batch sizes advocated by Reinertsen.
What make me think is that in the world of mathematical optimization, the opposite seems right. It is often better to optimize globally a set of decisions than to make decisions one at a time.
I've blogged about two examples supporting this view. First, in a manufacturing environment, it is better to assign work in progress to machines globally instead of dealing with them one at a time. See the Simulation And Optimization Are Not The Same entry for more details. Second, the Decision Optimization entry shows that assigning commercial responses to customers one customer at a time leads to suboptimal outcome. It is much better to optimize assignments for all customers at once.
In these cases, large batch sizes are much better than small batch sizes. This contradicts Cook and Reinertsen. Since they are smart guys I was quite puzzled for a while, wondering how one could reconcile these two conflicting views.
Well, it also happens that it may be more effective to decompose an optimization problem into smaller pieces than to solve it at once. (Note that this is the strategy used by most MIP solvers in their branch and bound search: they recursively decompose the problem into smaller, disjoint, subproblems by fixing values for a given variable. ) There are many decomposition methods for optimization problems, and choosing the right one is itself an interesting problem. Some methods are ad hoc, some are quite generic like Benders or Dantzig-Wolfe. Decomposition methods deserve a longer treatment, and I'll defer it to another post.
Point is that it may be better to decompose a given optimization problem. Question remains:
When should one decompose a problem rather than try to solve it at once?
The short answer is when the problem is too complex for the solver you are using. Too complex usually means that your favorite solver does not come up with a good enough answer in the limited time you have fo solving the problem.
If you replace the software solver by a human you get this interesting analogy: one should decompose a task when it is too complex for a human being. I guess this is what the small batch size story is about.