Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems

Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization 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 Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems Naoya Onizawa, Takahiro Hanyu This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-3353725/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 16 Jan, 2024 Read the published version in Scientific Reports → Version 1 posted 8 You are reading this latest preprint version Abstract This article critically investigates the limitations of the simulated annealing algorithm using probabilistic bits (pSA) in solving large-scale combinatorial optimization problems. The study begins with an in-depth analysis of the pSA process, focusing on the issues resulting from unexpected oscillations among p-bits. These oscillations hinder the energy reduction of the Ising model and thus obstruct the successful execution of pSA in complex tasks. Through detailed simulations, we unravel the root cause of this energy stagnation, identifying the feedback mechanism inherent to the pSA operation as the primary contributor to these disruptive oscillations. To address this challenge, we propose two novel algorithms, time average pSA (TApSA) and stalled pSA (SpSA). These algorithms are designed based on partial deactivation of p-bits and are thoroughly tested using Python simulations on maximum cut benchmarks that are typical combinatorial optimization problems. On the 16 benchmarks from 800 to 5,000 nodes, the proposed methods improve the normalized cut value from 0.8% to 98.4% on average in comparison with the conventional pSA. Physical sciences/Mathematics and computing/Computational science Physical sciences/Engineering/Electrical and electronic engineering Physical sciences/Nanoscience and technology/Nanoscale devices/Magnetic devices Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 16 Jan, 2024 Read the published version in Scientific Reports → Version 1 posted Editorial decision: Revision requested 02 Nov, 2023 Reviews received at journal 19 Oct, 2023 Reviewers agreed at journal 09 Oct, 2023 Reviewers invited by journal 22 Sep, 2023 Editor assigned by journal 16 Sep, 2023 Editor invited by journal 16 Sep, 2023 Submission checks completed at journal 16 Sep, 2023 First submitted to journal 13 Sep, 2023 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-3353725","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Article","associatedPublications":[],"authors":[{"id":234055211,"identity":"1ca00aff-8015-48ee-a615-df1e017c5692","order_by":0,"name":"Naoya Onizawa","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABJ0lEQVRIiWNgGAWjYDADNihd3w9mH4DwDIjRwjizjVgtMMC44RiSFmzAnP3wMYkfDDZ5fPyHnwEZdszG95uPPfhw5jADf/sBhuICTC2WPWlpkj0MacVsDMfMgIxkNrNjbOmGM24cZpA4k8BgPANTi8GBHDMJHobDiW2MDWY3eBiYecyO8ZhJ83w4zMBwg4HBmAeLlvNvzCT/gLQws3+7+YehXsK4DapFHpeWGzlABSAtbDxmt4EMAwM2kBagwwxwanmWbC1jkJbYxsNT/lvG4HiCxDGg72acSecxPJPYgNUv55MP3nxTYZM4v//4ZsM3FdUJ/M3AMPxwzFpO7vjhY8ZYQgwIWCQQMYYUdUAnMbYZY9XBwPwBuzhI6jFOqVEwCkbBKBhBAAAnC2CAQrQ1FgAAAABJRU5ErkJggg==","orcid":"","institution":"Tohoku University","correspondingAuthor":true,"prefix":"","firstName":"Naoya","middleName":"","lastName":"Onizawa","suffix":""},{"id":234055213,"identity":"ad92411c-7609-49bc-aeb3-6145239e622a","order_by":1,"name":"Takahiro Hanyu","email":"","orcid":"","institution":"Tohoku University","correspondingAuthor":false,"prefix":"","firstName":"Takahiro","middleName":"","lastName":"Hanyu","suffix":""}],"badges":[],"createdAt":"2023-09-14 03:29:16","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-3353725/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-3353725/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1038/s41598-024-51639-x","type":"published","date":"2024-01-16T15:00:33+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":49978556,"identity":"3aabd80b-1302-4a52-890c-018c3a62797c","added_by":"auto","created_at":"2024-01-22 15:06:34","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1993479,"visible":true,"origin":"","legend":"","description":"","filename":"main.pdf","url":"https://assets-eu.researchsquare.com/files/rs-3353725/v1_covered_a146b563-6979-44f2-9ee0-583b867a2f29.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"scientific-reports","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"scirep","sideBox":"Learn more about [Scientific Reports](http://www.nature.com/srep/)","snPcode":"","submissionUrl":"","title":"Scientific Reports","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Scientific Reports","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"","lastPublishedDoi":"10.21203/rs.3.rs-3353725/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-3353725/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"This article critically investigates the limitations of the simulated annealing algorithm using probabilistic bits (pSA) in solving large-scale combinatorial optimization problems. The study begins with an in-depth analysis of the pSA process, focusing on the issues resulting from unexpected oscillations among p-bits. These oscillations hinder the energy reduction of the Ising model and thus obstruct the successful execution of pSA in complex tasks. Through detailed simulations, we unravel the root cause of this energy stagnation, identifying the feedback mechanism inherent to the pSA operation as the primary contributor to these disruptive oscillations. To address this challenge, we propose two novel algorithms, time average pSA (TApSA) and stalled pSA (SpSA). These algorithms are designed based on partial deactivation of p-bits and are thoroughly tested using Python simulations on maximum cut benchmarks that are typical combinatorial optimization problems. On the 16 benchmarks from 800 to 5,000 nodes, the proposed methods improve the normalized cut value from 0.8% to 98.4% on average in comparison with the conventional pSA.","manuscriptTitle":"Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2023-09-22 03:52:16","doi":"10.21203/rs.3.rs-3353725/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2023-11-02T05:18:50+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2023-10-19T22:50:04+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"e80cf458-a415-40e3-855e-9099ca4f6ba4","date":"2023-10-09T17:26:44+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2023-09-22T17:40:53+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2023-09-16T12:43:55+00:00","index":"","fulltext":""},{"type":"editorInvited","content":"","date":"2023-09-16T12:41:26+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2023-09-16T12:37:39+00:00","index":"","fulltext":""},{"type":"submitted","content":"Scientific Reports","date":"2023-09-14T03:20:10+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"scientific-reports","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"scirep","sideBox":"Learn more about [Scientific Reports](http://www.nature.com/srep/)","snPcode":"","submissionUrl":"","title":"Scientific Reports","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Scientific Reports","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"e115964a-498f-4f13-8dac-f1dd016ab48e","owner":[],"postedDate":"September 22nd, 2023","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[{"id":24795453,"name":"Physical sciences/Mathematics and computing/Computational science"},{"id":24795454,"name":"Physical sciences/Engineering/Electrical and electronic engineering"},{"id":24795455,"name":"Physical sciences/Nanoscience and technology/Nanoscale devices/Magnetic devices"}],"tags":[],"updatedAt":"2024-01-22T15:02:30+00:00","versionOfRecord":{"articleIdentity":"rs-3353725","link":"https://doi.org/10.1038/s41598-024-51639-x","journal":{"identity":"scientific-reports","isVorOnly":false,"title":"Scientific Reports"},"publishedOn":"2024-01-16 15:00:33","publishedOnDateReadable":"January 16th, 2024"},"versionCreatedAt":"2023-09-22 03:52:16","video":"","vorDoi":"10.1038/s41598-024-51639-x","vorDoiUrl":"https://doi.org/10.1038/s41598-024-51639-x","workflowStages":[]},"version":"v1","identity":"rs-3353725","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-3353725","identity":"rs-3353725","version":["v1"]},"buildId":"_2-kVJe1T_tPrBINL-cwx","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}