| 1. |
|
|
| 2. |
|
|
| 3. |
|
|
| 4. |
|
|
| 5. |
- Fahimi, Z., et al.
(författare)
-
Combinatorial optimization by weight annealing in memristive hopfield networks
- 2021
-
Ingår i: Scientific Reports. - : Nature Portfolio. - 2045-2322. ; 11:1
-
Tidskriftsartikel (refereegranskat)abstract
- The increasing utility of specialized circuits and growing applications of optimization call for the development of efficient hardware accelerator for solving optimization problems. Hopfield neural network is a promising approach for solving combinatorial optimization problems due to the recent demonstrations of efficient mixed-signal implementation based on emerging non-volatile memory devices. Such mixed-signal accelerators also enable very efficient implementation of various annealing techniques, which are essential for finding optimal solutions. Here we propose a "weight annealing" approach, whose main idea is to ease convergence to the global minima by keeping the network close to its ground state. This is achieved by initially setting all synaptic weights to zero, thus ensuring a quick transition of the Hopfield network to its trivial global minima state and then gradually introducing weights during the annealing process. The extensive numerical simulations show that our approach leads to a better, on average, solutions for several representative combinatorial problems compared to prior Hopfield neural network solvers with chaotic or stochastic annealing. As a proof of concept, a 13-node graph partitioning problem and a 7-node maximum-weight independent set problem are solved experimentally using mixed-signal circuits based on, correspondingly, a 20 x 20 analog-grade TiO2 memristive crossbar and a 12 x 10 eFlash memory array.
|
|
| 6. |
- Golovin, Daniel, et al.
(författare)
-
Improved approximations for two-stage min-cut and shortest path problems under uncertainty
- 2015
-
Ingår i: Mathematical Programming. - : Springer Science and Business Media LLC. - 0025-5610 .- 1436-4646. ; 149:1, s. 167-194
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, we study the robust and stochastic versions of the two-stage min-cut and shortest path problems introduced in Dhamdhere et al. (in How to pay, come what may: approximation algorithms for demand-robust covering problems. In: FOCS, pp 367–378, 2005), and give approximation algorithms with improved approximation factors. Specifically, we give a 2-approximation for the robust min-cut problem and a 4-approximation for the stochastic version. For the two-stage shortest path problem, we give a 3.39'>3.39 3.39 -approximation for the robust version and 6.78'>6.78 6.78 -approximation for the stochastic version. Our results significantly improve the previous best approximation factors for the problems. In particular, we provide the first constant-factor approximation for the stochastic min-cut problem. Our algorithms are based on a guess and prune strategy that crucially exploits the nature of the robust and stochastic objective. In particular, we guess the worst-case second stage cost and based on the guess, select a subset of costly scenarios for the first-stage solution to address. The second-stage solution for any scenario is simply the min-cut (or shortest path) problem in the residual graph. The key contribution is to show that there is a near-optimal first-stage solution that completely satisfies the subset of costly scenarios that are selected by our procedure. While the guess and prune strategy is not directly applicable for the stochastic versions, we show that using a novel LP formulation, we can adapt a guess and prune algorithm for the stochastic versions. Our algorithms based on the guess and prune strategy provide insights about the applicability of this approach for more general robust and stochastic versions of combinatorial problems.
|
|
| 7. |
- Mahmoodi, M. R., et al.
(författare)
-
An Analog Neuro-Optimizer with Adaptable Annealing Based on 64x64 0T1R Crossbar Circuit
- 2019
-
Ingår i: 2019 IEEE INTERNATIONAL ELECTRON DEVICES MEETING (IEDM). - : IEEE. - 9781728140315
-
Konferensbidrag (refereegranskat)abstract
- We demonstrate an analog neuro-optimization hardware, suitable for solving a large number of combinatorial optimization problems, based on a crossbar circuit with 4096 passively-integrated analog-grade memristors. The proposed hardware supports a variety of metaheuristic techniques for improving optimization performance, such as stochastic and chaotic simulated annealing, and novel "exponential" annealing. The hardware operation is successfully tested by experimentally solving weighted graph partitioning, maximum clique, vertex cover, and independent set problems, and observing good agreement with simulation results.
|
|
