Finding the Minimum Potential Energy State by Adiabatic Parcel Rearrangements with a Nonlinear Equation of State: An Exact Solution in Polynomial Time

Abstract

The problem of finding the state of minimum potential energy through the rearrangement of water parcels with a nonlinear equation of state is discussed in the context of a combinatorial optimization problem. It is found that the problem is identical to a classical optimization problem called the linear assignment problem. This problem belongs to a problem class known as P, a class of problems that have known efficient solutions. This is very fortunate since this study’s problem has been suggested to be an asymmetric traveling salesman problem. A problem that belongs to a class called NP-hard, for which no efficient solutions are known. The difference between the linear assignment problem and the traveling salesman problem is discussed and made clear by looking at the different constraints used for the two problems. It is also shown how the rearrangement of water parcels that minimizes the potential energy can be found in polynomial time using the so-called Hungarian algorithm. The Hungarian algorithm is then applied to a simplified ocean stratification, and the result is compared to a few different approximate solutions to the minimization problem. It is found that the improved accuracy over the approximate methods comes at a high computational cost. Last, the algorithm is applied to a realistic ocean stratification using a technique that splits the minimization problem into smaller bits.