Timescales of Boolean satisfiability solver using continuous-time dynamical system

Abstract Various physical systems for solving combinatorial optimization problems have been proposed, and among them, the dynamical system recently proposed in [Ercsey-Ravasz & Toroczkai, 2011] to solve the satisfiability problem is also expected to perform well in a physical realization. This system improves the assignment by the gradient descent with respect to a target function, which is also changing in time. These two parts have their own timescales, and their balance can be considered to play an important role in finding a solution. In this paper, we develop a variant of the system, where the balance is explicitly represented by a parameter. Using the developed system, we propose a natural time measure for evaluation and show that with an appropriate choice of the relative timescale we can maximize the performance with respect to the proposed measure.

• Publication year

  2020

• Venue

  Communications in nonlinear science & numerical simulation

• Publication date

  2020-05-01

• Fields of study

  Physics, Computer Science

• Identifiers
  DOI 10.1016/j.cnsns.2020.105183
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A continuous-time MaxSAT solver with high analog performance

  2018cited by this paper
• Combinatorial optimization using dynamical phase transitions in driven-dissipative systems.

  2017cited by this paper
• Efficient Analog Circuits for Boolean Satisfiability

  2016cited by this paper
• A coherent Ising machine for 2000-node optimization problems

  2016cited by this paper
• 24.3 20k-spin Ising chip for combinational optimization problem with CMOS annealing

  2015cited by this paper
• Robust optimization with transiently chaotic dynamical systems

  2014cited by this paper
• Ising formulations of many NP problems

  2013cited by this paper
• Local search for Boolean Satisfiability with configuration checking and subscore

  2013cited by this paper
• The Chaos Within Sudoku

  2012cited by this paper
• Optimization hardness as transient chaos in an analog approach to constraint satisfaction

  2011cited by this paper
• Scaling and Probabilistic Smoothing: Efficient Dynamic Local Search for SAT

  2002cited by this paper
• A Discrete Lagrangian-Based Global-Search Method for Solving Satisfiability Problems

  1996cited by this paper
• Chaotic simulated annealing by a neural network model with transient chaos

  1995cited by this paper
• The Breakout Method for Escaping from Local Minima

  1993cited by this paper

• Conditional random k satisfiability modeling for k = 1, 2 (CRAN2SAT) with non-monotonic Smish activation function in discrete Hopfield neural network

  2024cites this paper
• Low-Rank Combinatorial Optimization and Statistical Learning by Spatial Photonic Ising Machine.

  2023cites this paper
• Spatial-photonic Boltzmann machines: low-rank combinatorial optimization and statistical learning by spatial light modulation

  2023cites this paper
• Accelerating numerical simulation of continuous-time Boolean satisfiability solver using discrete gradient

  2021cites this paper
• Amazon Employees Resources Access Data Extraction via Clonal Selection Algorithm and Logic Mining Approach

  2020cites this paper
• Bounded Continous-Time Satisfiability Solver

  2020influential citation
• A Systematic Review of Hyper-Heuristics on Combinatorial Optimization Problems

  2020cites this paper