Abstract

Many real-world problems are intrinsically mixed-integer nonlinear optimization models, which are challenging to solve due to the combinatorial complexity resulting from discrete decision variables and nonlinear functions. Mixed-integer second-order cone programming (MISOCP) is one of the promising methods to solve MINLP problems. We can describe a wide variety of real-world problems in MISOCP, such as supply chain planning, finance, network design, facility planning, and scheduling. This dissertation aims to study the MISOCP approach in facility location and network design problems where the congestion or competition settings make the problem nonlinear. We develop different types of MISOCP reformulations of nonlinear problems. We aim to find a reliable reformulation method using MISOCP to replace MINLPs which outperforms the existing solution method in the literature. We further strengthen the MISOCPs by adding valid inequality cuts.
The first paper of this thesis investigates a class of discrete stochastic facility location problems with congestion. The problem is to simultaneously determine the location and the capacity level of the facilities, as well as the allocation of customers to these facilities, aiming to minimize the combined total travel, waiting, and service times at the facilities. To model facilities, we employ spatially distributed M/G/1 queues. Incorporating waiting and service times at the facilities while determining their locations and capacities simultaneously results in a nonlinear mixed-integer programming formulation that can be computationally challenging to solve even for moderate-sized instances. We reformulate the problem as a MISOCP model. We present nine conic reformulations and polymatroid inequalities for them. Extensive computations are conducted to assess the efficacy of reformulations and determine the characteristics of a strong conic formulation.
The focus of the second paper is on the bandwidth packing problem (BPP) within telecommunication networks. The problem aims to maximize revenue by determining a set of accepted calls and routing each through the network. Excessive delays due to congestion in the network may arise if certain links are utilized close to their bandwidth capacities. The links in the network are modelled as independent M/M/1 queues. We study two variants of BPP: BPP with queueing delay cost (BPP-QDC) and BPP with queuing delay guarantees (BPP-QDG). BPP-QDC and BPP-QDG are formulated as binary integer nonlinear programs where the nonlinearity is in the objective function for BPP-QDC and the constraint for BPP-QDG. We show several ways of recasting the nonlinear BPP-QDC and BPP-QDG as MISOCPs by transforming the nonlinearity to second-order conic constraints. The reformulations are strengthened with McCormick and polymatroid inequalities. Our comprehensive computational analysis, conducted on both synthetic instances and real-world telecommunication networks, illustrates the efficacy of conic reformulations over large networks.
In the final part of this thesis, we present a branch-and-cut algorithm for a class of discrete competitive location problems (CLP), showcasing its ability to tackle extensive instances. We study our algorithms on two variants of CLP, the competitive facility location problem (CFLP) under both the MNL and gravity model and the competitive hub location problem (CHLP) under the gravity model. We present a MISOCP reformulation for this class of problems which is solved through a branch-and-cut algorithm. Our approach incorporates McCormick, polymatroid, outer approximation, and submodular inequalities. Extensive computational results demonstrate the reliability and efficacy of our algorithm in terms of CPU time, optimality gap, and the number of instances solved to optimality.