Optimized Metaheuristic Tabu Search Algorithm (Instantiated for Bio-Conservation Networks and Groundwater Management)
Background NP-hard (nondeterministic polynomial-time hard) optimization problems are notoriously difficult. Finding an optimal solution requires an exponential amount of time; it is impossible to search through all combinations and permutations; and approximate algorithms may deliver extremely sub-optimal solutions. For many industries, this is more than just a mathematical inconvenience--it is a major setback in efficiency, productivity, and performance. (The classic example is the optimization problem of finding the least-cost route through all nodes of a weighted graph, commonly known as the Traveling Salesman Problem.Designing a conservation area network is an NP-hard problem. Planners must make difficult decisions about which land to purchase in order to preserve the broadest amount of biodiversity considering the spatial configuration as well as many biological, economic, and socio-political criteria. This requires efficient solutions to a complex multi-criteria optimization problem which could not be solved with previous methods.
Invention Description Building on twenty years of direct search methods in operations research, we have developed a modular generic software framework that combines creative new strategies with a metaheuristic algorithm to find fast efficient solutions to NP-hard problems. This flexible framework takes advantage of problem-specific knowledge, learns about the search space, and uses multiple processors to quickly find high quality solutions. This algorithm has been successfully demonstrated on mixed integer nonlinear programming problems.
An application of this powerful algorithm in conservation biology and groundwater management, ConsNet is a software tool for designing highly efficient conservation area networks which, based on several benchmarks, is the best available software for conservation needs.
Features
Modular generic software framework that combines creative new strategies with a metaheuristic algorithm Parallel algorithm takes advantage of multi-core processors Supports extremely large datasets and a variety of multi-criteria objectives
Market Potential/Applications Logistics, manufacturing, scheduling, network flows, bio-conservation agencies, land planners for renewable energy, industrial, and residential developers
Development Stage Beta product/commercial prototype
IP Status One U.S. patent application filed
UT Researcher J. Wesley Barnes, Ph.D., Mechanical Engineering, The University of Texas at Austin Michael Ciarleglio, ICEA/MATH, The University of Texas at Austin
Type of Offer: Licensing
« More Software Patents