This thesis aims to implement a combination of Linear Programming Column Generation and a Large Neighbourhood Search heuristic to solve scheduling problems. The resulting method is named Integer Programming Column Search (IPCS). For computational evaluation, the IPCS method is applied to the problem Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources generalised to parallel identical machines. The interest of combining exact procedures with heuristic approaches is quickly growing since scheduling problems have many and complex real-world applications. Most of these problems are NP-hard and therefore very challenging to solve. By using a combination of heuristic strategies and exact procedures, it can be possible to find high-quality solutions to such problems within an acceptable time horizon. The IPCS method uses a greedy integer programming column generating problem introduced in a previous work. This problem is designed to generate columns that are useful in near-optimal integer solutions. A difference to previously introduced method is that we here build a master problem, an Integer Programming Column Search Master (IPCS-Master). This is used to update the dual solution that is provided to the greedy integer programming column generating problem. The computational performance of the IPCS method is evaluated on instances with 60, 70, 80, 90 and 100 jobs. The result shows that the combined design encourage the generation of columns that benefit the search of near-optimal integer solutions. The introduction of an IPCS-Master, which is used to update the dual variable values, generally leads to fewer pricing problem iterations than when no master problem is used.

Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 250-274).

Road traffic dominates in domestic Swedish transportation and is highly dependent on fossil fuels, petrol and diesel. Currently, the use of renewable fuels in transportation accounts for less than 6% of the total energy use in transport. The demand for bioethanol to fuel transportation is growing and cannot be met through current domestic production alone. Lignocellulosic ethanol derived from agricultural crop residues may be a feasible alternative source of ethanol for securing a consistent regional fuel supply in Swedish climatic conditions.  This licentiate thesis focuses on regional transport fuel supply by considering local small-scale ethanol production from straw. It presents the results of investigations of regional transport fuel supply with respect to minimising regional CO2 emissions, cost estimates for transport fuel supply, and the availability of lignocellulosic resources for small-scale ethanol production. Regional transport fuel demand between the present and 2020 is also estimated. The results presented here show that significant bioethanol can be produced from the straw and Salix available in the studied regions and that this is sufficient to meet the regions’ current ethanol fuel demand.  A cost optimisation model for regional transport fuel supply is developed and applied for two cases in one study region, one when the ethanol production plant is integrated with an existing CHP plant (polygeneration), and one with a standalone ethanol production plant. The results of the optimisation model show that in both cases the changes in ethanol production costs have the biggest influence on the cost of supplying the regional passenger car fleet with transport fuel, followed by the petrol price and straw production costs.  By integrating the ethanol production process with a CHP plant, the costs of supplying regional passenger car fleet with transport fuel can be reduced by up to a third. Moreover, replacing petrol fuel with ethanol can cut regional CO2 emissions from transportation by half.

This thesis consists of an introduction and seven appended papers. The purpose of the introduction is to give an overview of the field of topology optimization of discretized load carrying continuum structures. It is assumed that the design domain has been discretized by the finite element method and that the design variable vector is a binary vector indicating presence or absence of material in the various finite elements. Common to all papers is the incorporation of von Mises stresses in the problem formulations. In the first paper the design variables are binary but it is assumed that the void structure can actually take some load. This is equivalent to adding a small positive value, epsilon, to all design variables, both those that are void and those that are filled with material. With this small positive lower bound the stiffness matrix becomes positive definite for all designs. If only one element is changed (from material to void or from void to material) the new global stiffness matrix is just a low rank modification of the old one and thus the Sherman-Morrison-Woodbury formula can be used to compute the displacements in the neighbouring designs efficiently. These efficient sensitivity calculations can then be applied in the context of a neighbourhood search method. Since the computed displacements are exact in the 1-neighbourhood (when one design variable is changed) the neighbourhood search method will find a local optimum with respect to the 1-neighbourhood. The second paper presents globally optimal zero-one solutions to some small scale topology optimization problems defined on discretized continuum design domains. The idea is that these solutions can be used as benchmarks when testing new algorithms for finding pure zero-one solutions to topology optimization problems. In the third paper the results from the first paper are extended to include also the case where there is no epsilon>0. In this case the stiffness matrix will no longer be positive definite which means that the Sherman-Morrison-Woodbury formula can no longer be applied. The changing of one or two binary design variables to their opposite binary values will still result in a low rank change, but the size of the reduced stiffness matrix will change with the design. It turns out, however, that it is possible to compute the effect of these low rank changes efficiently also without the positive lower bound. These efficient sensitivity calculations can then be used in the framework of a neighbourhood search method. In this case the complete 1-neighbourhood and a subset of the 2-neighbourhood is investigated in the search for a locally optimal solution. In the fourth paper the sensitivity calculations developed in the third paper are used to generate first and partial second order approximations of the nonlinear functions usually present in topology optimization problems. These approximations are then used to generate subproblems in two different sequential integer programming methods (SLIP and SQIP, respectively). Both these methods generate a sequence of iteration points that can be proven to converge to a local optimum with respect to the 1-neighbourhood. The methods are tested on some different topology optimization problems. The fifth paper demonstrates that the SLIP method developed in the previous paper can be applied also to the mechanism design problem with stress constraints. In order to generate the subproblems in a fast way small displacements are assumed, which implies that the efficient sensitivity calculations derived in the third paper can be used. The numerical results indicate that the method can be used to lower the stresses and still get a functional mechanism. In the sixth paper the SLIP method developed in the fourth paper is used as a post processor to obtain locally optimal zero-one solutions starting from a rounded solution to the corresponding continuous problem. The numerical results indicate that the method can perform well as a post processor. The seventh paper is a theoretical paper that investigates the validity of the commonly used positive lower bound epsilon on the design variables when stating and solving topology optimization problems defined on discretized load carrying continuum structures. The main result presented here is that an optimal "epsilon-1" solution to an "epsilon-perturbed" discrete minimum weight problem with constraints on compliance, von Mises stresses and strain energy densities, is optimal, after rounding to zero-one, to the corresponding "unperturbed" discrete problem. This holds if the constraints in the perturbed problem are carefully defined and epsilon>0 is sufficiently small. / QC 20100917

We define an order cutoff for a retailer as a time in the day such that orders sent to the depot before this point will be delivered by tomorrow, and orders submitted after will be delivered by the day after tomorrow. The later a retailer’s cutoff, the sooner it receives its orders which helps it to maintain ideal inventory levels. Generally, not all retailers in a supply chain can have the latest cutoff since transportation takes a significant amount of time. This thesis tries to assign optimal order cutoffs to retailers. We call this an order cutoff assignment problem and we solve it using three different mathematical programming approaches. The approaches are exhaustive route generation and selection, a series of mixed integer programs, and branch-and-price. 60 sample problems were solved and results showed that branch-and-price is often the most effective method.

We define an order cutoff for a retailer as a time in the day such that orders sent to the depot before this point will be delivered by tomorrow, and orders submitted after will be delivered by the day after tomorrow. The later a retailer’s cutoff, the sooner it receives its orders which helps it to maintain ideal inventory levels. Generally, not all retailers in a supply chain can have the latest cutoff since transportation takes a significant amount of time. This thesis tries to assign optimal order cutoffs to retailers. We call this an order cutoff assignment problem and we solve it using three different mathematical programming approaches. The approaches are exhaustive route generation and selection, a series of mixed integer programs, and branch-and-price. 60 sample problems were solved and results showed that branch-and-price is often the most effective method.

This thesis documents the optimized design of a touch screen using infrared technology as a three dimensional problem. The framework is fundamentally built on laser diode technology and introduces mirrors for signal reflection. The rising popularity of touch screens are credited to the naturally intuitive control of display interfaces, extensive data presentation, and the improved manufacturing process of various touch screen implementations. Considering the demands on touch screen technology, the design for a large scaled touch panel is inevitable, and signal reduction techniques become a necessity to facilitate signal processing and accurate touch detection. The developed research model seeks to capture realistic touch screen design limitations to create a deploy-able configuration. The motivation of the problem stems from the significant reduction of representation achieved by combinatorial group theory. The research model is of difficulty NP-complete. Additional exclusive-or functions for uniqueness, strengthening model search space, symmetry eliminating constraints, and implementation constraints are incorporated for enhanced performance. The computational results and analysis of objectives, valuing the emphasis on diodes and layers are evaluated. The evaluation of trade-off between diodes and layers is also investigated.

In this dissertation we study several non-convex and stochastic optimization problems. The common theme is the use of mixed-integer programming (MIP) techniques including valid inequalities and reformulation to solve these problems. We first study a strategic capacity planning model which captures the trade-off between the incentive to delay capacity installation to wait for improved technology and the need for some capacity to be installed to meet current demands. This problem is naturally formulated as a MIP with a bilinear objective. We develop several linear MIP formulations, along with classes of strong valid inequalities. We also present a specialized branch-and-cut algorithm to solve a compact concave formulation. Computational results indicate that these formulations can be used to solve large-scale instances. We next study methods for optimization with joint probabilistic constraints. These problems are challenging because evaluating solution feasibility requires multidimensional integration and the feasible region is not convex. We propose and analyze a Monte Carlo sampling scheme to simplify the probabilistic structure of such problems. Computational tests of the approach indicate that it can yield good feasible solutions and reasonable bounds on their quality. Next, we study a MIP formulation of the non-convex sample approximation problem. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. Computational results indicate that large-scale instances can be solved using the strengthened formulations. Finally, we study optimization problems with stochastic dominance constraints. A stochastic dominance constraint states that a random outcome which depends on the decision variables should stochastically dominate a given random variable. We present new formulations for both first and second order stochastic dominance which are significantly more compact than existing formulations. Computational tests illustrate the benefits of the new formulations.

In this dissertation, several essays in the field of bio-security are presented. The estimation of the probability of an FMD outbreak by type and location of premises is important for decision making. In Essay I, we estimate and predict the probability/risk of an FMD outbreak spreading to the various premises in the study area. We first used a Poisson regression model with adjustment dispersion associated with random simulation results from the AusSpead model to estimate the parameters of the model. Our estimation and prediction show that large cattle loss could be concentrated in three counties-Deaf Smith, Parmer, and Castro. These results are based on approximately 70% of the feedlots with over 10,000 cattle located in the three counties previously mentioned. In Essay II, our objective is to determine the best mitigation strategies in minimizing animal loss based on AusSpead simulation model. We tested 15 mitigation strategies by using multiple comparison. The results show that the best mitigation strategies for all four scenarios are regular surveillance, slaughter of the infected animals, and early detection. We then used the Mixed Integer Programming to estimate costs of disposing of animal carcasses and transportation. Results show that the unit disposal cost will vary with carcass scale and the unit transportation cost also varies with the distribution of the infected premises and disposal locations. FMD seems to have varying impacts on equity markets. In Essay III, we studied returns at three different levels of the stock market. We determined results in a structural break, and then estimated the impact of the announcement of confirmed cases of FMD disease on the volatility of stock market returns by using a GARCH-Mean model. Our results show that the structure break occurs on the day with the largest number of confirmed cases for meat product firms rather than the day of the first confirmed case. We found that the conditional volatilities over the FMD period are higher than those over the sample period. The announcement of confirmed cases had the largest marginal impact on meat products. Investors may always consider maintaining a portfolio consisting of index funds or hedge funds.

In this thesis, we propose a hierarchical level decision support system for workforce planning in medical equipment maintenance services. In strategic level, customer clusters and the total number of field engineers is determined via a mixed integer programming and simulation. In MIP, we aim to find the minimum number of field engineers. Afterwards, we analyze service measures such as response time via simulation. In tactical level, quarterly training program for the field engineers is determined via mixed integer programming and the results are interpreted in terms of service level via simulation.