Show simple item record

dc.contributor.advisorKianfar, Kiavash
dc.creatorLuo, Haochen
dc.date.accessioned2020-08-26T18:54:34Z
dc.date.available2020-08-26T18:54:34Z
dc.date.created2019-12
dc.date.issued2019-10-21
dc.date.submittedDecember 2019
dc.identifier.urihttps://hdl.handle.net/1969.1/188770
dc.description.abstractIn this dissertation, we develop new methodologies and algorithms to solve the multi-module (survivable) network design problem. Many real-world decision-making problems can be modeled as network design problems, especially on networks with capacity requirements on arcs or edges. In most cases, network design problems of this type that have been studied involve different types of capacity sizes (modules), and we call them the multi-module capacitated network design (MMND) problem. MMND problems arise in various industrial applications, such as transportation, telecommunication, power grid, data centers, and oil production, among many others. In the first part of the dissertation, we study the polyhedral structure of the MMND problem. We summarize current literature on polyhedral study of MMND, which generates the family of the so-called cutset inequalities based on the traditional mixed integer rounding (MIR). We then introduce a new family of inequalities for MMND based on the so-called n-step MIR, and show that various classes of cutset inequalities in the literature are special cases of these inequalities. We do so by studying a mixed integer set, the cutset polyhedron, which is closely related to MMND. We We also study the strength of this family of inequalities by providing some facet-defining conditions. These inequalities are then tested on MMND instances, and our computational results show that these classes of inequalities are very effective for solving MMND problems. Generalizations of these inequalities for some variants of MMND are also discussed. Network design problems have many generalizations depending on the application. In the second part of the dissertation, we study a highly applicable form of SND, referred to as multi-module SND (MM-SND), in which transmission capacities on edges can be sum of integer multiples of differently sized capacity modules. For the first time, we formulate MM-SND as a mixed integer program (MIP) using preconfigured-cycles (p-cycles) to reroute flow on failed edges. We derive several classes of valid inequalities for this MIP, and show that the valid inequalities previously developed in the literature for single-module SND are special cases of our inequalities. Furthermore, we show that our valid inequalities are facet-defining for MM-SND in many cases. Our computational results, using a heuristic separation algorithm, show that these inequalities are very effective in solving MM-SND. In particular they are more effective than compared to using single-module inequalities alone. Lastly, we generalize the inequalities for MMND for other mixed integer sets relaxed from MMND and the cutset polyhedron. These inequalities also generalize several valid inequalities in the literature. We conclude the dissertation by summarizing the work and pointing out potential directions for future research.en
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.subjectmixed-integer programmingen
dc.subjectnetwork designen
dc.subjectcutset inequalitiesen
dc.subjectvalid inequalitiesen
dc.subjectn-step MIRen
dc.titleValid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem
dc.typeThesisen
thesis.degree.departmentIndustrial and Systems Engineeringen
thesis.degree.disciplineIndustrial Engineeringen
thesis.degree.grantorTexas A&M Universityen
thesis.degree.nameDoctor of Philosophyen
thesis.degree.levelDoctoralen
dc.contributor.committeeMemberButenko, Sergiy
dc.contributor.committeeMemberMoreno-Centeno, Erick
dc.contributor.committeeMemberChen, Jianer
dc.type.materialtexten
dc.date.updated2020-08-26T18:54:34Z
local.etdauthor.orcid0000-0002-8846-527X


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record