Change search
ReferencesLink to record
Permanent link

Direct link
Finding the Minimum Potential Energy State by Adiabatic Parcel Rearrangements with a Nonlinear Equation of State: An Exact Solution in Polynomial Time
Stockholm University, Faculty of Science, Department of Meteorology .
Number of Authors: 2
2015 (English)In: Journal of Physical Oceanography, ISSN 0022-3670, Vol. 45, no 7, 1843-1857 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2015. Vol. 45, no 7, 1843-1857 p.
National Category
Oceanography, Hydrology, Water Resources
URN: urn:nbn:se:su:diva-119741DOI: 10.1175/JPO-D-14-0174.1ISI: 000357994200005OAI: diva2:849228
Available from: 2015-08-27 Created: 2015-08-24 Last updated: 2015-08-27Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Nycander, Jonas
By organisation
Department of Meteorology
In the same journal
Journal of Physical Oceanography
Oceanography, Hydrology, Water Resources

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 120 hits
ReferencesLink to record
Permanent link

Direct link