Advanced search options

Sorted by: relevance · author · university · date | New search

Dates: Last 2 Years ^{❌}

You searched for `subject:(Cutset)`

.
Showing records 1 – 2 of
2 total matches.

▼ Search Limiters

Texas A&M University

1. Luo, Haochen. Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem.

Degree: PhD, Industrial Engineering, 2019, Texas A&M University

URL: http://hdl.handle.net/1969.1/188770

In 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.
*Advisors/Committee Members: Kianfar, Kiavash (advisor), Butenko, Sergiy (committee member), Moreno-Centeno, Erick (committee member), Chen, Jianer (committee member).*

Subjects/Keywords: mixed-integer programming; network design; cutset inequalities; valid inequalities; n-step MIR

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Luo, H. (2019). Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem. (Doctoral Dissertation). Texas A&M University. Retrieved from http://hdl.handle.net/1969.1/188770

Chicago Manual of Style (16^{th} Edition):

Luo, Haochen. “Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem.” 2019. Doctoral Dissertation, Texas A&M University. Accessed November 30, 2020. http://hdl.handle.net/1969.1/188770.

MLA Handbook (7^{th} Edition):

Luo, Haochen. “Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem.” 2019. Web. 30 Nov 2020.

Vancouver:

Luo H. Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem. [Internet] [Doctoral dissertation]. Texas A&M University; 2019. [cited 2020 Nov 30]. Available from: http://hdl.handle.net/1969.1/188770.

Council of Science Editors:

Luo H. Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem. [Doctoral Dissertation]. Texas A&M University; 2019. Available from: http://hdl.handle.net/1969.1/188770

Wilfrid Laurier University

2. Gorbonos, Elizabeth. Separability and Vertex Ordering of Graphs.

Degree: 2019, Wilfrid Laurier University

URL: https://scholars.wlu.ca/etd/2148

Many graph optimization problems, such as finding an optimal coloring, or a largest clique, can be solved by a divide-and-conquer approach. One such well-known technique is decomposition by clique separators where a graph is decomposed into special induced subgraphs along their clique separators. While the most common practice of this method employs minimal clique separators, in this work we study other variations as well. We strive to characterize their structure and in particular the bound on the number of atoms. In fact, we strengthen the known bounds for the general clique cutset decomposition and the minimal clique separator decomposition. Graph ordering is the arrangement of a graphâ€™s vertices according to a certain logic and is a useful tool in optimization problems. Special types of vertices are often recognized in graph classes, for instance it is well-known every chordal graph contains a simplicial vertex. Vertex-ordering, based on such properties, have originated many linear time algorithms. We propose to define a new family named SE-Class such that every graph belonging to this family inherently contains a simplicial extreme, that is a vertex which is either simplicial or has exactly two neighbors which are non-adjacent. Our family lends itself to an ordering based on simplicial extreme vertices (named SEO) which we demonstrate to be advantageous for the coloring and maximum clique problems. In addition, we examine the relation of SE-Class to the family of (Even-Hole, Kite)-free graphs and show a linear time generation of SEO for (Even-Hole, Diamond, Claw)-free graphs. We showcase the applications of those two core tools, namely clique-based decomposition and vertex ordering, on the (Even-Hole, Kite)-free family.

Subjects/Keywords: graph theory; decomposition; clique cutset; simplicial extreme; even-hole; kite; Theory and Algorithms

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Gorbonos, E. (2019). Separability and Vertex Ordering of Graphs. (Thesis). Wilfrid Laurier University. Retrieved from https://scholars.wlu.ca/etd/2148

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Gorbonos, Elizabeth. “Separability and Vertex Ordering of Graphs.” 2019. Thesis, Wilfrid Laurier University. Accessed November 30, 2020. https://scholars.wlu.ca/etd/2148.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Gorbonos, Elizabeth. “Separability and Vertex Ordering of Graphs.” 2019. Web. 30 Nov 2020.

Vancouver:

Gorbonos E. Separability and Vertex Ordering of Graphs. [Internet] [Thesis]. Wilfrid Laurier University; 2019. [cited 2020 Nov 30]. Available from: https://scholars.wlu.ca/etd/2148.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Gorbonos E. Separability and Vertex Ordering of Graphs. [Thesis]. Wilfrid Laurier University; 2019. Available from: https://scholars.wlu.ca/etd/2148

Not specified: Masters Thesis or Doctoral Dissertation