Undercover Heuristic Solves the Case
Buses, mobile phones, football: we encounter integer optimization problems in situations where we least expect them. In order to find solutions to such problems, you need good intuition – and also a bit of luck. This feature explains in plain text how this works. It won (in a slightly modified form) the Klaus Tschira Award 2015 for Achievements in Public Understanding of Sciences – KlarText! [5].
Figure 1: Cutting complicated objects can make things simpler. © Klaus Tschira Stiftung gGmbH / © Dietmar Gust, http://www.gustfoto.de
It’s nice weather today and your favorite club is playing. You call your friends to arrange a meeting point and take the bus to the stadium. While having some cold drinks before kickoff, you discuss whether the roster of the upcoming opponent favors your club or not. You’re having a great day with mathematics.
Mathematics? Yes, because bus timetables, the allocation of mobile radio frequencies to cell towers, and scheduling of sport leagues, are all so-called "integer optimization problems." Such a problem consists of three basic components: an objective function, constraints, and the restriction to integer solution values. Let’s explain this using the examples provided above.
Figure 2: A mathematician searching for a good solution. © Klaus Tschira Stiftung gGmbH / © Dietmar Gust, http://www.gustfoto.de
Passengers like to have short transfer times; for mobile communication, there should be little interference between adjacent transmission towers; and in professional sports, the revenue from broadcasting rights should be maximized. That is the objective function: something you aim to shrink within the feasible options, or something you are trying to expand. The constraints determine what the feasible options are; that is, constraints are like rules that have to be observed in any case. Bus drivers have to take breaks; there are location restrictions for the placement of transmission towers; and for many leagues, home and away games have to alternate. Such constraints can be formulated as a mathematical equation system – just as we remember it from school, but much, much larger. Instead of two or three variables and equations, there are often hundreds of thousands. For these equations we would like to find the best possible solution (concerning the objective function). Finally, there is the restriction to whole numbers, or integers. Half a bus driver or two-thirds of a football team – that doesn’t work. Therefore, we need to find solutions that are in integers; hence, the variables take values such as zero, one, or two, but not five and three-sevenths.
When the mathematicians at ZIB are faced with a new optimization problem, there are two major steps to be taken. The first step is to set up a suitable model; that is, a system of equations. This usually happens by utilizing a blackboard and chalk – and a duster! What are the variables? Did we consider all the constraints, and does the objective really represent what we want? Write down, dust off, start again. When we have a good model, step two follows: finding a solution for this model. No blackboard in the world is big enough for such a calculation. Instead, this is accomplished with computer programs. And the good news is: a very large class of such models, so called integer optimization problems, can often be solved these days by extremely powerful black-box software, like the optimization toolkit SCIP, which has been developed at ZIB.
A PROGRAM THAT FINDS THE SOLUTION – THE HEURISTIC
The magic component of such a program is the one that finds the solution – the heuristic (from the Greek word "heuriskein." which means "to discover, to find"). Heuristics are methods that attempt to quickly construct a relatively good solution for a given problem, yet often do not find the best possible solution. One could say that heuristics are intelligent guessing methods.
Figure 3: Solutions can sometimes be found in strange places. © Michaela Keinert
Heuristic decisions for optimization problems – this sounds complicated, but we all know heuristics from our daily lives. Imagine, for example, that you would like to buy a new smartphone. Theoretically, you could try to get a complete market overview and compare all of the available brands, models, versions, and all offers with each other. However, no one would do this, because it would take forever. Your favorite would probably be out of stock when you finally made your decision. Instead, you proceed in a much more focused and intuitive manner. You analyze some particularly relevant information, a test report, for example. You compile a shortlist of eligible models that you compare in more detail. You purchase from the retailer who has always provided you with good advice. This is, more or less, how heuristics work. They collect statistics on which they base their decisions, try to fix a few variables, and recognize and exploit common patterns. Equation systems and the methods by which we solve them can often be interpreted and understood geometrically. Patterns can often be represented, moved, or divided geometrically. The set of feasible solutions of a system of equations might be a cube, a prism, a cone, or another solid. This object might be complex and multi-dimensional, but it is, literally, edgy. And at some point in this solid is the integer optimal solution that we are looking for. One new heuristic of this type, which has been developed at ZIB and which has a nice geometric interpretation, is called "Undercover"(FN:T.Berthold. Heuristic algorithms in global MINLP solvers. Doctoral thesis. Technische Universität Berlin, 2014, Isbn: 978-3-8439-1931-9.),(FN:T. Berthold, A- Gleixner. Undercover: a primal MINPL heuristic exploring a largest sub_MIP. Mathematical Programming 144 (1-2), 2014: 315-346.). It is based on the idea of finding an easy-to-handle solid within a much more complicated mathematical solid. Or to put it a different way: a huge, extremely hard system of equations is converted into a smaller system which is easier to solve.
Figure 4:A mathematician’s view of equation systems and algorithms: a curved solid (the solution space of a nonlinear optimization problem) and a straight, triangular, cut through it (the search space for the Undercover heuristic). ©Timo Berthold
Imagine a cylinder, or a solid in the shape of a tin can (see also Figure 1). If you cut a single, ultra-thin slice out of the cylinder, what do you get? Most people think of a circle, but that is not the only correct answer. If you cut through the cylinder along the height, then you get a rectangle as a cutting surface. The interesting part of this observation is that you have cut an object with straight sides from a round object with a single cut. In Figure 4, you can see a similar setup. The big, blue, "curved" object depicts the solution space of a nonlinear optimization problem. The Undercover heuristic restricts its search to the blue "straightly bounded" triangle, finding the solution corresponding to the yellow point A.
Mathematically, this cutting corresponds to the fixing of variables. The solid corresponds to the set of feasible solutions of an equation system. And interestingly, it is much easier to optimize over "straight-line-limited" objects than over curved objects. In math-speak: linear optimization is easier than non-linear. The Undercover heuristic proceeds exactly like this: determine the smallest possible set of variables of a given optimization problem that has to be fixed in order to obtain a simpler optimization problem. Then, solve this smaller problem. Any solution to it is a solution to the original problem, but not vice versa.
However, it may be that the optimal solution is not contained in our sub-problem, or worse that the sub-problem does not even have a feasible integer solution. After all, Undercover is just a heuristic. However, by an empirical analysis, three things could be demonstrated. First, it is often sufficient to fix relatively few variables to remove all non-linearities; that is, "straighten" the problem. Second, the resulting sub-problems can almost always be solved rapidly. Third, Undercover could find a feasible solution in more than half of the test cases. That’s a very good value for a single heuristic.
Figure 5: From an infeasible starting point (0,0,0), a candidate solution is shifted along different dimensions, making it feasible for more and more of the side constraints. In between, so-called “domain propagation” techniques are applied to deduce lower bounds on the variables. Finally, a feasible solution (2,2,1) is found. ©imo Berthold, Gregor Hendel
Heuristics like Undercover or Shift-and-Propagate, see Figure 5, are generic; that is, they are not about a very specific application, but about the mathematics that are intrinsic to planning and the optimization of processes [1],(FN:T. Berthold, G. Hendel. Shift-And-Propagate. Journal of Heuristics 21[1], 2015: 73-106.). As a consequence, such methods can be utilized by a lot of different applications, though mostly behind the scenes. The mixed integer programming solver SCIP, which implements the named heuristics, was developed in cooperation with Siemens AG, SAP SE, and Open Grid Europe GmbH in the MODAL SynLab (FN:MODAL SynLab. http://www.zib.de/projects/modal-synlab.). Methods developed at ZIB are nowadays employed by the three market leaders for mathematical optimization software – FICO Xpress, IBM Cplex, and Gurobi. As of today, such software is deployed in almost all blue-chip companies.
Final whistle. It was a really tight match with a well-earned win; that provides a nice buffer for the next few weeks. With your recently purchased smartphone, you check which bus is quickest for you. That’s the beauty of integer optimization. We use its results, without having to think about it. If we encounter it in everyday life, then the optimal solution has already been found, maybe by one of the heuristics that were developed by researchers at ZIB.
Figure 6: his text (with some small changes) won a Klaus Tschira Award 2015 for Achievements in Public Understanding of Sciences – KlarText!. (FN:T. Berthold. Gut geraten. bild der wissenschaft plus. Oktober 2015:6-9.), see also http://www.klaus-tschira-preis.info/. © Klaus Tschira Stiftung gGmbH
