Cluster Optimization

Picture source: www.michael-noll.com

BY: OLIVER BASTERT

ORMS – APRIL 2014

Cluster optimization, or grouping like objects together, has hundreds of potential real-world applications, and for more than a decade professors Gritzmann and Brieden have been researching methods to extend the technology to a variety applications. A generalization of this particular approach has been applied, for example, to matching up available airplanes with cargo shipments, a logistical nightmare. Determining the most profitable insurance premiums is another challenge where these techniques can be applied. Cluster optimization also can helps insurance companies reasonably spread risk across groups by determining a profitable premium rate. This is the crucial decision point that determines whether the insurance company makes money.

By the same token, solving land consolidation challenges can mean economic life or death for rural regions. One of the problems is that farmers will often have multiple lots that are distributed not adjacent and connected, which wastes their resources and also prohibits them from using large machinery to farm the land. There is huge economic value in consolidating farmers’ lots into larger, connected plots. The Bavarian farmland problem may sound like a straightforward one to solve, almost like assembling a jigsaw puzzle – but it isn’t. Farmers can’t solve the challenges themselves and they often have conflicts with neighboring farmers going back hundreds of years that make simple land exchanges difficult.

To solve that problem, The Munich researchers used extremely advanced mathematical methods to solve this geometry problem – turning small, scattered farmland plots into larger groupings. They started with a mixed – integer programming formulation that included multiple constraints, such that each farmer would have the overall same quality and amount of land as before. The challenging part to state as a constraint was that each farmer’s lots should be connected. The shape of the land mattered too – a square or round shape is more economical to work than a long string of lots. To solve this, the researchers allocated each farmer a center point and would then build the farmer’s fields around that, using a very rigid mathematical formulation to find the optimal solution. However, this is a real-world problem so the mathematically pure solution was not always practical. The process required room to include additional constraints, and to make the solution feasible, the researchers went to Bavarian villagers and presented their work as a game. First, they would have the farmers exchange fields with buddies to consolidate their land. Then the researchers presented the optimal solution worked out in FICO Xpress Optimization Suite, using a visual interface that worked like a colored map. The optimal solution was never perfect, so the researchers factored in the complaints and requests for different swaps as new constraints, then optimized again. The iterative approach not only worked – the researchers and farmers thought it was fun.

One key lesson learned from the Bavarian farmland experience is that stakeholders must use the analytics for the process to work. “Playful analytics: was absolutely necessary to get buy-in and show that they created the solution; it wasn’t being imposed on them. The work done by researchers represents a mix of a good mathematical solution and a good practical solution. The potential cost savings for just the state of Bavaria are €150 million per year. Optimization has always been a research-intensive endeavor. That’s why companies such as FICO work closely with leading academic institutions to push the envelope of innovation to create better tools and better solution. And another lesson from that problem is cluster optimization can be a key part of the solution and companies will rely on their academic partners to delve deep into complex problems and identify the winning formulas for success