{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/29700"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/29700","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Enabling massive parallelism for two-stage stochastic integer optimizations a branch and bound based approach","abstract":"DoD's transportation activities incur USD 11+Billion expenditure anually. Optimal resource allocation under uncertainty provides huge opportunity for improvement and commensurate cost savings. Stochastic optimization techniques are used to incorporate uncertainty in the data to arrive at robust resource allocations. The application of stochastic optimization extends to a broad range of areas ranging from finance to production to economics to energy systems planning. We study the DoD Air Mobility Command's airfleet assignment problem that schedules 1300+ aircrafts to deal with combat delivery, strategic airlift, air refueling, aeromedical evacuation operations, etc. around the world. Our formulation of the airfleet allocation problem for a smaller time horizon shows that annual average cost benefits of 3\\% can be obtained by using stochastic integer optimization. Despite the potential cost benefits, use of stochastic integer optimization has remained intractable because the computational complexity of the problem prevents rapid decisions. Modern supercomputers can attain performance of several petaflops and hence can enhance solution tractability for use in a highly dynamic decision environment. We start with a conventional parallel decomposition of the problem, analyze the challenges and address a number of performance optimizations like cut retirement and scenario clustering. We then present results from a novel branch-and-bound based design that converges to an optimal integer allocation for large problems while allowing evaluation of tens of thousands of possible scenarios. We believe that this is an interesting and uncommon approach to harnessing tera/petascale compute power for such problems without decomposing the linear programs further.","abstract_html":"DoD's transportation activities incur USD 11+Billion expenditure anually. Optimal resource allocation under uncertainty provides huge opportunity for improvement and commensurate cost savings. Stochastic optimization techniques are used to incorporate uncertainty in the data to arrive at robust resource allocations. The application of stochastic optimization extends to a broad range of areas ranging from finance to production to economics to energy systems planning. We study the DoD Air Mobility Command's airfleet assignment problem that schedules 1300+ aircrafts to deal with combat delivery, strategic airlift, air refueling, aeromedical evacuation operations, etc. around the world. Our formulation of the airfleet allocation problem for a smaller time horizon shows that annual average cost benefits of 3\\% can be obtained by using stochastic integer optimization. Despite the potential cost benefits, use of stochastic integer optimization has remained intractable because the computational complexity of the problem prevents rapid decisions. Modern supercomputers can attain performance of several petaflops and hence can enhance solution tractability for use in a highly dynamic decision environment. We start with a conventional parallel decomposition of the problem, analyze the challenges and address a number of performance optimizations like cut retirement and scenario clustering. We then present results from a novel branch-and-bound based design that converges to an optimal integer allocation for large problems while allowing evaluation of tens of thousands of possible scenarios. We believe that this is an interesting and uncommon approach to harnessing tera/petascale compute power for such problems without decomposing the linear programs further.","abstract_has_math":false,"creators":["Langer, Akhil"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Kale, Laxmikant V."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-02-06T20:11:49Z","date_published":"2012-02-06T20:11:49Z","updated_at":"2026-07-22T22:25:27Z","subjects":["High Performance Computing (HPC)","Stochastic Optimization","Parallel Computing","Branch-and-bound","Integer Programming","Aircraft Allocation"],"languages":["en"],"rights":["Copyright 2011 Akhil Langer"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/29700","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kale, Laxmikant V."]},{"key":"dc:creator","label":"Author","values":["Langer, Akhil"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-02-06T20:11:49Z","2011-12"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation / Thesis","text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"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":["High Performance Computing (HPC)","Stochastic Optimization","Parallel Computing","Branch-and-bound","Integer Programming","Aircraft Allocation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 Akhil Langer"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/29700"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["DoD's transportation activities incur USD 11+Billion expenditure anually. Optimal resource allocation under uncertainty provides huge opportunity for improvement and commensurate cost savings. Stochastic optimization techniques are used to incorporate uncertainty in the data to arrive at robust resource allocations. The application of stochastic optimization extends to a broad range of areas ranging from finance to production to economics to energy systems planning. We study the DoD Air Mobility Command's airfleet assignment problem that schedules 1300+ aircrafts to deal with combat delivery, strategic airlift, air refueling, aeromedical evacuation operations, etc. around the world. Our formulation of the airfleet allocation problem for a smaller time horizon shows that annual average cost benefits of 3\\% can be obtained by using stochastic integer optimization. Despite the potential cost benefits, use of stochastic integer optimization has remained intractable because the computational complexity of the problem prevents rapid decisions. Modern supercomputers can attain performance of several petaflops and hence can enhance solution tractability for use in a highly dynamic decision environment. We start with a conventional parallel decomposition of the problem, analyze the challenges and address a number of performance optimizations like cut retirement and scenario clustering. We then present results from a novel branch-and-bound based design that converges to an optimal integer allocation for large problems while allowing evaluation of tens of thousands of possible scenarios. We believe that this is an interesting and uncommon approach to harnessing tera/petascale compute power for such problems without decomposing the linear programs further.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-12-07T20:30:51Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 3 Langer_Akhil.pdf: 1970096 bytes, checksum: 72e8f6f45621e9a9a10b68369a9b4544 (MD5) Langer_Akhil.pdf: 1968291 bytes, checksum: 03236ea9b1910918af458d81bb89fd2e (MD5) Langer_Akhil.pdf: 1970043 bytes, checksum: b1caca86b4386e2bfc7e9ec795f92997 (MD5)","Made available in DSpace on 2012-02-06T20:11:49Z (GMT). No. of bitstreams: 2 Langer_Akhil.pdf: 1970043 bytes, checksum: b1caca86b4386e2bfc7e9ec795f92997 (MD5) license.txt: 4061 bytes, checksum: fb6f6101022b63d1e8cc52c40498a6f6 (MD5)"]},{"key":"dc:title","label":"Title","values":["Enabling massive parallelism for two-stage stochastic integer optimizations a branch and bound based approach"]}]}],"canonical_facts":{"dc:contributor":["Kale, Laxmikant V."],"dc:creator":["Langer, Akhil"],"dc:date":["2012-02-06T20:11:49Z","2011-12"],"dc:description":["DoD's transportation activities incur USD 11+Billion expenditure anually. Optimal resource allocation under uncertainty provides huge opportunity for improvement and commensurate cost savings. Stochastic optimization techniques are used to incorporate uncertainty in the data to arrive at robust resource allocations. The application of stochastic optimization extends to a broad range of areas ranging from finance to production to economics to energy systems planning. We study the DoD Air Mobility Command's airfleet assignment problem that schedules 1300+ aircrafts to deal with combat delivery, strategic airlift, air refueling, aeromedical evacuation operations, etc. around the world. Our formulation of the airfleet allocation problem for a smaller time horizon shows that annual average cost benefits of 3\\% can be obtained by using stochastic integer optimization. Despite the potential cost benefits, use of stochastic integer optimization has remained intractable because the computational complexity of the problem prevents rapid decisions. Modern supercomputers can attain performance of several petaflops and hence can enhance solution tractability for use in a highly dynamic decision environment. We start with a conventional parallel decomposition of the problem, analyze the challenges and address a number of performance optimizations like cut retirement and scenario clustering. We then present results from a novel branch-and-bound based design that converges to an optimal integer allocation for large problems while allowing evaluation of tens of thousands of possible scenarios. We believe that this is an interesting and uncommon approach to harnessing tera/petascale compute power for such problems without decomposing the linear programs further.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-12-07T20:30:51Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 3 Langer_Akhil.pdf: 1970096 bytes, checksum: 72e8f6f45621e9a9a10b68369a9b4544 (MD5) Langer_Akhil.pdf: 1968291 bytes, checksum: 03236ea9b1910918af458d81bb89fd2e (MD5) Langer_Akhil.pdf: 1970043 bytes, checksum: b1caca86b4386e2bfc7e9ec795f92997 (MD5)","Made available in DSpace on 2012-02-06T20:11:49Z (GMT). No. of bitstreams: 2 Langer_Akhil.pdf: 1970043 bytes, checksum: b1caca86b4386e2bfc7e9ec795f92997 (MD5) license.txt: 4061 bytes, checksum: fb6f6101022b63d1e8cc52c40498a6f6 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/29700"],"dc:language":["en"],"dc:rights":["Copyright 2011 Akhil Langer"],"dc:subject":["High Performance Computing (HPC)","Stochastic Optimization","Parallel Computing","Branch-and-bound","Integer Programming","Aircraft Allocation"],"dc:title":["Enabling massive parallelism for two-stage stochastic integer optimizations a branch and bound based approach"],"dc:type":["Dissertation / Thesis","text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:27Z"}