No description available.

No description available.

In this dissertation, we consider two important problems pertaining to the analysis of transportation systems. The first of these is an approach-dependent, time-dependent, label-constrained shortest path problem that arises in the context of the Route Planner Module of the Transportation Analysis Simulation System (TRANSIMS), which has been developed by the Los Alamos National Laboratory for the Federal Highway Administration. This is a variant of the shortest path problem defined on a transportation network comprised of a set of nodes and a set of directed arcs such that each arc has an associated label designating a mode of transportation, and an associated travel time function that depends on the time of arrival at the tail node, as well as on the node via which this node was approached. The lattermost feature is a new concept injected into the time-dependent, label-constrained shortest path problem, and is used to model turn-penalties in transportation networks. The time spent at an intersection before entering the next link would depend on whether we travel straight through the intersection, or make a right turn at it, or make a left turn at it. Accordingly, we model this situation by incorporating within each link's travel time function a dependence on the link via which its tail node was approached. We propose two effective algorithms to solve this problem by adapting two efficient existing algorithms to handle time dependency and label constraints: the Partitioned Shortest Path (PSP) algorithm and the Heap-Dijkstra (HP-Dijkstra) algorithm, and present related theoretical complexity results. In addition, we also explore various heuristic methods to curtail the search. We explore an Augmented Ellipsoidal Region Technique (A-ERT) and a Distance-Based A-ERT, along with some variants to curtail the search for an optimal path between a given origin and destination to more promising subsets of the network. This helps speed up computation without sacrificing optimality. We also incorporate an approach-dependent delay estimation function, and in concert with a search tree level-based technique, we derive a total estimated travel time and use this as a key to prioritize node selections or to sort elements in the heap. As soon as we reach the destination node, while it is within some p% of the minimum key value of the heap, we then terminate the search. We name the versions of PSP and HP-Dijkstra that employ this method as Early Terminated PSP (ET-PSP) and Early Terminated Heap-Dijkstra (ETHP-Dijkstra) algorithms. All of these procedures are compared with the original Route Planner Module within TRANSIMS, which is implemented in the Linux operating system, using C++ along with the g++ GNU compiler. Extensive computational testing has been conducted using available data from the Portland, Oregon, and Blacksburg, Virginia, transportation networks to investigate the efficacy of the developed procedures. In particular, we have tested twenty-five different combinations of network curtailment and algorithmic strategies on three test networks: the Blacksburg-light, the Blacksburg-full, and the BigNet network. The results indicate that the Heap-Dijkstra algorithm implementations are much faster than the PSP algorithmic approaches for solving the underlying problem exactly. Furthermore, mong the curtailment schemes, the ETHP-Dijkstra with p=5%, yields the best overall results. This method produces solutions within 0.37-1.91% of optimality, while decreasing CPU effort by 56.68% at an average, as compared with applying the best available exact algorithm. The second part of this dissertation is concerned with the Classification and Regression Tree (CART) algorithm, and its application to the Activity Generation Module of TRANSIMS. The CART algorithm has been popularly used in various contexts by transportation engineers and planners to correlate a set of independent household demographic variables with certain dependent activity or travel time variables. However, the algorithm lacks an automated mechanism for deriving classification trees based on optimizing specified objective functions and handling desired side-constraints that govern the structure of the tree and the statistical and demographic nature of its leaf nodes. Using a novel set partitioning formulation, we propose new tree development, and more importantly, optimal pruning strategies to accommodate the consideration of such objective functions and side-constraints, and establish the theoretical validity of our approach. This general enhancement of the CART algorithm is then applied to the Activity Generator module of TRANSIMS. Related computational results are presented using real data pertaining to the Portland, Oregon, and Blacksburg, Virginia, transportation networks to demonstrate the flexibility and effectiveness of the proposed approach in classifying data, as well as to examine its numerical performance. The results indicate that a variety of objective functions and constraints can be readily accommodated to efficiently control the structural information that is captured by the developed classification tree as desired by the planner or analyst, dependent on the scope of the application at hand. / Ph. D.

This dissertation explores mathematical programming optimization models and algorithms for routing and scheduling ships in a maritime transportation system. Literature surveyed on seaborne transportation systems indicates that there is a scarcity of research on ship routing and scheduling problems. The complexity and the overwhelming size of a typical ship routing and scheduling problem are the primary reasons that have resulted in the scarcity of research in this area. The principal thrust of this research effort is focused at the Kuwait Petroleum Corporation (KPC) Problem. This problem is of great economic significance to the State of Kuwait, whose economy has been traditionally dominated to a large extent by the oil sector. Any enhancement in the existing ad-hoc scheduling procedure has the potential for significant savings. A mixed-integer programming model for the KPC problem is constructed in this dissertation. The resulting mathematical formulation is rather complex to solve due to (1) the overwhelming problem size for a typical demand contract scenario, (2) the integrality conditions, and (3) the structural diversity in the constraints. Accordingly, attempting to solve this formulation for a typical demand contract scenario without resorting to any aggregation or partitioning schemes is theoretically complex and computationally intractable. Motivated by the complexity of the above model, an aggregate model that retains the principal features of the KPC problem is formulated. This model is computationally far more tractable than the initial model, and consequently, it is utilized to construct a good quality heuristic solution for the KPC problem. The initial formulation is solved using CPLEX 4.0 mixed integer programming capabilities for a number of relatively small-sized test cases, and pertinent results and computational difficulties are reported. The aggregate formulation is solved using CPLEX 4.0 MIP in concert with specialized rolling horizon solution algorithms and related results are reported. The rolling horizon solution algorithms enabled us to handle practical sized problems that could not be handled by directly solving the aggregate problem. The performance of the rolling horizon algorithms may be enhanced by increasing the physical memory, and consequently, better solutions can be extracted. The potential saving and usefulness of this model in negotiation and planning purposes strongly justifies the acquisition of more computing power to tackle practical sized test problems. An ad-hoc scheduling procedure that is intended to simulate the current KPC scheduling practice is presented in this dissertation. It is shown that results obtained via the proposed rolling horizon algorithms are at least as good, and often substantially better than, results obtained via this ad-hoc procedure. / Ph. D.

Solving real world problems with mixed integer programming (MIP) involves efforts in modeling and efficient algorithms. To solve a minimization MIP problem, a lower bound is needed in a branch-and-bound algorithm to evaluate the quality of a feasible solution and to improve the efficiency of the algorithm. This thesis develops a new MIP model and studies algorithms for obtaining lower bounds for MIP. The first part of the thesis is dedicated to a new production planning model with pricing decisions. To increase profit, a company can use pricing to influence its demand to increase revenue, decrease cost, or both. We present a model that uses pricing discounts to increase production and delivery flexibility, which helps to decrease costs. Although the revenue can be hurt by introducing pricing discounts, the total profit can be increased by properly choosing the discounts and production and delivery decisions. We further explore the idea with variations of the model and present the advantages of using flexibility to increase profit. The second part of the thesis focuses on solving integer programming(IP) problems by improving lower bounds. Specifically, we consider obtaining lower bounds for the multi- dimensional knapsack problem (MKP). Because MKP lacks special structures, it allows us to consider general methods for obtaining lower bounds for IP, which includes various relaxation algorithms. A problem relaxation is achieved by either enlarging the feasible region, or decreasing the value of the objective function on the feasible region. In addition, dual algorithms can also be used to obtain lower bounds, which work directly on solving the dual problems. We first present some characteristics of the value function of MKP and extend some properties from the knapsack problem to MKP. The properties of MKP allow some large scale problems to be reduced to smaller ones. In addition, the quality of corner relaxation bounds of MKP is considered. We explore conditions under which the corner relaxation is tight for MKP, such that relaxing some of the constraints does not affect the quality of the lower bounds. To evaluate the overall tightness of the corner relaxation, we also show the worst-case gap of the corner relaxation for MKP. To identify parameters that contribute the most to the hardness of MKP and further evaluate the quality of lower bounds obtained from various algorithms, we analyze the characteristics that impact the hardness of MKP with a series of computational tests and establish a testbed of instances for computational experiments in the thesis. Next, we examine the lower bounds obtained from various relaxation algorithms com- putationally. We study methods of choosing constraints for relaxations that produce high- quality lower bounds. We use information obtained from linear relaxations to choose con- straints to relax. However, for many hard instances, choosing the right constraints can be challenging, due to the inaccuracy of the LP information. We thus develop a dual heuristic algorithm that explores various constraints to be used in relaxations in the Branch-and- Bound algorithm. The algorithm uses lower bounds obtained from surrogate relaxations to improve the LP bounds, where the relaxed constraints may vary for different nodes. We also examine adaptively controlling the parameters of the algorithm to improve the performance. Finally, the thesis presents two problem-specific algorithms to obtain lower bounds for MKP: A subadditive lifting method is developed to construct subadditive dual solutions, which always provide valid lower bounds. In addition, since MKP can be reformulated as a shortest path problem, we present a shortest path algorithm that uses estimated distances by solving relaxations problems. The recursive structure of the graph is used to accelerate the algorithm. Computational results of the shortest path algorithm are given on the testbed instances.

This thesis concerns the application of mixed-integer programming techniques to solve special classes of network flow problems and stochastic integer programs. We draw tools from complexity and polyhedral theory to analyze these problems and propose improved solution methods. In the first part, we consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are required to take values above a prespecified minimum threshold whenever they are not zero. These problems find applications in management and supply chain models where orders in small quantities are undesirable. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We also consider a class of semi-continuous transportation problems where inflow systems arise as substructures, for which we investigate complexity questions. Finally, we study the computational efficacy of the developed polyhedral results in solving randomly generated instances of semi-continuous transportation problems. In the second part, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of optimizing a linear function on the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem and finds applications in stochastic integer programming. We observe that the complexity of the problem depends on how P and X are specified. For instance, P can be explicitly given by its linear description, or implicitly by an oracle. Similarly, X can be explicitly given as a list of vectors, or implicitly as a face of P. While removing vertices turns to be hard in general, it is tractable for tractable 0-1 polytopes, and compact extended formulations can be obtained. Some extensions to integral polytopes are also presented. The third part is devoted to the integer L-shaped method for two-stage stochastic integer programs. A widely used model assumes that decisions are made in a two-step fashion, where first-stage decisions are followed by second-stage recourse actions after the uncertain parameters are observed, and we seek to minimize the expected overall cost. In the case of finitely many possible outcomes or scenarios, the integer L-shaped method proposes a decomposition scheme akin to Benders' decomposition for linear problems, but where a series of mixed-integer subproblems have to be solved at each iteration. To improve the performance of the method, we devise a simple modification that alternates between linear and mixed-integer subproblems, yielding significant time savings in instances from the literature. We also present a general framework to generate optimality cuts via a cut-generating problem. Using an extended formulation of the forbidden-vertices problem, we recast our cut-generating problem as a linear problem and embed it within the integer L-shaped method. Our numerical experiments suggest that this approach can prove beneficial when the first-stage set is relatively complicated.

In this thesis I focus on cutting planes for large Mixed Integer Programming (MIP) problems. More specifically, I focus on two independent cutting planes studies. The first of these deals with cutting planes for the Traveling Salesman Problem (TSP), and the second with cutting planes for general MIPs. In the first study I introduce a new class of cutting planes which I call the Generalized Domino Parity (GDP) inequalities. My main achievements with regard to these are: (1) I show that these are valid for the TSP and for the graphical TSP. (2) I show that they generalize most well-known TSP inequalities (including combs, domino-parity constraints, clique-trees, bipartitions, paths and stars). (3) I show that a sub-class of these (which contains all clique-tree inequalities w/ a fixed number of handles) can be separated in polynomial time, on planar graphs. My second study can be subdivided in two parts. In the first of these I study the Mixed Integer Knapsack Problem (MIKP) and develop a branch-and-bound based algorithm for solving it. The novelty of the approach is that it exploits the notion of "dominance" in order to effectively prune solutions in the branch-and-bound tree. In the second part, I develop a Mixed Integer Rounding (MIR) cut separation heuristic, and embed the MIKP solver in a column generation algorithm in order to assess the performance of said heuristic. The goal of this study is to understand why no other class of inequalities derived from single-row systems has been able to outperform the MIR. Computational results are presented.

The purpose of this dissertation is to synthesize a methodology to prescribe a strategic design of a surveillance system to provide the required level of surveillance for ports and waterways. The method of approach to this problem is to formulate a linear integer programming model to prescribe a strategic surveillance system design (SSD) for ports or waterways, to devise branch-and-price decomposition (B

When integer programming (IP) models are used in operational situations there is a need to consider the tradeoff between the conflicting goals of solution quality and solution time, since for many problems solving realistic-size instances to a tight tolerance is still beyond the capability of state-of-the-art solvers. However, by appropriately defining small instances, good primal solutions frequently can be found quickly. We explore this approach in this thesis by studying the design of algorithms that produce solutions to an integer program by solving restrictions of the problem via integer programming technology. We refer to this type of algorithm as IP-based search and present algorithms for network design problems of both real-world and academic interest. Along with algorithms that exploit the structure of the problem studied we also present a general integer programming algorithm that uses column generation to choose the restrictions to solve.

Branch-price-and-cut algorithms are among the most successful exact optimization approaches for solving many routing and scheduling problems. This is due, in part, to the availability of extremely efficient and effective dynamic programming algorithms for solving the pricing problem, and the availability of efficient and effective branching schemes and cutting planes that drive integrality. In terms of branch-price-and-cut, two obstacles we face today are (1) being able to solve harder and larger pricing problems, and (2) solving mixed-integer column generation formulations that suffer from relatively weak LP bounds compared to the more traditional 0-1 set partitioning type. As part of the work presented in this thesis, we encounter column generation formulations motivated by real life problems that require overcoming both types of challenges. The first part of this thesis is dedicated to solving the resource constrained shortest path problem (RCSPP) arising in column generation pricing problems for formulations involving extremely large networks and a huge number of local resource constraints. We present a relaxation-based dynamic programming algorithm that alternates between a forward and a backward search. Each search employs bounds derived in the previous search to prune the search, and between consecutive searches, the relaxation is tightened over a set of critical resources and arcs. The second part of this thesis focuses in the fixed charge shortest path problem (FCSPP) in which the amount of resource consumed is itself a continuous bounded variable. By exploiting the structure of optimal solutions to FCSPP, we design and implement a solution approach that relies on solving multiple RCSPPs, and therefore can again make use of extremely efficient and effective dynamic programming algorithms. In the third and final part of this thesis, we present a branch-price-and-cut algorithm for the inventory routing problem (IRP). We extend a class of cuts known for the vehicle routing problem, and develop a new class of cuts specifically for IRP to tighten the formulation. Both the branching schemes and cuts preserve the structure of the pricing problem making them efficiently implementable within a branch-price-and-cut algorithm.