skip to main content


Title: Bounded Continuous-Time Satisfiability Solver
To tackle problems that can not be solved by current digital computers, many systems propose ideas from physics and neuroscience. The CTDS solver introduced by Ercsey-Ravasz and Toroczkai is one of such system. It solves the satisfiability problem by reducing it to a minimization of a time-varying target function. Although the possibility of an efficient electric circuit implementation of the solver has been shown, in terms of physical realizations, the solver has a problem of unbounded variations of the target function parameters. Here we propose a variant of the solver with bounded target function parameters. It includes several possible modifications of the solver in system parameter differences. We also show the basic characteristics of the solver, the upper and lower bounds of the target function parameters.  more » « less
Award ID(s):
1644368 1640081
NSF-PAR ID:
10163758
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
International Symposium on Nonlinear Theory and its Applications (NOLTA2019)
Page Range / eLocation ID:
436--439
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. To tackle problems that can not be solved by current digital computers, many systems propose ideas from physics and neuroscience. The CTDS solver introduced by Ercsey-Ravasz and Toroczkai is one of such system. It solves the satisfiability problem by reducing it to a minimization of a time-varying target function. Although the possibility of an efficient electric circuit implementation of the solver has been shown, in terms of physical realizations, the solver has a problem of unbounded variations of the target function parameters. Here we propose a variant of the solver with bounded target function parameters. It includes several possible modifications of the solver in system parameter differences. We also show the basic characteristics of the solver, the upper and lower bounds of the target function parameters. 
    more » « less
  2. Abstract

    We demonstrate the design of resonating structures using a density-based topology optimization approach, which requires the eigenfrequencies to match a set of target values. To develop a solution, several optimization modules are implemented, including material interpolation models, penalization schemes, filters, analytical sensitivities, and a solver. Moreover, common challenges in topology optimization for dynamic systems and their solutions are discussed. In this study, the objective function is to minimize the error between the target and actual eigenfrequency values. The finite element method is used to compute the eigenfrequencies at each iteration. To solve the optimization problem, we use the sequential linear programming algorithm with move limits, enhanced by a filtering technique. Finally, we present a resonator design as a case study and analyze the design process with different optimization parameters.

     
    more » « less
  3. The promise of self-assembly to enable the bottom-up formation of materials with prescribed architectures and functions has driven intensive efforts to uncover rational design principles for maximizing the yield of a target structure. Yet, despite many successful examples of self-assembly, ensuring kinetic accessibility of the target structure remains an unsolved problem in many systems. In particular, long-lived kinetic traps can result in assembly times that vastly exceed experimentally accessible timescales. One proposed solution is to design non-equilibrium assembly protocols in which system parameters change over time to avoid such kinetic traps. Here, we develop a framework to combine Markov state model (MSM) analysis with optimal control theory to compute a time-dependent protocol that maximizes the yield of the target structure at a finite time. We present an adjoint-based gradient descent method that, in conjunction with MSMs for a system as a function of its control parameters, enables efficiently optimizing the assembly protocol. We also describe an interpolation approach to significantly reduce the number of simulations required to construct the MSMs. We demonstrate our approach with two examples; a simple semi-analytic model for the folding of a polymer of colloidal particles, and a more complex model for capsid assembly. Our results show that optimizing time-dependent protocols can achieve significant improvements in the yields of selected structures, including equilibrium free energy minima, long-lived metastable structures, and transient states.

     
    more » « less
  4. Appeared in the proceedings of the 2021 IFAC Workshop on Time-Delay Systems This paper establishes a PIE (Partial Integral Equation)-based technique for the robust stability and H∞ performance analysis of linear systems with interval delays. The delays considered are time-invariant but uncertain, residing within a bounded interval excluding zero. We first propose a structured class of PIE systems with parametric uncertainty, then propose a Linear PI Inequality (LPI) for robust stability and H∞ performance of PIEs with polytopic uncertainty. Next, we consider the problem of robust stability and H∞ performance of multidelay systems with interval uncertainty in the delay parameters and show this problem is equivalent to robust stability and performance of a given PIE with parametric uncertainty. The robust stability and H∞ performance of the uncertain time-delay system are then solved using the LPI solver in the MATLAB PIETOOLS toolbox. Numerical examples are given to prove the effectiveness and accuracy of the method. This paper adds to the expanding field of PIE approach and can be extended to linear partial differential equations. 
    more » « less
  5. The “asymmetry” between spatiotemporally varying passenger demand and fixed-capacity transportation supply has been a long-standing problem in urban mass transportation (UMT) systems around the world. The emerging modular autonomous vehicle (MAV) technology offers us an opportunity to close the substantial gap between passenger demand and vehicle capacity through station-wise docking and undocking operations. However, there still lacks an appropriate approach that can solve the operational design problem for UMT corridor systems with MAVs efficiently. To bridge this methodological gap, this paper proposes a continuum approximation (CA) model that can offer near-optimal solutions to the operational design for MAV-based transit corridors very efficiently. We investigate the theoretical properties of the optimal solutions to the investigated problem in a certain (yet not uncommon) case. These theoretical properties allow us to estimate the seat demand of each time neighborhood with the arrival demand curves, which recover the “local impact” property of the investigated problem. With the property, a CA model is properly formulated to decompose the original problem into a finite number of subproblems that can be analytically solved. A discretization heuristic is then proposed to convert the analytical solution from the CA model to feasible solutions to the original problem. With two sets of numerical experiments, we show that the proposed CA model can achieve near-optimal solutions (with gaps less than 4% for most cases) to the investigated problem in almost no time (less than 10 ms) for large-scale instances with a wide range of parameter settings (a commercial solver may even not obtain a feasible solution in several hours). The theoretical properties are verified, and managerial insights regarding how input parameters affect system performance are provided through these numerical results. Additionally, results also reveal that, although the CA model does not incorporate vehicle repositioning decisions, the timetabling decisions obtained by solving the CA model can be easily applied to obtain near-optimal repositioning decisions (with gaps less than 5% in most instances) very efficiently (within 10 ms). Thus, the proposed CA model provides a foundation for developing solution approaches for other problems (e.g., MAV repositioning) with more complex system operation constraints whose exact optimal solution can hardly be found with discrete modeling methods. 
    more » « less