Evidence of Exponential Speed-Up in the Solution of Hard Optimization Problems
Optimization problems pervade essentially every scientific discipline and industry. A common form requires identifying a solution satisfying the maximum number among a set of many conflicting constraints. Often, these problems are particularly difficult to solve, requiring resources that grow expone...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2018-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2018/7982851 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832553552670621696 |
|---|---|
| author | Fabio L. Traversa Pietro Cicotti Forrest Sheldon Massimiliano Di Ventra |
| author_facet | Fabio L. Traversa Pietro Cicotti Forrest Sheldon Massimiliano Di Ventra |
| author_sort | Fabio L. Traversa |
| collection | DOAJ |
| description | Optimization problems pervade essentially every scientific discipline and industry. A common form requires identifying a solution satisfying the maximum number among a set of many conflicting constraints. Often, these problems are particularly difficult to solve, requiring resources that grow exponentially with the size of the problem. Over the past decades, research has focused on developing heuristic approaches that attempt to find an approximation to the solution. However, despite numerous research efforts, in many cases even approximations to the optimal solution are hard to find, as the computational time for further refining a candidate solution also grows exponentially with input size. In this paper, we show a noncombinatorial approach to hard optimization problems that achieves an exponential speed-up and finds better approximations than the current state of the art. First, we map the optimization problem into a Boolean circuit made of specially designed, self-organizing logic gates, which can be built with (nonquantum) electronic elements with memory. The equilibrium points of the circuit represent the approximation to the problem at hand. Then, we solve its associated nonlinear ordinary differential equations numerically, towards the equilibrium points. We demonstrate this exponential gain by comparing a sequential MATLAB implementation of our solver with the winners of the 2016 Max-SAT competition on a variety of hard optimization instances. We show empirical evidence that our solver scales linearly with the size of the problem, both in time and memory, and argue that this property derives from the collective behavior of the simulated physical circuit. Our approach can be applied to other types of optimization problems, and the results presented here have far-reaching consequences in many fields. |
| format | Article |
| id | doaj-art-7066cf9345f14227b6881417b4292550 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2018-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-7066cf9345f14227b6881417b42925502025-02-03T05:53:47ZengWileyComplexity1076-27871099-05262018-01-01201810.1155/2018/79828517982851Evidence of Exponential Speed-Up in the Solution of Hard Optimization ProblemsFabio L. Traversa0Pietro Cicotti1Forrest Sheldon2Massimiliano Di Ventra3MemComputing Inc., San Diego, CA 92130, USASan Diego Supercomputer Center, La Jolla, CA 92093, USADepartment of Physics, University of California, La Jolla, San Diego, CA 92093, USADepartment of Physics, University of California, La Jolla, San Diego, CA 92093, USAOptimization problems pervade essentially every scientific discipline and industry. A common form requires identifying a solution satisfying the maximum number among a set of many conflicting constraints. Often, these problems are particularly difficult to solve, requiring resources that grow exponentially with the size of the problem. Over the past decades, research has focused on developing heuristic approaches that attempt to find an approximation to the solution. However, despite numerous research efforts, in many cases even approximations to the optimal solution are hard to find, as the computational time for further refining a candidate solution also grows exponentially with input size. In this paper, we show a noncombinatorial approach to hard optimization problems that achieves an exponential speed-up and finds better approximations than the current state of the art. First, we map the optimization problem into a Boolean circuit made of specially designed, self-organizing logic gates, which can be built with (nonquantum) electronic elements with memory. The equilibrium points of the circuit represent the approximation to the problem at hand. Then, we solve its associated nonlinear ordinary differential equations numerically, towards the equilibrium points. We demonstrate this exponential gain by comparing a sequential MATLAB implementation of our solver with the winners of the 2016 Max-SAT competition on a variety of hard optimization instances. We show empirical evidence that our solver scales linearly with the size of the problem, both in time and memory, and argue that this property derives from the collective behavior of the simulated physical circuit. Our approach can be applied to other types of optimization problems, and the results presented here have far-reaching consequences in many fields.http://dx.doi.org/10.1155/2018/7982851 |
| spellingShingle | Fabio L. Traversa Pietro Cicotti Forrest Sheldon Massimiliano Di Ventra Evidence of Exponential Speed-Up in the Solution of Hard Optimization Problems Complexity |
| title | Evidence of Exponential Speed-Up in the Solution of Hard Optimization Problems |
| title_full | Evidence of Exponential Speed-Up in the Solution of Hard Optimization Problems |
| title_fullStr | Evidence of Exponential Speed-Up in the Solution of Hard Optimization Problems |
| title_full_unstemmed | Evidence of Exponential Speed-Up in the Solution of Hard Optimization Problems |
| title_short | Evidence of Exponential Speed-Up in the Solution of Hard Optimization Problems |
| title_sort | evidence of exponential speed up in the solution of hard optimization problems |
| url | http://dx.doi.org/10.1155/2018/7982851 |
| work_keys_str_mv | AT fabioltraversa evidenceofexponentialspeedupinthesolutionofhardoptimizationproblems AT pietrocicotti evidenceofexponentialspeedupinthesolutionofhardoptimizationproblems AT forrestsheldon evidenceofexponentialspeedupinthesolutionofhardoptimizationproblems AT massimilianodiventra evidenceofexponentialspeedupinthesolutionofhardoptimizationproblems |