Call number: LD2668 .T4 1978 L445 / Master of Science

The factors limiting the performance of computer software periodically undergo sudden shifts, resulting from technological progress, and these shifts can have profound implications for the design of high performance codes. At the present time, the speed with which hardware can execute a single stream of instructions has reached a plateau. It is now the number of instruction streams that may be executed concurrently which underpins estimates of compute power, and with this change, a critical limitation on the performance of software has come to be the degree to which it can be parallelised. The research in this thesis is concerned with the means by which codes for linear programming may be adapted to this new hardware. For the most part, it is codes implementing the simplex method which will be discussed, though these have typically lower performance for single solves than those implementing interior point methods. However, the ability of the simplex method to rapidly re-solve a problem makes it at present indispensable as a subroutine for mixed integer programming. The long history of the simplex method as a practical technique, with applications in many industries and government, has led to such codes reaching a great level of sophistication. It would be unexpected in a research project such as this one to match the performance of top commercial codes with many years of development behind them. The simplex codes described in this thesis are, however, able to solve real problems of small to moderate size, rather than being confined to random or otherwise artificially generated instances. The remainder of this thesis is structured as follows. The rest of this chapter gives a brief overview of the essential elements of modern parallel hardware and of the linear programming problem. Both the simplex method and interior point methods are discussed, along with some of the key algorithmic enhancements required for such systems to solve real-world problems. Some background on the parallelisation of both types of code is given. The next chapter describes two standard simplex codes designed to exploit the current generation of hardware. i6 is a parallel standard simplex solver capable of being applied to a range of real problems, and showing exceptional performance for dense, square programs. i8 is also a parallel, standard simplex solver, but now implemented for graphics processing units (GPUs).

The study aims to provide information on efficiency opportunities on SCA's northbound cassettes. It has been made by examining the capacity utilization rate on the northbound cassettes on SCA's vessels for a period of two weeks. The cargo loaded in the ports of Rotterdam and Sheerness consists of external cargo of varying shape. The cargo is shipped northbound to Holmsund and Sundsvall. Measurements have been made on the cargo to the final destinations Sundsvall, Holmsund and Finland. The measurements have been used in a mathematical optimization model created to optimize the loading of the cassettes. The model is based on placing boxes in a grid where the boxes that are placed representing the cargo and the grids representing the cassettes. The aim of the model is to reduce the number of cassettes and thereby increase the capacity utilization rate. The study resulted in an increase in capacity utilization rate for both area and volume to all destinations. The overall improvement for all cassettes examined resulted in an increase in the area capacity utilization rate by 9.02 percentage points and 5.72 percentage points for the volume capacity utilization rate. It also resulted in a decrease of 22 cassettes in total on the four voyages that were examined which indicate that there are opportunities to improve the capacity utilization rate. The study also shows that the model can be used as a basis for similar problems.

In recent years, the importance of incorporating uncertainty into planning models for logistics and transportation systems has been widely recognized in the Operations Research and transportation science communities. Maritime transportation, as a major mode of transport in the world, is subject to a wide range of disruptions at the strategic, tactical and operational levels. This thesis is mainly concerned with the development of robustness planning strategies that can mitigate the effects of some major types of disruptions for an important class of optimization problems in the shipping industry. Such problems arise in the creation and negotiation of long-term delivery contracts with customers who require on-time deliveries of high-value goods throughout the year. In this thesis, we consider the disruptions that can increase travel times between ports and ultimately affect one or more scheduled deliveries to the customers. Computational results show that our integrated solution procedure and robustness planning strategies can generate delivery plans that are both economical as well as robust against uncertain disruptions.

Commercial fresh vegetable production is one of the most rewarding and risky farming activities. The price and yield variations throughout the production year, the special characteristics of fresh vegetable produce (i.e. perishability), and the changing consumer demands are some of the factors contributing to the increased uncertainty faced by vegetable producers. This dissertation combined mathematical programming and econometric techniques to: 1) investigate the optimal production and marketing practices under different price distribution information scenarios, risk aversion levels and marketing outlets and 2) examine growers’ preferences as well the effect of risk aversion levels and growers’ risk perception on the choice of marketing contracts. Specifically, the following three modeling approaches were adopted in order to achieve the dissertation objectives: 1) quadratic programming under a mean-variance framework, 2) discrete choice experiments and 3) a combination of quadratic and integer programming embodied in a meanvariance framework. The findings indicate that optimal production practices and the resulting net returns are substantially influenced not only by the choice of marketing channel but also by growers’ risk aversion levels as well as price knowledge. Furthermore, regarding the choice of marketing contracts, the results highlight the existence of heterogeneity in preferences and illustrate the importance of certification cost, in line with the previous literature. Lastly, the findings indicate that risk aversion and risk preferences do not play a significant role in the choice of contractual agreements by farmers.

The aim of this dissertation is to present an algorithm for mixed integer programs which when started with a good heuristic solution can find improved solutions and reduce the error estimate as quickly as possible. This is achieved by using two ideas: a fixed order branch-and-bound method with selective expansion of subproblems and the sieve strategy which uses stronger than optimal bounds. The fixed order branch-and-bound method with selective expansion of subproblems is effective in reducing the error estimate quickly whereas the sieve strategy is effective in reducing the error estimate as well as finding improved solutions quickly. Computational experience is reported.

The objective of this project is to optimize the SAPREF oil refinery steam distribution in which imbalances between the various levels presently require the venting of steam from the lowest level. The overall steam balance shows that the problem originates from an excess of high·pressure (HP) steam production for too few medium pressure steam users and turbines. We proposed to solve this problem by considering the replacement of selected steam turbines with electrical drives. Given a set of demands of electricity, mechanical power and steam at various pressure levels, the objective is to recommend configuration changes to minimize overall cost. This is not a trivial problem, as steam not passed down through turbines to lower levels can create a shortage there, so a combination of replacements is required. The variables of the problem are both decision variables on every steam turbine and continuous variables, such as flows and enthalpies. These decision variables are integer variables, 0 or 1 for every steam turbine. Depending on whether it is kept on steam use or replaced with an electrical drive, these variables are as follows: E = 0: keep the existing steam turbine E - 1: switch it to an electrical drive. A complete and realistic model of this utility section must be constructed in order to represent the actual distribution accurately. This model will include an objective function to minimize, some equality and inequality constraints, and some cost functions. If we want this model to be accurate, we shall have to deal with nonlinearities to avoid simplifications, and these non-linearities could lead to infeasabilities or sub-optimal solutions. So we are facing a typical MTNLP (Mixed Integer Non-Linear Programming) problem to find optimal configuration changes which will maximize the return on investment, meeting the electrical, mechanical and steam demands of the refinery. In order to solve this difficult optimization problem we shall use the user-friendly package GAMS (General Algebraic Modeling System). / Thesis (M.Sc.Eng.)-University of Natal, Durban, 2001.

The objective of this research project is to develop new software tools capable of operational optimisation of existing, large-scale water distribution networks. Since pumping operations represent the main operating cost of any water supply scheme, the optimisation problem is equivalent to providing a new sequence for pumping operations that makes better use of the different electricity tariff structures available to the operators of distribution systems. The minimisation of pumping costs can be achieved by using an optimal schedule that will allow best use of gravitational flows, and restriction of pumping to low-cost power periods as far as possible. A secondary objective of the operational optimisation is to maintain the desired level of disinfectant chlorine at the point of delivery to consumers. There is a steady loss of chlorine with residence time in the system. If the level drops too low there is a risk of bacterial activity. Re-dosage points are sometimes provided in the network. Conversely, too high a level produces an unacceptable odour. The combinatation of dynamic elements (reservoir volumes and chlorine concentration responses) and discrete elements (pump stati and valve positions) makes this a challenging Model Predictive Control (MPC) and constrained optimisation problem, which was solved using MINLP (Mixed Integer Non-linear Programming). The MINLP algorithm was selected for its ability to handle a large number of integer choices (valves open or shut / pumps on or off in this particular case). A model is defined on the basis of a standard element, viz. a vessel containing a variable volume, capable of receiving multiple inputs and delivering just two outputs. The physical properties of an element can be defined in such a way as to allow representation of any item in the actual network: pipes (including junctions and splits), reservoirs, and of course, valves or pumps. The overall network is defined by the inter-linking of a number of standard elements. Once the network has been created within the model, the model predictive control algorithm minimises a penalty function on each time-step, over a defined time horizon from the present, with all variables also obeying defined constraints in this horizon. This constrained non-linear optimization requires an estimate of expected consumer demand profile, which is obtained from historical data stored by the SCADA system monitoring the network. Electricity cost patterns, valve positions, pump characteristics, and reservoir properties (volumes, emergency levels, setpoints) are some of the parameters required for the operational optimisation of the system. / Thesis (M.Sc.Eng.)-University of Natal, Durban, 2004.

In this thesis we study how to efficiently combine the column generation technique (CG) and interior point methods (IPMs) for solving the relaxation of a selection of integer programming problems. In order to obtain an efficient method a change in the column generation technique and a new reoptimization strategy for a primal-dual interior point method are proposed. It is well-known that the standard column generation technique suffers from unstable behaviour due to the use of optimal dual solutions that are extreme points of the restricted master problem (RMP). This unstable behaviour slows down column generation so variations of the standard technique which rely on interior points of the dual feasible set of the RMP have been proposed in the literature. Among these techniques, there is the primal-dual column generation method (PDCGM) which relies on sub-optimal and well-centred dual solutions. This technique dynamically adjusts the column generation tolerance as the method approaches optimality. Also, it relies on the notion of the symmetric neighbourhood of the central path so sub-optimal and well-centred solutions are obtained. We provide a thorough theoretical analysis that guarantees the convergence of the primal-dual approach even though sub-optimal solutions are used in the course of the algorithm. Additionally, we present a comprehensive computational study of the solution of linear relaxed formulations obtained after applying the Dantzig-Wolfe decomposition principle to the cutting stock problem (CSP), the vehicle routing problem with time windows (VRPTW), and the capacitated lot sizing problem with setup times (CLSPST). We compare the performance of the PDCGM with the standard column generation method (SCGM) and the analytic centre cutting planning method (ACCPM). Overall, the PDCGM achieves the best performance when compared to the SCGM and the ACCPM when solving challenging instances from a column generation perspective. One important characteristic of this column generation strategy is that no speci c tuning is necessary and the algorithm poses the same level of difficulty as standard column generation method. The natural stabilization available in the PDCGM due to the use of sub-optimal well-centred interior point solutions is a very attractive feature of this method. Moreover, the larger the instance, the better is the relative performance of the PDCGM in terms of column generation iterations and CPU time. The second part of this thesis is concerned with the development of a new warmstarting strategy for the PDCGM. It is well known that taking advantage of the previously solved RMP could lead to important savings in solving the modified RMP. However, this is still an open question for applications arising in an integer optimization context and the PDCGM. Despite the current warmstarting strategy in the PDCGM working well in practice, it does not guarantee full feasibility restorations nor considers the quality of the warmstarted iterate after new columns are added. The main motivation of the design of the new warmstarting strategy presented in this thesis is to close this theoretical gap. Under suitable assumptions, the warmstarting procedure proposed in this thesis restores primal and dual feasibilities after the addition of new columns in one step. The direction is determined so that the modi cation of small components at a particular solution is not large. Additionally, the strategy enables control over the new duality gap by considering an expanded symmetric neighbourhood of the central path. As observed from our computational experiments solving CSP and VRPTW, one can conclude that the warmstarting strategies for the PDCGM are useful when dense columns are added to the RMP (CSP), since they consistently reduce the CPU time and also the number of iterations required to solve the RMPs on average. On the other hand, when sparse columns are added (VRPTW), the coldstart used by the interior point solver HOPDM becomes very efficient so warmstarting does not make the task of solving the RMPs any easier.

Approved for public release; distribution is unlimited. / We model the minimum-cost procurement and allocation of anti-ship cruise missiles to naval combat ships as a two-period stochastic integer program. Discrete scenarios in two periods define "demands" for missiles (i.e., targets and number of missiles required to kill those targets), which must be met with sufficiently high probabilities. After the former combat period, ships may replenish their inventories from a depot if desired and if the available depot inventory suffices. A force commander optimizes ship-to-target assignments to meet demands. The basic model solves slowly, so we add constraints to enforce reasonable operational directives, and add valid inequalities. These improvements reduce the solution time by 95% for the test case. Instances with up to six ships and five scenarios in each period then solve in less than one hour on a 2 GHz personal computer. / Lieutenant Commander, Israel Navy