Influenza is a public health problem that causes serious illness and deaths all over the world. Vaccination has been shown to be the most effective mean to prevent infection. The primary component of influenza vaccine is the weakened strains. Vaccination triggers the immune system to develop antibodies against those strains whose viral surface glycoprotein hemagglutinin (HA) is similar to that of vaccine strains. However, influenza vaccine must be updated annually since the antigenic structure of HA is constantly mutation. Hemagglutination inhibition (HI) assay is a laboratory procedure frequently applied to evaluate the antigenic relationships of the influenza viruses. It enables the World Health Organization (WHO) to recommend appropriate updates on strains that will most likely be protective against the circulating influenza strains. However, HI assay is labour intensive and time-consuming since it requires several controls for standardization. We use two machine-learning methods, i.e. Artificial Neural Network (ANN) and Logistic Regression, and a Mixed-Integer Optimization Model to predict antigenic variety. The ANN generalizes the input data to patterns inherent in the data, and then uses these patterns to make predictions. The logistic regression model identifies and selects the amino acid positions, which contribute most significantly to antigenic difference. The output of the logistic regression model will be used to predict the antigenic variants based on the predicted probability. The Mixed-Integer Optimization Model is formulated to find hyperplanes that enable binary classification. The performances of our models are evaluated by cross validation.

Solution methodologies for mixed integer bilinear problems (MIBLP) are studied in this dissertation. This problem class is motivated using the pooling problem, a multicommodity network flow problem that typically arises in chemical engineering applications. Stronger than previously known results are provided to compare the strengths of polyhedral relaxations of the pooling problem. A novel single node flow relaxation, defined by a bilinear equality constraint and flow balance, is proposed for the pooling problem. Linear valid inequalities in the original space of variables are derived using a well-known technique called lifting. Mixed integer linear (MILP) formulations are proposed for generating feasible solutions to the pooling problem. Some of these MILP models arise from variable discretizations while others possess a network flow interpretation. The effectiveness of these MILP models is empirically validated on a library of medium and large-scale instances. General MIBLPs, not necessarily pooling problems, are solved using extended MILP reformulations. The reformulation is obtained by writing binary representation for each general integer variable. Facet-defining inequalities are provided for the reformulation of each bilinear term. New valid inequalities are also proposed for bilinear terms with a nontrivial upper bound. The proposed reformulation and cutting planes are compared against a global solver on five different classes of MIBLPs.

A fundamental aspect in performance engineering of wireless networks is optimizing the set of links that can be concurrently activated to meet given signal-to-interference-and-noise ratio (SINR) thresholds. The solution of this combinatorial problem is the key element in scheduling and cross-layer resource management. In this paper, we assume multiuser decoding receivers, which can cancel strongly interfering signals. As a result, in contrast to classical spatial reuse, links being close to each other are more likely to be active concurrently. Our focus is to gauge the gain of successive interference cancellation (SIC), as well as the simpler, yet instructive, case of parallel interference cancellation (PIC), in the context of optimal link activation. We show that both problems are NP-hard and develop compact integer linear programming formulations that enable to approach global optimality. We provide an extensive numerical performance evaluation, indicating that for low to medium SINR thresholds the improvement is quite substantial, especially with SIC, whereas for high SINR thresholds the improvement diminishes and both schemes perform equally well.

As the "network of network", the Internet has been playing a central and crucial role in modern society, culture, knowledge, businesses and so on in a period of over two decades by supporting a wide variety of network technologies and applications. However, due to its popularity and multi-provider nature, the future development of the Internet is limited to simple incremental updates. To address this challenge, network virtualization has been propounded as a potential candidate to provide the essential basis for the future Internet architecture. Network virtualization is capable of providing an open and flexible networking environment in which service providers are allowed to dynamically compose multiple coexisting heterogeneous virtual networks on a shared substrate network. Such a flexible environment will foster the deployment of diversified services and applications. A major challenge in network virtualization area is the Virtual Network Embedding (VNE), which aims to statically or dynamically allocate virtual nodes and virtual links on substrate resources, physical nodes and paths. Making effective use of substrate resources requires high-efficient and survivable VNE techniques. The main contribution of this thesis is two high-performance p-Cycle-based survivable virtual network embedding approaches. These approaches take advantage of p-Cycle-based protection techniques that minimize the backup resources while providing a full VN protection scheme against link and node failures.

Runway systems at airports have been identified as a major source of delay in the aviation system and efficient runway operations are, therefore, important to maintain and/or increase the capacity of the entire aviation system. The goal of the airport runway scheduling problem is to schedule a set of aircraft and minimize a given objective while maintaining separation requirements and enforcing other operational constraints. Uncertain factors such as weather, surrounding traffic and pilot behavior affect when aircraft can be scheduled, and these factors need to be considered in planning models. In this thesis we propose two stochastic programs to address the stochastic airport runway scheduling problem and similarly structured machine scheduling problems. In the first part, we develop a two-stage stochastic integer programming model and analyze it by developing alternative formulations and solution methods. As part of our analysis, we first show that a restricted version of the stochastic runway scheduling problem is equivalent to a machine scheduling problem on a single machine with sequence dependent setup times and stochastic due dates. We then extend this restricted model by considering characteristics specific to the runway scheduling problem and present two different stochastic integer programming models. We derive some tight valid inequalities for these formulations, and we propose a solution methodology based on sample average approximation and Lagrangian based scenario decomposition. Realistic data sets are then used to perform a detailed computational study involving implementations and analyses of several different configurations of the models. The results from the computational tests indicate that practically implementable truncated versions of the proposed solution algorithm almost always produce very high quality solutions. In the second part, we propose a sampling based stochastic program for a general machine scheduling problem with similar characteristics as the airport runway scheduling problem. The sampling based approach allows us to capture more detailed aspects of the problem, such as taxiway operations crossing active runways. The model is based on the stochastic branch and bound algorithm with several enhancements to improve the computational performance. More specifically, we incorporate a method to dynamically update the sample sizes in various parts of the branching tree, effectively decreasing the runtime without worsening the solution quality. When applied to runway scheduling, the algorithm is able to produce schedules with makespans that are 5% to 7% shorter than those obtained by optimal deterministic methods. Additional contributions in this thesis include the development of a global cost function, capturing all relevant costs in airport runway scheduling and trading off different, sometimes conflicting, objectives. We also analyze the impact of including environmental factors in the scheduling process.

We consider the daily transportation problem in forestry which arises when transporting logs from forest sites to customers such as sawmills and pulp and paper mills. Each customer requires a specific amount of a certain assortment, and the deliveries to the customers can be made within time intervals, known as time windows. Further, there are a number of supply points, each with a certain assortment, and a number of vehicles of a given capacity, to be used for transport. The log truck scheduling problem consists of finding a set of minimal costs routes, one for each vehicle, such that the customers’ demands are satisfied without exceeding the supplies available at the supplies. Each route has to satisfy a number of constraints concerning time windows, truck capacity, timetable of the driver, lunch breaks, et cetera. The model used to describe the log truck scheduling problem is based on the route concept, and each variable, or column, represents one feasible route. Since the number of feasible routes is huge, we work only with restricted versions of this problem, which are similar to restricted master problems in a Dantzig-Wolfe decomposition scheme. We use three solution methods based on the column generation principle, together with a pool strategy which allows us to deal with the feasible routes outside the restricted master problem. The three methods proposed have a common structure; they use branch-andprice together with a column generator, followed by branch-and-bound. The column generators in the three methods differ. In the first method, the subproblem is based on a cluster-first-route-second strategy. The column generator in the second method involves solving a constrained shortest path problem, and finally, the third method builds on a repeated generation of clusters and routes. The three methods are tested on real cases from Swedish forestry companies, and the third method has been adapted to a computerised system that utilises the Swedish national road data base, for computing travelling distances. The results obtained show that the optimisation methods succeed in finding significantly better solutions than those obtained by manual planning, and in a reasonable computing time.

Vendor Managed Inventory (VMI), Consignment Inventory (CI) and a combination of both (C&VMI) are supply-chain sourcing agreements between a vendor and customer. VMI allows the vendor to initiate orders on behalf of the customer. In CI, the customer pays for the goods supplied by the vendor only upon use. The vendor under C&VMI decides customer-replenishments, and owns the goods replenished until they are deployed by the customer. Our thesis studies these agreements in three essays. <br /><br /> The first essay considers a vendor <em>V</em> that manufactures a particular product at a unique location. That item is sold to a single retailer, the customer <em>C</em>. Three cases are treated in detail: Independent decision making (no agreement between the parties); VMI, whereby the supplier <em>V</em> initiates orders on behalf of <em>C</em>; and Central decision making (both Vendor and Customer are controlled by the same corporate entity). <br /><br /> Values of some cost parameters may vary between the three cases, and each case may cause a different actor to be responsible for particular expenses. Under a constant demand rate, optimal solutions are obtained analytically for the customer's order quantity, the vendor's production quantity, hence the parties' individual and total costs in the three cases. Inequalities are obtained to delineate those situations in which VMI is beneficial. <br /><br /> The problem setting in the second essay is the same with that of Essay 1, but the sourcing agreements investigated are now CI and C&VMI. In CI, as in the usual independent-sourcing approach, the customer has authority over the timing and quantity of replenishments. CI seems to favour the customer because, in addition, he pays for the goods only upon use. Under a C&VMI agreement, the vendor still owns the goods at the customer's premises, but at least can determine how much to store there. <br /><br /> The second essay thus contrasts the cases CI and C&VMI, and compares each of them to a no-agreement case. General conditions under which those cases create benefits for the vendor, the customer and the whole chain are determined. <br /><br /> Essay 3 investigates VMI and C&VMI separately for a vendor and multiple customers who face time-varying, but deterministic demand for a single product. In any of those agreements, the vendor seeks the best set of customers to achieve economies of scale. MIP models are developed to find that set of customers, and to determine the vendor's optimal production, transportation, and customer-replenishment quantities. The model for VMI is solved using a heuristic that produces two sub-models, and uses hierarchical solution approach for production, customer-replenishment and transportation decisions. C&VMI model is solved using Lagrangian relaxation. Various numerical examples are used to test the solution approaches used. <br /><br /> In the mean time, the customers can guarantee to be no worse off under VMI or C&VMI than the no-agreement case by setting the right levels of maximum inventory. A model to determine those levels and a solution algorithm are also proposed in Essay 3. <br /><br /> The first two essays can help a vendor or customer in a supply chain to determine the least costly sourcing option, which depends on the relative values of various cost parameters. A vendor with multiple customers can make use of the results in the third essay, which reveal the best possible economies of scale under VMI or C&VMI. Those customers can guarantee to be no worse of than traditional sourcing when they set the proposed levels of maximum inventory.

A VLSI chip can today contain hundreds of millions transistors and is expected to contain more than 1 billion transistors in the next decade. In order to handle this rapid growth in integration technology, the design procedure is therefore divided into a sequence of design steps. Circuit layout is the design step in which a physical realization of a circuit is obtained from its functional description. Global routing is one of the key subproblems of the circuit layout which involves finding an approximate path for the wires connecting the elements of the circuit without violating resource constraints. The global routing problem is NP-hard, therefore, heuristics capable of producing high quality routes with little computational effort are required as we move into the Deep Sub-Micron (DSM) regime. In this thesis, different approaches for global routing problem are first reviewed. The advantages and disadvantages of these approaches are also summarized. According to this literature review, several mathematical programming based global routing models are fully investigated. Quality of solution obtained by these models are then compared with traditional Maze routing technique. The experimental results show that the proposed model can optimize several global routing objectives simultaneously and effectively. Also, it is easy to incorporate new objectives into the proposed global routing model. To speedup the computation time of the proposed ILP based global router, several hierarchical methods are combined with the flat ILP based global routing approach. The experimental results indicate that the bottom-up global routing method can reduce the computation time effectively with a slight increase of maximum routing density. In addition to wire area, routability, and vias, performance and low power are also important goals in global routing, especially in deep submicron designs. Previous efforts that focused on power optimization for global routing are hindered by excessively long run times or the routing of a subset of the nets. Accordingly, a power efficient multi-pin global routing technique (PIRT) is proposed in this thesis. This integer linear programming based techniques strives to find a power efficient global routing solution. The results indicate that an average power savings as high as 32\% for the 130-nm technology can be achieved with no impact on the maximum chip frequency.

This thesis presents a multi-stage linear stochastic mixed integer programming (SMIP) model for planning power generation in a pool-type day-ahead electricity market. The model integrates a reserve demand curve and shares most of the features of a stochastic unit commitment (UC) problem, which is known to be NP-hard. We capture the stochastic nature of the problem through scenarios, resulting in a large-scale mixed integer programming (MIP) problem that is computationally challenging to solve. Given that an independent system operator (ISO) has to solve such a problem within a time requirement of an hour or so, in order to release operating schedules for the next day real-time market, the problem has to be solved efficiently. For that purpose, we use some approximations to maintain the linearity of the model, parsimoniously select a subset of scenarios, and invoke realistic assumptions to keep the size of the problem reasonable. Even with these measures, realistic-size SMIP models with binary variables in each stage are still hard to solve with exact methods. We, therefore, propose a scenario-rolling heuristic to solve the SMIP problem. In each iteration, the heuristic solves a subset of the scenarios, and uses part of the obtained solution to solve another group in the subsequent iterations until all scenarios are solved. Two numerical examples are provided to test the performance of the scenario-rolling heuristic, and to highlight the difference between the operative schedules of a deterministic model and the SMIP model. Motivated by previous studies on pricing MIP problems and their applications to pricing electric power, we investigate pricing issues and compensation schemes using MIP formulations in the second part of the thesis. We show that some ideas from the literature can be applied to pricing energy/reserves for a relatively realistic model with binary variables, but some are found to be impractical in the real world. We propose two compensation schemes based on the SMIP that can be easily implemented in practice. We show that the compensation schemes with make-whole payments ensure that generators can have non-negative profits. We also prove that under some assumptions, one of the compensation schemes has the interesting theoretical property of minimizing the variance of the profit of generators to zero. Theoretical and numerical results of these compensation schemes are presented and discussed.

The focus of this thesis is to explore a new mechanism to give added incentive to invest in new capacities in deregulated electricity markets. There is a lot of concern in energy markets, regarding lack of sufficient private sector investment in new capacities to generate electricity. Although some markets are using mechanisms to reward these investments directly, e.g., by governmental subsidies for renewable sources such as wind or solar, there is not much theory to guide the process of setting the reward levels. The proposed mechanism involves a long term planning model, maximizing the social welfare measured as consumers’ plus producers’ surplus, by choosing new generation capacities which, along with still existing capacities, can meet demand. Much previous research in electricity capacity planning has also solved optimization models, usually with continuous variables only, in linear or non-linear programs. However, these approaches can be misleading when capacity additions must either be zero or a large size, e.g., the building of a nuclear reactor or a large wind farm. Therefore, this research includes binary variables for the building of large new facilities in the optimization problem, i.e. the model becomes a mixed integer linear or nonlinear program. It is well known that, when binary variables are included in such a model, the resulting commodity prices may give insufficient incentive for private investment in the optimal new capacities. The new mechanism is intended to overcome this difficulty with a capacity price in addition to the commodity price: an auxiliary mathematical program calculates the minimum capacity price that is necessary to ensure that all firms investing in new capacities are satisfied with their profit levels. In order to test the applicability of this approach, the result of the suggested model is compared with the Ontario Integrated Power System Plan (IPSP), which recommends new generation capacities, based on historical data and costs of different sources of electricity generation for the next 20 years given a fixed forecast of demand.