{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/88050"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/88050","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Parallel algorithms for two-stage stochastic optimization","abstract":"We develop scalable algorithms for two-stage stochastic program optimizations. We propose performance optimizations such as cut-window mechanism in Stage 1 and scenario clustering in Stage 2 of benders method for solving two-stage stochastic programs. A naive implementation of benders method has slow convergence rate and does not scale well to large number of processors especially when the problem size is large and/or there are integer variables in Stage 1. Parallelization of stochastic integer programs pose very unique characteristics that make them very challenging to parallelize. We develop a Parallel Stochastic Integer Program Solver (PSIPS) that exploits nested parallelism by exploring the branch-and-bound tree vertices in parallel along with scenario parallelization. PSIPS has been shown to have high parallel efficiency of greater than 40% at 120 cores which is significantly greater than the parallel efficiency of state-of-the-art mixed-integer program solvers. A significant portion of the time in this branch-and-bound solver is spent in optimizing the stochastic linear program at the root vertex. Stochastic linear programs at other vertices of the branch-and-bound tree take very less iterations to converge because they can inherit benders cut from their parent vertices and/or the root. Therefore, it is important to reduce the optimization time of the stochastic linear program at the root vertex. We propose two decomposition schemes namely the Split-and-Merge (SAM) method and the Lagrangian Decomposition and Merge (LDAM) method that significantly increase the convergence rate of benders decomposition. SAM method gives up to 64% reduction in solution time while also giving significantly higher parallel speedups as compared to the naive benders method. LDAM method, on the other hand, has made it possible to solve otherwise intractable stochastic programs. We further provide a computational engine for many real-time and dynamic problems faced by US Air Mobility Command. We first propose a stochastic programming solution to the military aircraft allocation problem with consideration for disaster management. Then, we study US AMC's dynamic mission re-planning problem and propose a mathematical formulation that is computationally feasible and leads to significant savings in cost as compared to myopic and deterministic optimization. It is expected that this work will provide the springboard for more robust problem solving with HPC in many logistics and planning problems.","abstract_html":"We develop scalable algorithms for two-stage stochastic program optimizations. We propose performance optimizations such as cut-window mechanism in Stage 1 and scenario clustering in Stage 2 of benders method for solving two-stage stochastic programs. A naive implementation of benders method has slow convergence rate and does not scale well to large number of processors especially when the problem size is large and/or there are integer variables in Stage 1. Parallelization of stochastic integer programs pose very unique characteristics that make them very challenging to parallelize. We develop a Parallel Stochastic Integer Program Solver (PSIPS) that exploits nested parallelism by exploring the branch-and-bound tree vertices in parallel along with scenario parallelization. PSIPS has been shown to have high parallel efficiency of greater than 40% at 120 cores which is significantly greater than the parallel efficiency of state-of-the-art mixed-integer program solvers. A significant portion of the time in this branch-and-bound solver is spent in optimizing the stochastic linear program at the root vertex. Stochastic linear programs at other vertices of the branch-and-bound tree take very less iterations to converge because they can inherit benders cut from their parent vertices and/or the root. Therefore, it is important to reduce the optimization time of the stochastic linear program at the root vertex. We propose two decomposition schemes namely the Split-and-Merge (SAM) method and the Lagrangian Decomposition and Merge (LDAM) method that significantly increase the convergence rate of benders decomposition. SAM method gives up to 64% reduction in solution time while also giving significantly higher parallel speedups as compared to the naive benders method. LDAM method, on the other hand, has made it possible to solve otherwise intractable stochastic programs. We further provide a computational engine for many real-time and dynamic problems faced by US Air Mobility Command. We first propose a stochastic programming solution to the military aircraft allocation problem with consideration for disaster management. Then, we study US AMC's dynamic mission re-planning problem and propose a mathematical formulation that is computationally feasible and leads to significant savings in cost as compared to myopic and deterministic optimization. It is expected that this work will provide the springboard for more robust problem solving with HPC in many logistics and planning problems.","abstract_has_math":false,"creators":["Langer, Akhil"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Kale, Laxmikant V.","Palekar, Udatta","Padua, David A.","Rutenbar, Rob","Baker, Steven"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-29T20:38:28Z","date_published":"2015-09-29T20:38:28Z","updated_at":"2026-07-22T22:26:31Z","subjects":["Stochastic Optimization","Integer Program Optimization","Benders Decomposition","Lagrangian Decomposition","Parallel Computing","High Performance Computing (HPC)","Branch-and-bound","Resource Allocation","Large Scale Optimization","Air Mobility Command","Dynamic Mission Replanning","Aircraft Allocation","Itinerary Selection","Military Airlift Planning"],"languages":["en"],"rights":["Copyright 2015 Akhil Langer"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/88050","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kale, Laxmikant V.","Palekar, Udatta","Padua, David A.","Rutenbar, Rob","Baker, Steven"]},{"key":"dc:creator","label":"Author","values":["Langer, Akhil"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-29T20:38:28Z","2015-08","2015-07-17","2015-8"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Stochastic Optimization","Integer Program Optimization","Benders Decomposition","Lagrangian Decomposition","Parallel Computing","High Performance Computing (HPC)","Branch-and-bound","Resource Allocation","Large Scale Optimization","Air Mobility Command","Dynamic Mission Replanning","Aircraft Allocation","Itinerary Selection","Military Airlift Planning"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 Akhil Langer"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/88050"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We develop scalable algorithms for two-stage stochastic program optimizations. We propose performance optimizations such as cut-window mechanism in Stage 1 and scenario clustering in Stage 2 of benders method for solving two-stage stochastic programs. A naive implementation of benders method has slow convergence rate and does not scale well to large number of processors especially when the problem size is large and/or there are integer variables in Stage 1. Parallelization of stochastic integer programs pose very unique characteristics that make them very challenging to parallelize. We develop a Parallel Stochastic Integer Program Solver (PSIPS) that exploits nested parallelism by exploring the branch-and-bound tree vertices in parallel along with scenario parallelization. PSIPS has been shown to have high parallel efficiency of greater than 40% at 120 cores which is significantly greater than the parallel efficiency of state-of-the-art mixed-integer program solvers. A significant portion of the time in this branch-and-bound solver is spent in optimizing the stochastic linear program at the root vertex. Stochastic linear programs at other vertices of the branch-and-bound tree take very less iterations to converge because they can inherit benders cut from their parent vertices and/or the root. Therefore, it is important to reduce the optimization time of the stochastic linear program at the root vertex. We propose two decomposition schemes namely the Split-and-Merge (SAM) method and the Lagrangian Decomposition and Merge (LDAM) method that significantly increase the convergence rate of benders decomposition. SAM method gives up to 64% reduction in solution time while also giving significantly higher parallel speedups as compared to the naive benders method. LDAM method, on the other hand, has made it possible to solve otherwise intractable stochastic programs. We further provide a computational engine for many real-time and dynamic problems faced by US Air Mobility Command. We first propose a stochastic programming solution to the military aircraft allocation problem with consideration for disaster management. Then, we study US AMC's dynamic mission re-planning problem and propose a mathematical formulation that is computationally feasible and leads to significant savings in cost as compared to myopic and deterministic optimization. It is expected that this work will provide the springboard for more robust problem solving with HPC in many logistics and planning problems.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2015-09-29 without embargo terms","The student, Akhil Langer, accepted the attached license on 2015-07-15 at 02:22.","The student, Akhil Langer, submitted this Dissertation for approval on 2015-07-15 at 15:56.","This Dissertation was approved for publication on 2015-07-17 at 07:27.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8472 on 2015-09-29 at 13:22:52","Made available in DSpace on 2015-09-29T20:38:28Z (GMT). No. of bitstreams: 2 LANGER-DISSERTATION-2015.pdf: 4682445 bytes, checksum: 028b60a2d9a067e3d74b70915e14938c (MD5) LICENSE.txt: 4209 bytes, checksum: ebdc22c756a4f70ada945c3ab7a6c478 (MD5) Previous issue date: 2015-07-17"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Parallel algorithms for two-stage stochastic optimization"]}]}],"canonical_facts":{"dc:contributor":["Kale, Laxmikant V.","Palekar, Udatta","Padua, David A.","Rutenbar, Rob","Baker, Steven"],"dc:creator":["Langer, Akhil"],"dc:date":["2015-09-29T20:38:28Z","2015-08","2015-07-17","2015-8"],"dc:description":["We develop scalable algorithms for two-stage stochastic program optimizations. We propose performance optimizations such as cut-window mechanism in Stage 1 and scenario clustering in Stage 2 of benders method for solving two-stage stochastic programs. A naive implementation of benders method has slow convergence rate and does not scale well to large number of processors especially when the problem size is large and/or there are integer variables in Stage 1. Parallelization of stochastic integer programs pose very unique characteristics that make them very challenging to parallelize. We develop a Parallel Stochastic Integer Program Solver (PSIPS) that exploits nested parallelism by exploring the branch-and-bound tree vertices in parallel along with scenario parallelization. PSIPS has been shown to have high parallel efficiency of greater than 40% at 120 cores which is significantly greater than the parallel efficiency of state-of-the-art mixed-integer program solvers. A significant portion of the time in this branch-and-bound solver is spent in optimizing the stochastic linear program at the root vertex. Stochastic linear programs at other vertices of the branch-and-bound tree take very less iterations to converge because they can inherit benders cut from their parent vertices and/or the root. Therefore, it is important to reduce the optimization time of the stochastic linear program at the root vertex. We propose two decomposition schemes namely the Split-and-Merge (SAM) method and the Lagrangian Decomposition and Merge (LDAM) method that significantly increase the convergence rate of benders decomposition. SAM method gives up to 64% reduction in solution time while also giving significantly higher parallel speedups as compared to the naive benders method. LDAM method, on the other hand, has made it possible to solve otherwise intractable stochastic programs. We further provide a computational engine for many real-time and dynamic problems faced by US Air Mobility Command. We first propose a stochastic programming solution to the military aircraft allocation problem with consideration for disaster management. Then, we study US AMC's dynamic mission re-planning problem and propose a mathematical formulation that is computationally feasible and leads to significant savings in cost as compared to myopic and deterministic optimization. It is expected that this work will provide the springboard for more robust problem solving with HPC in many logistics and planning problems.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2015-09-29 without embargo terms","The student, Akhil Langer, accepted the attached license on 2015-07-15 at 02:22.","The student, Akhil Langer, submitted this Dissertation for approval on 2015-07-15 at 15:56.","This Dissertation was approved for publication on 2015-07-17 at 07:27.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8472 on 2015-09-29 at 13:22:52","Made available in DSpace on 2015-09-29T20:38:28Z (GMT). No. of bitstreams: 2 LANGER-DISSERTATION-2015.pdf: 4682445 bytes, checksum: 028b60a2d9a067e3d74b70915e14938c (MD5) LICENSE.txt: 4209 bytes, checksum: ebdc22c756a4f70ada945c3ab7a6c478 (MD5) Previous issue date: 2015-07-17"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/88050"],"dc:language":["en"],"dc:rights":["Copyright 2015 Akhil Langer"],"dc:subject":["Stochastic Optimization","Integer Program Optimization","Benders Decomposition","Lagrangian Decomposition","Parallel Computing","High Performance Computing (HPC)","Branch-and-bound","Resource Allocation","Large Scale Optimization","Air Mobility Command","Dynamic Mission Replanning","Aircraft Allocation","Itinerary Selection","Military Airlift Planning"],"dc:title":["Parallel algorithms for two-stage stochastic optimization"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:31Z"}