What Do Gas Prices and Bridge Collapses Have in Common?

by Asteroide Santana

Perhaps you’ve heard about the dramatic collapse of the First Tacoma Narrows Bridge in 1940, just a few months after its inauguration. This turned out to be a watershed moment in civil engineering: after its collapse, the postmortem investigation yielded sophisticated, significantly improved models that described how similar constructions behaved under varying physical conditions.

In order to be accurate, however, engineers are faced with a difficult task: with the model in front of them, they build the structure. But the material used can never be the exact one assumed in the model. The engineers must take the measurements directly after the structure is built and update the model to learn exactly how the actual structure will behave under different conditions.

Part of this necessary updating process, called finite element model updating problem, requires a solution to a complicated set of equations. In practice, this set of equations doesn’t admit an exact solution due to the unavoidable inaccuracy of measurements; however, a solution of some kind is still required to maximize safety. The only alternative is to convert the problem (solving the set of equations) into an optimization problem that aims to find the best approximate solution.

Consider another real-world problem with me, one that happens to be a recurring issue in any supply chain: how do you send commodities from their origin to their destination at minimum cost? This is not an easy task, as specific requirements, including capacity and demand constraints, must be satisfied.

In the oil industry, where commodities are petroleum products, such as gasoline and diesel, this problem is particularly difficult to solve. Before the final products arrive at their final destination, crude oil from different refineries is mixed together into large tanks called pools. The composition of the mixture in the pools dictates the quality and cost of the final product. However, finding an optimal composition for each pool is a well-known and challenging optimization problem called The Pooling Problem (which actually finds application in several fields other than the oil industry now).

The BBP

Although these two problems belong to completely different fields of application, from a mathematical point of view, they are precisely the same! In fact, both of these problems are instances of a Bipartite Bilinear Program (BBP). This is an optimization problem that has two disjoint sets of decision variables. The problem becomes linear in the variables from one set whenever we fix all the variables from the other set. Another important real-world problem that is also a BBP instance can be found here. But this example is slightly different from the previous two because it involves binary variables.

BBPs belong to the class of non-convex optimization problems. This means that it’s very hard to solve (actually NP-hard, for those familiar with the computational complexity theory). It’s often easy to find a feasible solution for a BBP (i.e., a solution that satisfies all the restrictions of the problem). The challenge, though, is to make sure that the solution we have found is indeed the best solution we can possibly have. If the objective is to minimize cost while shipping commodities, how can we guarantee that another feasible solution does not exist which might lead to a much lower cost?

The Math

Now we’ve come to the fun part: using abstract math to explore this problem. This figure illustrates what can happen when you try to minimize a convex function vs. a non-convex function.

Function f is convex and admits a global optimal solution that algorithms can easily identify — the solution a in this case. Function g, on the other hand, is non-convex and has two local solutions, namely, b and c. Optimization algorithms often get “trapped” at solution c without knowing that a better solution b even exists. In this figure, we can see right away that c is not the global optimal solution. However, in higher dimensional space, i.e., when g is a function of several variables as it happens in practice, visualization is not an option. Yet, thousands of local solutions like c might exist.

My PhD adviser and I wrote a paper proposing a branch-and-bound algorithm to get around the issue continually trapped in the local solutions of BBPs. Our computational experiments on ten instances of the civil engineering application described above demonstrates that our method performs 81% better than the state-of-the-art comercial solver BARON for such problems.

The next figure gives a rough idea of a branch-and-bound algorithm for solving continuous non-convex optimization problems. First we “relax” the problem by approximating (bounding) g with a convex function h. Then we branch (partition) the domain and repeat.

There are two challenges here: finding convex functions h that well approximate the non-convex function g; and finding good points to branch the domain at. If your convexification and branching procedures work well, after a few iterations you may have approximated the hard non-convex problem by a number of easy convex sub-problems.

In Summary

We saw two problems that, at first, seemed completely unrelated: a finite element model updating problem and a difficult pooling problem. These turned out to be two instances of the same abstract mathematical model, a BBP. We then learned why non-convexity makes it hard to solve optimization problems and how we can use other abstract math concepts, such as convex relaxations and branch-and-bound schemes, to overcome the challenge of solving BBPs. The success of our computational experiments illustrates the power of using math abstraction to solve a variety of complex real-world problems.

People often say mathematics is like poetry, and it’s true. Both math and poetry share a particular beauty, grounded in abstraction. And yet, we’ve seen that abstraction not only makes math beautiful, it also makes it useful.

If you liked this blog post, check out our work, follow us on social media or join us for our free monthly Academy webinars.