This dissertation considers graph theoretic generalizations of the maximum clique problem. Models that were originally proposed in social network analysis literature, are investigated from a mathematical programming perspective for the first time. A social network is usually represented by a graph, and cliques were the first models of "tightly knit groups" in social networks, referred to as cohesive subgroups. Cliques are idealized models and their overly restrictive nature motivated the development of clique relaxations that relax different aspects of a clique. Identifying large cohesive subgroups in social networks has traditionally been used in criminal network analysis to study organized crimes such as terrorism, narcotics and money laundering. More recent applications are in clustering and data mining wireless networks, biological networks as well as graph models of databases and the internet. This research has the potential to impact homeland security, bioinformatics, internet research and telecommunication industry among others. The focus of this dissertation is a degree-based relaxation called k-plex. A distance-based relaxation called k-clique and a diameter-based relaxation called k-club are also investigated in this dissertation. We present the first systematic study of the complexity aspects of these problems and application of mathematical programming techniques in solving them. Graph theoretic properties of the models are identified and used in the development of theory and algorithms. Optimization problems associated with the three models are formulated as binary integer programs and the properties of the associated polytopes are investigated. Facets and valid inequalities are identified based on combinatorial arguments. A branch-and-cut framework is designed and implemented to solve the optimization problems exactly. Specialized preprocessing techniques are developed that, in conjunction with the branch-and-cut algorithm, optimally solve the problems on real-life power law graphs, which is a general class of graphs that include social and biological networks. Computational experiments are performed to study the effectiveness of the proposed solution procedures on benchmark instances and real-life instances. The relationship of these models to the classical maximum clique problem is studied, leading to several interesting observations including a new compact integer programming formulation. We also prove new continuous non-linear formulations for the classical maximum independent set problem which maximize continuous functions over the unit hypercube, and characterize its local and global maxima. Finally, clustering and network design extensions of the clique relaxation models are explored.

For traditional wireless communication systems, static spectrum allocation is the major spectrum allocation methodology. However, according to the recent investigations by the FCC, this has led to more than 70 percent of the allocated spectrum in the United States being under-utilized. Cognitive radio (CR) technology, which supports opportunistic spectrum sharing, is one idea that is proposed to improve the overall utilization efficiency of the radio spectrum. In this thesis we consider a CR communication system based on spectrum sharing schemes, where we have a secondary user (SU) link with multiple transmitting antennas and a single receiving antenna, coexisting with a primary user (PU) link with a single receiving antenna. At the SU transmitter (SU-Tx), the channel state information (CSI) of the SU link is assumed to be perfectly known; while the interference channel from the SU-Tx to the PU receiver (PU-Rx) is not perfectly known due to less cooperation between the SU and the PU. As such, the SU-Tx is only assumed to know that the interference channel gain can take values from a finite set with certain probabilities. Considering a SU transmit power constraint, our design objective is to determine the transmit covariance matrix that maximizes the SU rate, while we protect the PU by enforcing both a PU average interference constraint and a PU outage probability constraint. This problem is first formulated as a non-convex optimization problem with a non-explicit probabilistic constraint, which is then approximated as a mixed binary integer programming (MBIP) problem and solved with the Branch and Bound (BB) algorithm. The complexity of the BB algorithm is analyzed and numerical results are presented to validate the eff ectiveness of the proposed algorithm. A key result proved in this thesis is that the rank of the optimal transmit covariance matrix is one, i.e., CR beamforming is optimal under PU outage constraints. Finally, a heuristic algorithm is proposed to provide a suboptimal solution to our MBIP problem by efficiently (in polynomial time) solving a particularly-constructed convex problem.

This study deals with chocolate production line scheduling. The particular production line allows producing multiple items at the same time. Another distinguishing property affecting the planning methodology is that an item can have different production capacities when produced in different product combinations which are called production patterns in this study. Planning is done on a 12 weeks rolling horizon. There are 21 products and 103 production patterns covering all the production possibilities. The subject of the study is to construct an algorithm that gives 12 weeks&rsquo / production values of each product and to construct the shift based scheduling of the first week of the planning horizon. The first part is Master Production Scheduling (MPS) and the objective is minimizing the shortage and overage costs. A mathematical modeling approach is used to solve the MPS problem. The second part is the scheduling part which aims to arrange the production patterns obtained from the MPS module within the shifts for the first week of the planning horizon considering the setup times. The MPS module is a large integer programming model. The challenge is finding a reasonable lower bound whenever possible. If it is not possible, finding a reasonable upper bound and seeking solutions better than that is the main approach. The scheduling part, after solving MPS, becomes a TSP and the setup times are sequence independent. In this part, the challenge is solving TSP with an appropriate objective function.

In this study, a new selective and time-window routing problem is defined for the first time in the literature, which is called the campaign routing problem (CRP). The two special cases of the CRP correspond to the two real-life problems, namely political campaign routing problem (PCRP) and the experiments on wheels routing problem (EWRP). The PCRP is based on two main decision levels. In the first level, a set of campaign regions is selected according to a given criteria subject to the special time-window constraints. In the second level, a pair of selected regions or a single region is assigned to a campaign day. In the EWRP, a single selected region (school) is assigned to a campaign day. These two problems are modeled using classical mathematical programming and bi-level programming methods, and a two-step heuristic approach is developed for the solution of the problems. Implementation of the solution methods is done using the test instances that are compiled from the real-life data. Computational results show that the solution methods developed generate good solutions in reasonable time.

In this thesis, we work on adisassembly lot-sizing problem for multiple products with parts commonality,i.e., general product structure. We assume that supply of discarded products is infinite. When a product (or a subassembly) is disassembled, all its immediate child items are obtained,i.e., complete disassembly case.Intermediate and leaf items obtained are demandedbyexternal suppliers or remanufacturers. The maximum possible salesfor each intermediate and leaf item are known.Sales of the intermediate and leaf items are the revenue sources. The discarded products are purchased ata unit purchasing cost. The disassembly operation incurs a fixed and a variable disassembly cost. Due to this cost structure, intermediate and leaf items can be stocked incurring an inventory holding cost. We develop an integer programming formulation to determine the time and quantity of the discarded products to be purchased / thetime and quantity of the discarded products and the intermediateitemsto be disassembled / and the time and quantity of intermediate and leaf items to be soldin order tomaximizethe total profit over a finite planning horizon. We state that ourproblem is NP-hard by refering the study of Kim et. al. (2009). We propose a heuristic solution approach that solves the problem in a reasonable computational time and generates near optimal solutions. The solution approach is based on the idea of sequentially solving a relaxed version of the problem and one-period integer programming models.In a computational study, the performance of the heuristic approach is assessed for a number ofrandomly generated problem instances.The results of the computational study show that the solutions of the heuristic approacharevery close to the optimal and the best feasible solutions obtained within the time limit.

The aim of this study is planning the locations of emergency centers (ECs) as well as the number of vehicles in each EC of Corporation, Man Truck and Bus Group, to respond to the calls (arrival of the mobile/24 emergency service vehicle to the broken vehicle) within the desired time. The company aims to respondto the calls within 90 minutes. If the EC cannot respond to the calls within 90 minutes, they should be satisfiedwithin 180 minutes. We propose a probabilistic programming approach to maximize the number of responded calls in 90 minutes while responding to all the calls in 180 minutes. The model determines the locations of the new ECs addition to the existing ones and also the number of vehicles assigned to those centers. The data source to this study is the emergency service calls of the company within February 2008 and December 2010. There are 30 ECs of the company distributed all over Turkey. By using the data, it is examined if the company can get closer to its target in responding to the calls with the current ECs. Necessary changes are proposed in the number and the locations of emergency centers for the desired target. Furthermore, several scenarios for targets with different quality service levels are generated and the effects of these parameters on the objective are observed.

This thesis is to investigate the power system operation strategy for an electrified mass rapid transit¡]MRT¡^network with the load transfer among main transformers by considering load growth and due to annual ridership increase, the loading factors of main transformers are improved so that the power system loss can be reduced. For the conventional planning of an electrified MRT system to serve the public transportation for the metropolitan area, the transformer capacity is often designed to meet the criterion of not only covering the peak demand but also providing the 100% fully capacity reserve for the system operation of target year. With such a high backup capability, the transformers are very lightly loaded for most of the operation time and significant core loss will be introduced over the lifecycle. In this thesis the train motion equation has been applied to find the mechanical power required, the proper strategy of unit commitment of main transformers and network reconfiguration by switching operation has been considered to enhance the operation efficiency of an MRT power system. To demonstrate the effectiveness of the proposed methodology, the Taipei MRT network is selected for computer simulation. It is found that the loading factors of main transformers can be improved dramatically and the load balance among the transformers can be obtained by the proper switching operation. An efficient strategy for transformer planning by taking into account the growth rate of load so that the overall investment cost of main transformers can be justified. The load characteristics and load growth rate of mass rapid transit¡]MRT¡^are derived by an Energy Management Model (EMM) and the AC load flow analysis is used to solve the transformer copper loss and core loss over the study period. To obtain optimal planning and operation strategy of main transformers for the MRT power system, the transformers initial investment cost and depreciation cost, peak power loss and energy loss, and reliability cost of distribution transformers are combined to form the overall cost function .By performing the dynamic programming (DP) the unit commitment of main transformers by considering the annual peak and off peak power loading of whole MRT system is derived. It is found that more efficient system operation can be obtained by the proposed methodology.

We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.

It is an internationally acknowledged that marine protected area (MPA) is an important measure for maintaining biodiversity and rescuing endangered species. MPA can also effectively inhibit human interferences such as development and pollution discharge. The establishment of MPA is possible to fulfill the goal of sustainable management, which is to conserve marine habitat for an integrative ecosystem and a higher biodiversity. However, how to design an effective MPA remains an important research issue to be explored. In order to grasp the spatial distribution of the ecological data in the study area, the current research uses spatial interpolation tool, Kriging, provided by the Geographic information system (GIS) software. Then three spatial analytical models have been developed based on integer programming techniques. It is guarantee that all three models can find the global optimal solutions for the best protective area partitions. This quantitative approach is more efficient and effective compared to the qualitative methods in many aspects. The models are able to preserve the maximum ecological resources under the limited spatial area. Besides, the model formulation can be adjusted from different environmental impact factors to fulfill the requirements of users. The case study of the research is to design a MPA for Kaomei wetland. However the spatial analytical models developed in this research can also be applied to protected area design in land area.

Perhaps no single industry has benefited more from advancements in computation, analytics, and optimization than the airline industry. Operations Research (OR) is now ubiquitous in the way airlines develop their schedules, price their itineraries, manage their fleet, route their aircraft, and schedule their crew. These problems, among others, are well-known to industry practitioners and academics alike and arise within the context of the planning environment which takes place well in advance of the date of departure. One salient feature of the planning environment is that decisions are made in a frictionless environment that do not consider perturbations to an existing schedule. Airline operations are rife with disruptions caused by factors such as convective weather, aircraft failure, air traffic control restrictions, network effects, among other irregularities. Substantially less work in the OR community has been examined within the context of the real-time operational environment. While problems in the planning and operational environments are similar from a mathematical perspective, the complexity of the operational environment is exacerbated by two factors. First, decisions need to be made in as close to real-time as possible. Unlike the planning phase, decision-makers do not have hours of time to return a decision. Secondly, there are a host of operational considerations in which complex rules mandated by regulatory agencies like the Federal Administration Association (FAA), airline requirements, or union rules. Such restrictions often make finding even a feasible set of re-scheduling decisions an arduous task, let alone the global optimum. The goals and objectives of this thesis are found in Chapter 1. Chapter 2 provides an overview airline operations and the current practices of disruption management employed at most airlines. Both the causes and the costs associated with irregular operations are surveyed. The role of airline Operations Control Center (OCC) is discussed in which serves as the real-time decision making environment that is important to understand for the body of this work. Chapter 3 introduces an optimization-based approach to solve the Airline Integrated Recovery (AIR) problem that simultaneously solves re-scheduling decisions for the operating schedule, aircraft routings, crew assignments, and passenger itineraries. The methodology is validated by using real-world industrial data from a U.S. hub-and-spoke regional carrier and we show how the incumbent approach can dominate the incumbent sequential approach in way that is amenable to the operational constraints imposed by a decision-making environment. Computational effort is central to the efficacy of any algorithm present in a real-time decision making environment such as an OCC. The latter two chapters illustrate various methods that are shown to expedite more traditional large-scale optimization methods that are applicable a wide family of optimization problems, including the AIR problem. Chapter 4 shows how delayed constraint generation and column generation may be used simultaneously through use of alternate polyhedra that verify whether or not a given cut that has been generated from a subset of variables remains globally valid. While Benders' decomposition is a well-known algorithm to solve problems exhibiting a block structure, one possible drawback is slow convergence. Expediting Benders' decomposition has been explored in the literature through model reformulation, improving bounds, and cut selection strategies, but little has been studied how to strengthen a standard cut. Chapter 5 examines four methods for the convergence may be accelerated through an affine transformation into the interior of the feasible set, generating a split cut induced by a standard Benders' inequality, sequential lifting, and superadditive lifting over a relaxation of a multi-row system. It is shown that the first two methods yield the most promising results within the context of an AIR model.