The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

This dissertation studies models for locating facilities in time varying demand environments. We describe the characteristics of the time varying demand that motivate the analysis of our location models in terms of total demand and the change in value and location of the demand of each customer. The first part of the dissertation is devoted to the dynamic location model, which determines the optimal time and location for establishing capacitated facilities when demand and cost parameters are time varying. This model minimizes the total cost over a discrete and finite time horizon for establishing, operating, and closing facilities, including the transportation costs for shipping demand from facilities to customers. The model is solved using Lagrangian relaxation and Benders? decomposition. Computational results from different time varying total demand structures demonstrate, empirically, the performance of these solution methods. The second part of the dissertation studies two location models where relocation of facilities is not allowed and the objective is to determine the optimal location of capacitated facilities that will have a good performance when demand and cost parameters are time varying. The first model minimizes the total cost for opening and operating facilities and the associated transportation costs when demand and cost parameters are time varying. The model is solved using Benders? decomposition. We show that in the presence of high relocation costs of facilities (opening and closing costs), this model can be solved as a special case by the dynamic location model. The second model minimizes the maximum regret or opportunity loss between a robust configuration of facilities and the optimal configuration for each time period. We implement local search and simulated annealing metaheuristics to efficiently obtain near optimal solutions for this model.

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).

No description available.