| In general, mixed integer linear programming models are known to be computationally intractable. Algorithmic procedures that provide optimal or near optimal solutions are usually specific to a particular model or class of models. In recent decades, the focus has shifted to developing, what are termed, tight formulations through the use of valid inequalities. Valid inequalities are typically specific to a class of optimization models and have been shown to be crucial to obtaining optimal solutions.; Modeling the supply chain to determine efficient and effective policies across and within the echelons of a supply chain can be a formidable task. Supply chains are not only defined by their physical infrastructure of plants, warehouses, distribution centers, and transportation alternatives, but also by defining characteristics such as the number of products, product volumes, and their demand patterns over time. A model for a supply chain can defy solution for specific instances of both the product characteristics and the spatial characteristics of the infrastructure. The difference in two supply chain instances that render the model for one to be intractable, and the model for the other to yield instantaneously obtained optimal solutions, can be due to a combination of factors, such as cost structures, demand patterns, or spatial configurations.; This dissertation examines various model instances of each of a suite of single and multi-period supply chain models to reveal the manner in which specific supply chain characteristics can lead to computational intractability. Valid inequalities, which are developed for each model studied, are shown to not only alleviate the model's computational intractability by orders of magnitude, but also afford identification of optimal solutions to a spectrum of model instances. This study of various problem instances reveals that particular patterns of transportation, inventory, and distribution are determined by the particular cost structures and cost tradeoffs. The studies reveal that computational intractability is, in fact, due to factors that include specific types of spatial configuration, cost structures of multiple modes of transportation, and temporal relationships between inventory and transportation. |
