Hardware Acceleration of Simulated Annealing for Constraint Satisfaction Problems

Hardware Acceleration of Simulated Annealing for Constraint Satisfaction Problems | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Article Hardware Acceleration of Simulated Annealing for Constraint Satisfaction Problems Saptarshi Das, Andrew Pannone, Rishikesh Nair, Pranav Krishnan, and 5 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7171868/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted You are reading this latest preprint version Abstract Combinatorial optimization of a discrete system with an arbitrary set of constraints is a computationally intensive task typically solved by search algorithms that iteratively explore the solution space. Simulated annealing (SA), a metaheuristic algorithm inspired by physical annealing processes, solves this class of problems by performing a stochastic search wherein thermally modulated acceptance criteria enable probabilistic transitions across high-energy states. This allows the system to escape local minima and progressively converge toward a global optimum, even within complex and non-convex solution landscapes. In this work, we present the hardware acceleration of SA for spatial optimization under constrained environments, specifically targeting drone placement for maximum coverage while avoiding no-fly zones. Stochasticity is introduced through a true random number generator based on two-dimensional (2D) materials, which initializes the system states and drives probabilistic transitions. The system energy is evaluated using a Boolean logic circuit, wherein the acceptance of candidate solutions is governed by a programmable 2D circuit with tunable threshold behavior. This hardware implementation achieves an 1800-fold acceleration compared to exhaustive brute-force trials. Furthermore, simulations of the annealing accelerator reveal that the degree of search acceleration scales favorably with both system size and agent count, demonstrating enhanced efficiency in larger and more complex configurations. This work also underscores the potential of 2D-material-enabled stochastic and programmable hardware for real-time constrained optimization. Physical sciences/Materials science/Materials for devices/Electronic devices Physical sciences/Materials science/Nanoscale materials/Two-dimensional materials Full Text Additional Declarations There is NO Competing Interest. Cite Share Download PDF Status: Under Review Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-7171868","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Article","associatedPublications":[],"authors":[{"id":498421841,"identity":"d89db1c3-87f0-4e57-a89a-20d42b957751","order_by":0,"name":"Saptarshi Das","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAArklEQVRIiWNgGAWjYHAC8x8JFRCWBLFaDCQ+nCFVi+TMNlK0yM9I3mDMO++OvcEB5oO3eYiy4kZaQTLvtmeJGw6wJVsTp0Uix+Aw77bDCQYHeMykidIiPyPHsJl3zmGgw/i/EaeF4UaOMePMhsOMGw7wsBGnxeDMszKGD8eeJc48zGZsOYcoh7Unb2NIqLljz3e8+eGNN0Q5DAIOMDAwk6AcqmUUjIJRMApGAS4AAFpXMvwkPbDZAAAAAElFTkSuQmCC","orcid":"https://orcid.org/0000-0002-0188-945X","institution":"Penn State University","correspondingAuthor":true,"prefix":"","firstName":"Saptarshi","middleName":"","lastName":"Das","suffix":""},{"id":498421842,"identity":"670e60f5-8c1c-4dad-9129-f612fa9edc2d","order_by":1,"name":"Andrew Pannone","email":"","orcid":"https://orcid.org/0000-0001-8446-9946","institution":"Pennsylvania State University","correspondingAuthor":false,"prefix":"","firstName":"Andrew","middleName":"","lastName":"Pannone","suffix":""},{"id":498421843,"identity":"c0952d4d-c07e-4dd6-aad8-725bb6b4bb49","order_by":2,"name":"Rishikesh Nair","email":"","orcid":"","institution":"Penn State University","correspondingAuthor":false,"prefix":"","firstName":"Rishikesh","middleName":"","lastName":"Nair","suffix":""},{"id":498421844,"identity":"c2733c0e-2cfe-4805-9c44-d5a9dde0e7f4","order_by":3,"name":"Pranav Krishnan","email":"","orcid":"","institution":"Penn State University","correspondingAuthor":false,"prefix":"","firstName":"Pranav","middleName":"","lastName":"Krishnan","suffix":""},{"id":498421845,"identity":"17878be0-4261-4848-b8df-5625afbad6ce","order_by":4,"name":"Harikrishnan Ravichandran","email":"","orcid":"https://orcid.org/0009-0002-2230-370X","institution":"Pennsylvania State University","correspondingAuthor":false,"prefix":"","firstName":"Harikrishnan","middleName":"","lastName":"Ravichandran","suffix":""},{"id":498421846,"identity":"104b9f31-063d-4727-b45d-1c331429df42","order_by":5,"name":"Arav Dutta","email":"","orcid":"","institution":"Penn State University","correspondingAuthor":false,"prefix":"","firstName":"Arav","middleName":"","lastName":"Dutta","suffix":""},{"id":498421847,"identity":"f48d1a66-7b84-4bbd-8dd8-36fd0c4021ac","order_by":6,"name":"Subir Ghosh","email":"","orcid":"https://orcid.org/0000-0002-0883-4478","institution":"The Pennsylvenia State University","correspondingAuthor":false,"prefix":"","firstName":"Subir","middleName":"","lastName":"Ghosh","suffix":""},{"id":498421848,"identity":"5fa3130e-0642-4633-8128-a430f7c13067","order_by":7,"name":"Chen Chen","email":"","orcid":"","institution":"Pennsylvania State University","correspondingAuthor":false,"prefix":"","firstName":"Chen","middleName":"","lastName":"Chen","suffix":""},{"id":498421849,"identity":"823f9565-f630-44aa-9cd7-a506d0651941","order_by":8,"name":"Joan Redwing","email":"","orcid":"https://orcid.org/0000-0002-7906-452X","institution":"The Pennsylvania State University","correspondingAuthor":false,"prefix":"","firstName":"Joan","middleName":"","lastName":"Redwing","suffix":""}],"badges":[],"createdAt":"2025-07-20 22:10:19","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7171868/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7171868/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":90868717,"identity":"8b2b627c-d1b5-4a0a-8364-c007371ba55d","added_by":"auto","created_at":"2025-09-09 07:51:47","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":2649278,"visible":true,"origin":"","legend":"Article File","description":"","filename":"Manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7171868/v1_covered_717ff4ad-3da1-476a-a0fd-47665fc70906.pdf"}],"financialInterests":"There is \u003cb\u003eNO\u003c/b\u003e Competing Interest.","formattedTitle":"Hardware Acceleration of Simulated Annealing for Constraint Satisfaction Problems","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"nature-portfolio","isNatureJournal":true,"hasQc":false,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"","title":"Nature Portfolio","twitterHandle":"","acdcEnabled":false,"dfaEnabled":false,"editorialSystem":"ejp","reportingPortfolio":"","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"","lastPublishedDoi":"10.21203/rs.3.rs-7171868/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7171868/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eCombinatorial optimization of a discrete system with an arbitrary set of constraints is a computationally intensive task typically solved by search algorithms that iteratively explore the solution space. Simulated annealing (SA), a metaheuristic algorithm inspired by physical annealing processes, solves this class of problems by performing a stochastic search wherein thermally modulated acceptance criteria enable probabilistic transitions across high-energy states. This allows the system to escape local minima and progressively converge toward a global optimum, even within complex and non-convex solution landscapes. In this work, we present the hardware acceleration of SA for spatial optimization under constrained environments, specifically targeting drone placement for maximum coverage while avoiding no-fly zones. Stochasticity is introduced through a true random number generator based on two-dimensional (2D) materials, which initializes the system states and drives probabilistic transitions. The system energy is evaluated using a Boolean logic circuit, wherein the acceptance of candidate solutions is governed by a programmable 2D circuit with tunable threshold behavior. This hardware implementation achieves an 1800-fold acceleration compared to exhaustive brute-force trials. Furthermore, simulations of the annealing accelerator reveal that the degree of search acceleration scales favorably with both system size and agent count, demonstrating enhanced efficiency in larger and more complex configurations. This work also underscores the potential of 2D-material-enabled stochastic and programmable hardware for real-time constrained optimization.\u003c/p\u003e","manuscriptTitle":"Hardware Acceleration of Simulated Annealing for Constraint Satisfaction Problems","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-09-09 07:43:38","doi":"10.21203/rs.3.rs-7171868/v1","editorialEvents":[],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"nature-communications","isNatureJournal":true,"hasQc":false,"allowDirectSubmit":false,"externalIdentity":"NCOMMS","sideBox":"Learn more about [Nature Communications](http://www.nature.com/ncomms/)","snPcode":"","submissionUrl":"https://mts-ncomms.nature.com/","title":"Nature Communications","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"ejp","reportingPortfolio":"Nature Communications","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"1c1c78fa-bddd-4c45-8af7-c2783248d6d8","owner":[],"postedDate":"September 9th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[{"id":52935774,"name":"Physical sciences/Materials science/Materials for devices/Electronic devices"},{"id":52935775,"name":"Physical sciences/Materials science/Nanoscale materials/Two-dimensional materials"}],"tags":[],"updatedAt":"2025-09-09T07:43:38+00:00","versionOfRecord":[],"versionCreatedAt":"2025-09-09 07:43:38","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7171868","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7171868","identity":"rs-7171868","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}