Facets for Continuous Multi-Mixing Set and Its Generalizations: Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem

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.