Decomposition methods for multi-horizon stochastic programming

Decomposition methods for multi-horizon stochastic programming | 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 Research Article Decomposition methods for multi-horizon stochastic programming Hongyu Zhang, Ignacio E. Grossmann, Asgeir Tomasgard This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-3258743/v2 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 10 May, 2024 Read the published version in Computational Management Science → Version 2 posted 3 You are reading this latest preprint version Show more versions Abstract Multi-horizon stochastic programming includes short-term and long-term uncertainty in investment planning problems more efficiently than traditional multi-stage stochastic programming. In this paper, we exploit the block separable structure of multi-horizon stochastic linear programming, and establish that it can be decomposed by Benders decomposition and Lagrangean decomposition. In addition, we propose parallel Lagrangean decomposition with primal reduction that, (1) solves the scenario subproblems in parallel, (2) reduces the primal problem by keeping one copy for each scenario group at each stage, and (3) solves the reduced primal problem in parallel. We apply the parallel Lagrangean decomposition with primal reduction, Lagrangean decomposition and Benders decomposition to solve a stochastic energy system investment planning problem. The computational results show that: (a) the Lagrangean type decomposition algorithms have better convergence at the first iterations to Benders decomposition, and (b) parallel Lagrangean decomposition with primal reduction is very efficient for solving multi-horizon stochastic programming problems. Based on the computational results, the choice of algorithms for multi-horizon stochastic programming is discussed. Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 10 May, 2024 Read the published version in Computational Management Science → Version 2 posted Editorial decision: Accepted 06 Mar, 2024 Submission checks completed at journal 05 Mar, 2024 First submitted to journal 02 Mar, 2024 You are reading this latest preprint version Show more versions 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-3258743","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":276470679,"identity":"786fd3ed-6fef-438a-80ee-913b15602da2","order_by":0,"name":"Hongyu Zhang","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA0ElEQVRIiWNgGAWjYBACAxTGB5K1MM5A8InUwsxDjBZz9t7Dr3nbGOzN2c8efm2740+ewQHegw/wabHsOZdmDdTCbNmTl2ade8ag2OAAXzJeuwxu5JgZA7WwGRwAMnLbDBI3HOAxkyBGC4/B+TdmxpZEajF+DNQiAWYwEqXlzBkzxjnnJAwMbrwxY+xtM06ceZjHGL9fjvcYf3hTZmNvcD7H+MPPNrnEvuM9hg/waQECNikeBrBL2CDuYSagHqTk4w8og6j0MgpGwSgYBSMPAACBaEbMxOVEHgAAAABJRU5ErkJggg==","orcid":"","institution":"Norwegian University of Science and Technology","correspondingAuthor":true,"prefix":"","firstName":"Hongyu","middleName":"","lastName":"Zhang","suffix":""},{"id":276470680,"identity":"9ece787d-eab3-4035-869e-1927cdc2a37c","order_by":1,"name":"Ignacio E. Grossmann","email":"","orcid":"","institution":"Carnegie Mellon University","correspondingAuthor":false,"prefix":"","firstName":"Ignacio","middleName":"E.","lastName":"Grossmann","suffix":""},{"id":276470681,"identity":"f5eeaa9a-5d24-457a-ad5e-5dd8c831120e","order_by":2,"name":"Asgeir Tomasgard","email":"","orcid":"","institution":"Norwegian University of Science and Technology","correspondingAuthor":false,"prefix":"","firstName":"Asgeir","middleName":"","lastName":"Tomasgard","suffix":""}],"badges":[],"createdAt":"2023-08-12 18:14:04","currentVersionCode":2,"declarations":"","doi":"10.21203/rs.3.rs-3258743/v2","doiUrl":"https://doi.org/10.21203/rs.3.rs-3258743/v2","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s10287-024-00509-y","type":"published","date":"2024-05-10T12:15:31+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":58861704,"identity":"4f85ef8d-0793-460a-ba46-6cbba6846e8c","added_by":"auto","created_at":"2024-06-22 12:15:37","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":865066,"visible":true,"origin":"","legend":"","description":"","filename":"decompositionMHSPrevisionr3codesubmitted.pdf","url":"https://assets-eu.researchsquare.com/files/rs-3258743/v2_covered_e312207b-b1f7-435c-8d25-12b2a586e6a5.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Decomposition methods for multi-horizon stochastic programming","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":"computational-management-science","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Computational Management Science](https://www.springer.com/journal/10287)","snPcode":"10287","submissionUrl":"https://submission.nature.com/new-submission/10287/3","title":"Computational Management Science","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"","lastPublishedDoi":"10.21203/rs.3.rs-3258743/v2","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-3258743/v2","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Multi-horizon stochastic programming includes short-term and long-term uncertainty in investment planning problems more efficiently than traditional multi-stage stochastic programming. In this paper, we exploit the block separable structure of multi-horizon stochastic linear programming, and establish that it can be decomposed by Benders decomposition and Lagrangean decomposition. In addition, we propose parallel Lagrangean decomposition with primal reduction that, (1) solves the scenario subproblems in parallel, (2) reduces the primal problem by keeping one copy for each scenario group at each stage, and (3) solves the reduced primal problem in parallel. We apply the parallel Lagrangean decomposition with primal reduction, Lagrangean decomposition and Benders decomposition to solve a stochastic energy system investment planning problem. The computational results show that: (a) the Lagrangean type decomposition algorithms have better convergence at the first iterations to Benders decomposition, and (b) parallel Lagrangean decomposition with primal reduction is very efficient for solving multi-horizon stochastic programming problems. Based on the computational results, the choice of algorithms for multi-horizon stochastic programming is discussed.","manuscriptTitle":"Decomposition methods for multi-horizon stochastic programming","msid":"","msnumber":"","nonDraftVersions":[{"code":2,"date":"2024-03-05 18:26:33","doi":"10.21203/rs.3.rs-3258743/v2","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Accepted","date":"2024-03-06T10:20:44+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-03-05T09:51:01+00:00","index":"","fulltext":""},{"type":"submitted","content":"Computational Management Science","date":"2024-03-02T17:53:56+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"computational-management-science","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Computational Management Science](https://www.springer.com/journal/10287)","snPcode":"10287","submissionUrl":"https://submission.nature.com/new-submission/10287/3","title":"Computational Management Science","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}},{"code":"","date":"2024-02-27 16:08:26","doi":"","editorialEvents":[{"type":"decision","content":"Revision requested","date":"2024-02-28T22:54:33+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-02-28T04:02:38+00:00","index":"","fulltext":""},{"type":"submitted","content":"Computational Management Science","date":"2024-02-27T15:29:58+00:00","index":"","fulltext":""},{"type":"notPreprinted","content":""}],"status":"timeline","journal":{"display":true,"email":"[email protected]","identity":"computational-management-science","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Computational Management Science](https://www.springer.com/journal/10287)","snPcode":"10287","submissionUrl":"https://submission.nature.com/new-submission/10287/3","title":"Computational Management Science","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}},{"code":"","date":"2023-12-31 13:59:14","doi":"","editorialEvents":[{"type":"decision","content":"Revision requested","date":"2024-02-14T22:27:02+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-01-16T08:15:45+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"72d0f6de-68c9-4e7b-a9af-8ddb5d77b054","date":"2024-01-08T06:06:32+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-01-07T22:43:30+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-01-03T02:24:11+00:00","index":"","fulltext":""},{"type":"submitted","content":"Computational Management Science","date":"2023-12-31T13:57:10+00:00","index":"","fulltext":""},{"type":"notPreprinted","content":""}],"status":"timeline","journal":{"display":true,"email":"[email protected]","identity":"computational-management-science","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Computational Management Science](https://www.springer.com/journal/10287)","snPcode":"10287","submissionUrl":"https://submission.nature.com/new-submission/10287/3","title":"Computational Management Science","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}},{"code":1,"date":"2023-08-18 04:09:36","doi":"10.21203/rs.3.rs-3258743/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2023-12-21T21:14:48+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2023-09-05T08:42:37+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"72d0f6de-68c9-4e7b-a9af-8ddb5d77b054","date":"2023-08-17T02:15:55+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2023-08-15T20:35:40+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2023-08-15T06:08:35+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2023-08-14T01:36:54+00:00","index":"","fulltext":""},{"type":"submitted","content":"Computational Management Science","date":"2023-08-12T17:59:04+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"computational-management-science","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Computational Management Science](https://www.springer.com/journal/10287)","snPcode":"10287","submissionUrl":"https://submission.nature.com/new-submission/10287/3","title":"Computational Management Science","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"f1d40778-9321-49ad-9719-59c718a0a647","owner":[],"postedDate":"March 5th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2024-06-22T12:15:31+00:00","versionOfRecord":{"articleIdentity":"rs-3258743","link":"https://doi.org/10.1007/s10287-024-00509-y","journal":{"identity":"computational-management-science","isVorOnly":false,"title":"Computational Management Science"},"publishedOn":"2024-05-10 12:15:31","publishedOnDateReadable":"May 10th, 2024"},"versionCreatedAt":"2024-03-05 18:26:33","video":"","vorDoi":"10.1007/s10287-024-00509-y","vorDoiUrl":"https://doi.org/10.1007/s10287-024-00509-y","workflowStages":[]},"version":"v2","identity":"rs-3258743","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-3258743","identity":"rs-3258743","version":["v2"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}