Advanced search options

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

You searched for `subject:(n step MIR)`

.
Showing records 1 – 3 of
3 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 December 03, 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. 03 Dec 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 Dec 03]. 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

2. Bansal, Manish. Facets for Continuous Multi-Mixing Set and Its Generalizations: Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem.

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

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

The research objective of this dissertation is to develop new facet-defining valid inequalities for several new multi-parameter multi-constraint mixed integer sets. These valid inequalities result in cutting planes that significantly improve the efficiency of algorithms for solving mixed integer programming (MIP) problems involving multimodule capacity constraints. These MIPs arise in many classical and modern applications ranging from production planning to cloud computing. The research in this dissertation generalizes cut-generating methods such as mixed integer rounding (MIR), mixed MIR, continuous mixing, n-step MIR, mixed n-step MIR, migling, and n-step mingling, along with various well-known families of cuts for problems such as multi-module capacitated lot-sizing (MMLS), multi-module capacitated facility location (MMFL), and multi-module capacitated network design (MMND) problems.
More specifically, in the first step, we introduce a new generalization of the continuous mixing set, referred to as the continuous multi-mixing set, where the coefficients satisfy certain conditions. For each n’ ϵ {1; : : : ; n}, we develop a class of valid inequalities for this set, referred to as the n0-step cycle inequalities, and present their facet-defining properties. We also present a compact extended formulation for this set and an exact separation algorithm to separate over the set of all n’-step cycle inequalities for a given n’ ϵ {1; : : : ; n}.
In the next step, we extend the results of the first step to the case where conditions on the coefficients of the continuous multi-mixing set are relaxed. This leads to an extended formulation and a generalization of the n-step cycle inequalities, n ϵ N, for the continuous multi-mixing set with general coefficients. We also show that these inequalities are facet-defining in many cases.
In the third step, we further generalize the continuous multi-mixing set (where no conditions are imposed on the coefficients) by incorporating upper bounds on the integer variables. We introduce a compact extended formulation and new families of multi-row cuts for this set, referred to as the mingled n-step cycle inequalities (n ϵ N), through a generalization of the n-step mingling. We also provide an exact separation algorithm to separate over a set of all these inequalities. Furthermore, we present the conditions under which a subset of the mingled n-step cycle inequalities are facet-defining for this set.
Finally, in the fourth step, we utilize the results of first step to introduce new families of valid inequalities for MMLS, MMFL, and MMND problems. Our computational results show that the developed cuts are very effective in solving the MMLS instances with two capacity modules, resulting in considerable reduction in the integrality gap, the number of nodes, and total solution time.
*Advisors/Committee Members: Kianfar, Kiavash (advisor), Butenko, Sergiy (committee member), Wilhelm, Wilbert E. (committee member), Jiang, Andrew (committee member).*

Subjects/Keywords: n-step cycle; n-step mingling; n-step MIR; mingled n-step MIR; mingled n-step cycle; continuous mixing; continuous multi-mixing; cycle inequalities; mixing; mixed integer programming; cutting planes

…including
mixed *MIR* [51], continuous mixing [105], *n*-*step* *MIR* [62]… …mingling [6], mixed *n*-*step*
*MIR* [96], and *n*-*step* mingling [7], are… …be developed by
2-*step* mingling
2-*step* mingling
*n*-*step* mingling
Mixing
Mixed *MIR*
Mixed *n*… …*step* *MIR*
*MIR*
*MIR*
Mixed *MIR*
Mixed *MIR*
Mixed *n*-*step* *MIR*
(2-*step*) *MIR*
*MIR*
*MIR*
Mixed… …*MIR*
*n*-*step* *MIR*
Table 1: Relation between known inequalities and procedures in literature…

Record Details Similar Records

❌

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

APA (6^{th} Edition):

Bansal, M. (2014). Facets for Continuous Multi-Mixing Set and Its Generalizations: Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem. (Doctoral Dissertation). Texas A&M University. Retrieved from http://hdl.handle.net/1969.1/153819

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

Bansal, Manish. “Facets for Continuous Multi-Mixing Set and Its Generalizations: Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem.” 2014. Doctoral Dissertation, Texas A&M University. Accessed December 03, 2020. http://hdl.handle.net/1969.1/153819.

MLA Handbook (7^{th} Edition):

Bansal, Manish. “Facets for Continuous Multi-Mixing Set and Its Generalizations: Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem.” 2014. Web. 03 Dec 2020.

Vancouver:

Bansal M. Facets for Continuous Multi-Mixing Set and Its Generalizations: Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem. [Internet] [Doctoral dissertation]. Texas A&M University; 2014. [cited 2020 Dec 03]. Available from: http://hdl.handle.net/1969.1/153819.

Council of Science Editors:

Bansal M. Facets for Continuous Multi-Mixing Set and Its Generalizations: Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem. [Doctoral Dissertation]. Texas A&M University; 2014. Available from: http://hdl.handle.net/1969.1/153819

3.
Sanjeevi, Sujeevraja.
Mixed *n*-*Step* *MIR* Inequalities, *n*-*Step* Conic *MIR* Inequalities and a Polyhedral Study of Single Row Facility Layout Problem.

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

URL: http://hdl.handle.net/1969.1/ETD-TAMU-2012-08-11719

In this dissertation, we introduce new families of valid inequalities for general linear mixed integer programs (MIPs) and second-order conic MIPs (SOCMIPs) and establish several theoretical properties and computational effectiveness of these inequalities.
First we introduce the mixed n-step mixed integer rounding (MIR) inequalities for a generalization of the mixing set which we refer to as the n-mixing set. The n-mixing set is a multi-constraint mixed integer set in which each constraint has n integer variables and a single continuous variable. We then show that mixed n-step MIR can generate multi-row valid inequalities for general MIPs and special structure MIPs, namely, multi- module capacitated lot-sizing and facility location problems. We also present the results of our computational experiments with the mixed n-step MIR inequalities on small MIPLIB instances and randomly generated multi-module lot-sizing instances which show that these inequalities are quite effective.
Next, we introduce the n-step conic MIR inequalities for the so-called polyhedral second-order conic (PSOC) mixed integer sets. PSOC sets arise in the polyhedral reformulation of SOCMIPs. We first introduce the n-step conic MIR inequality for a PSOC set with n integer variables and prove that all the 1-step to n-step conic MIR inequalities are facet-defining for the convex hull of this set. We also provide necessary and sufficient conditions for the PSOC form of this inequality to be valid. Then, we use the aforementioned n-step conic MIR facet to derive the n-step conic MIR inequality for a general PSOC set and provide conditions for it to be facet-defining. We further show that the n-step conic MIR inequality for a general PSOC set strictly dominates the n-step MIR inequalities written for the two linear constraints that define the PSOC set. We also prove that the n-step MIR inequality for a linear mixed integer constraint is a special case of the n-step conic MIR inequality.
Finally, we conduct a polyhedral study of the triplet formulation for the single row facility layout problem (SRFLP). For any number of departments n, we prove that the dimension of the triplet polytope (convex hull of solutions to the triplet formulation) is n(n - 1)(n - 2)/3. We then prove that several valid inequalities presented in Amaral (2009) for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral (2009).
*Advisors/Committee Members: Kianfar, Kiavash (advisor), Ntaimo, Lewis (committee member), Wilhelm, Wilbert (committee member), Friesen, Donald (committee member).*

Subjects/Keywords: n-step MIR; mixed n-step MIR; mixing; n-step conic MIR; mixed integer programming; multi-module capacitated lot-sizing; multi-module capacitated facility location; valid inequality; facet; polytope

…V.3
V.4
Polyhedral Second-order Conic Inequalities . . . . .
*n*-*step* Conic *MIR* Inequality… …*MIR* dominates *n*-*step* *MIR* for S. . .
Concluding Remarks… …threefold:
• Develop mixed *n*-*step* *MIR* inequalities for general and special structure linear
MIPs… …valid inequalities.
• Develop *n*-*step* conic *MIR* inequalities for SOCMIPs and linear MIPs, and… …dissertation.
I.1 Mixed *n*-*step* *MIR* Inequalities
Understanding the polyhedral structure of simple…

Record Details Similar Records

❌

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

APA (6^{th} Edition):

Sanjeevi, S. (2012). Mixed n-Step MIR Inequalities, n-Step Conic MIR Inequalities and a Polyhedral Study of Single Row Facility Layout Problem. (Doctoral Dissertation). Texas A&M University. Retrieved from http://hdl.handle.net/1969.1/ETD-TAMU-2012-08-11719

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

Sanjeevi, Sujeevraja. “Mixed n-Step MIR Inequalities, n-Step Conic MIR Inequalities and a Polyhedral Study of Single Row Facility Layout Problem.” 2012. Doctoral Dissertation, Texas A&M University. Accessed December 03, 2020. http://hdl.handle.net/1969.1/ETD-TAMU-2012-08-11719.

MLA Handbook (7^{th} Edition):

Sanjeevi, Sujeevraja. “Mixed n-Step MIR Inequalities, n-Step Conic MIR Inequalities and a Polyhedral Study of Single Row Facility Layout Problem.” 2012. Web. 03 Dec 2020.

Vancouver:

Sanjeevi S. Mixed n-Step MIR Inequalities, n-Step Conic MIR Inequalities and a Polyhedral Study of Single Row Facility Layout Problem. [Internet] [Doctoral dissertation]. Texas A&M University; 2012. [cited 2020 Dec 03]. Available from: http://hdl.handle.net/1969.1/ETD-TAMU-2012-08-11719.

Council of Science Editors:

Sanjeevi S. Mixed n-Step MIR Inequalities, n-Step Conic MIR Inequalities and a Polyhedral Study of Single Row Facility Layout Problem. [Doctoral Dissertation]. Texas A&M University; 2012. Available from: http://hdl.handle.net/1969.1/ETD-TAMU-2012-08-11719