This thesis consists of an introduction and sevenindependent, but closely related, papers which all deal withproblems in structural optimization. In particular, we considermodels and methods for global optimization of problems intopology design of discrete and continuum structures. In the first four papers of the thesis the nonconvex problemof minimizing the weight of a truss structure subject to stressconstraints is considered. First itis shown that a certainsubclass of these problems can equivalently be cast as linearprograms and thus efficiently solved to global optimality.Thereafter, the behavior of a certain well-known perturbationtechnique is studied. It is concluded that, in practice, thistechnique can not guarantee that a global minimizer is found.Finally, a convergent continuous branch-and-bound method forglobal optimization of minimum weight problems with stress,displacement, and local buckling constraints is developed.Using this method, several problems taken from the literatureare solved with a proof of global optimality for the firsttime. The last three papers of the thesis deal with topologyoptimization of discretized continuum structures. Theseproblems are usually modeled as mixed or pure nonlinear 0-1programs. First, the behavior of certain often usedpenalization methods for minimum compliance problems isstudied. It is concluded that these methods may fail to producea zero-one solution to the considered problem. To remedy this,a material interpolation scheme based on a rational functionsuch that compli- ance becomes a concave function is proposed.Finally, it is shown that a broad range of nonlinear 0-1topology optimization problems, including stress- anddisplacement-constrained minimum weight problems, canequivalently be modeled as linear mixed 0-1 programs. Thisresult implies that any of the standard methods available forgeneral linear integer programming can now be used on topologyoptimization problems. <b>Keywords:</b>topology optimization, global optimization,stress constraints, linear programming, mixed integerprogramming, branch-and-bound.

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.

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.

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.

No description available.

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.

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.

A workforce plan states the number of workers required at any point in time. Efficient workforce plans can help companies achieve their organizational goals while keeping costs low. In ever increasing globalized work market, companies need a competitive edge over their competitors. A competitive edge can be achieved by lowering costs. Labour costs can be one of the significant costs faced by the companies. Efficient workforce plans can provide companies with a competitive edge by finding low cost options to meet customer demand. This thesis studies the problem of determining the required number of workers when there are two categories of workers. Workers belonging to the first category are trained to work on one type of task (called Specialized Workers); whereas, workers in the second category are trained to work in all the tasks (called Flexible Workers). This thesis makes the following three main contributions. First, it addresses this problem when the demand is deterministic and stochastic. Two different models for deterministic demand cases have been proposed. To study the effects of uncertain demand, techniques of Robust Optimization and Robust Mathemat- ical Programming were used. The thesis also investigates methods to solve large instances of this problem; some of the instances we considered have more than 600,000 variables and constraints. As most of the variables are integer, and objective function is nonlinear, a commercial solver was not able to solve the problem in one day. Initially, we tried to solve the problem by using Lagrangian relaxation and Outer approximation techniques but these approaches were not successful. Although effective in solving small problems, these tools were not able to generate a bound within run time limit for the large data set. A number of heuristics were proposed using projection techniques. Finally this thesis develops a genetic algorithm to solve large instances of this prob- lem. For the tested population, the genetic algorithm delivered results within 2-3% of optimal solution.

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 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.