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.

This thesis sets out to analyze how restricting rest (sleep) locations for long-haul truckers may impact operational productivity, given hours-of-service regulations. Productivity in this thesis is measured by the minimum number of unique drivers required to feasibly execute a set of load requests over a known planning horizon. When drivers may stop for rest at any location, they may maximize utilization under regulated driving hours. When drivers may only rest at certain discrete locations, their productivity may be diminished since they may no longer be able to fully utilize available service hours. These productivity losses may require trucking firms to operate larger driver fleets. This thesis addresses two specific challenges presented by this scenario; first, understanding how a given discrete set of rest locations may affect driver fleet size requirements; and second, how to determine optimal discrete locations for a fixed number of rest facilities and the potential negative impact on fleet size of non-optimally located facilities. The minimum fleet size problem for a single origin-destination leg with fixed possible rest locations is formulated as a minimum cost network flow with additional bundling constraints. A mixed integer program is developed for solving the single-leg rest facility location problem. Tractable adaptations of the basic models to handle problems with multiple lanes are also presented. This thesis demonstrates that for typical long-haul lane lengths the effects of restricting rest to a relatively few fixed rest locations has minimal impact on fleet size. For an 18-hour lane with two rest facilities, no increase in fleet size was observed for any test load set instances with exponentially distributed interdeparture times. For test sets with uniformly distributed interdeparture times, additional required fleet sizes ranged from 0 to 11 percent. The developed framework and results should be useful in the analysis of truck transportation of security-sensitive commodities, such as food products and hazardous materials, where there may exist strong external pressure to ensure that drivers rest only in secure locations to reduce risks of tampering.

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.

In 2003, Gomory and Johnson gave two different three-slope T-space facet constructions, both of which shared a slope with the corresponding Gomory mixed-integer cut. We give a new three-slope facet which is independent of the GMIC and also give a four-slope T-space facet construction, which to our knowledge, is the first four-slope construction. We describe an enumerative framework for the discovery of T-space facets. Using an algorithm by Harvey for computing integer hulls in the plane, we give a heuristic for quickly computing lattice-free triangles. Given two rows of the tableau, we derive how to exactly calculate lattice-free triangles and quadrilaterals in the plane which can be used to derive facet-defining inequalities of the integer hull. We then present computational results using these derivations where non-basic integer variables are strengthened using Balas-Jeroslow lifting.

<p>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.</p><p>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.</p><p>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.</p><p><b>Keywords:</b>topology optimization, global optimization,stress constraints, linear programming, mixed integerprogramming, branch-and-bound.</p>