The transmission of power across the GB transmission system, as operated by National Grid, results in inevitable loss of electrical power. Operationally these power losses cannot be eliminated, but they can be reduced by adjustment of the system voltage profile. At present the minimisation of active power losses relies upon a lengthy manually based iterative adjustment process. Therefore the system operator requires the development of advanced optimisation tools to cope with the challenges faced over the next decade, such as achieving the stringent greenhouse gas emission targets laid down by the UK government, while continue to provide an economical, secure and efficient service. To meet these challenges the research presented in this thesis has developed optimisation techniques that can assist control centre engineers by automatically setting up voltage studies that are low loss and low cost. The proposed voltage optimisation techniques have been shown to produce solutions that are secured against 800 credible contingency cases. A prototype voltage optimisation tool has been deployed, which required the development of a series of novel approaches to extend the functionality of an existing optimisation program. This research has lead to the development of novel methods for handling multi-objectives, contradictory shunt switching configurations and selecting all credible contingencies. Studies indicate that a theoretical loss saving of 1.9% is achievable, equivalent to an annual emissions saving of approximately 64,000 tonnes of carbon dioxide. A novel security constrained mixed integer non-linear optimisation technique has also been developed. The proposed method has been shown to be superior to several conventional methods on a wide range of IEEE standard network models and also on a range of large-scale GB network models. The proposed method manages to further reduce active power losses and also satisfies all security constraints.

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

Well-publicized lost opportunities for U.S. and coalition air forces to strike enemy leadership targets in Afghanistan and Iraq demonstrate the importance of Time Sensitive Targeting. How do we "pair" the weapon and weapons delivery platform with their target? The available platforms (aircraft, manned or unmanned) may be on the ground in an alert status, loitering airborne, or on their way to attack other targets. The problem is compounded by the facts that we actually wish to (a) create multiple strike packages simultaneously, (b) recompose existing strike packages that are disrupted by the new plans, (c) minimize such disruptions, (d) satisfy minimum kill probabilities, and (e) avoid the attrition of tasked assets. This thesis develops an automated, optimizing, heuristic decision aid, "RAPT-OR", that rapidly revises a current Air Taking Order (ATO) to meet the requirements above. Using a set-packing model, RAPT-OR, an ATO near optimally, on a desktop PC, in less than two seconds, for a typical scenario with 40 aircraft, four new targets and hundreds of potential strike packages. RAPT-OR allows decision makers the ability of adjusting risk acceptance in the formulation of possible courses of action by manipulating friendly attrition importance in formulating a solution.

The Marine infantryman is carrying too much weight in combat. This thesis analyzes the trade-offs between individual load weights and the value that a Distributed Operations squad receives from the equipment its members carry. We use multiple objective decision analysis principles to help determine the coefficients for an integer linear programming model. The optimization model prescribes equipment assignment to individual positions that maximizes squad mission success while meeting target weights for the individual Marine. Our findings indicate that significant improvements can be made to the Marine's combat load weight and equipment composition. The optimization model provides the squad with a more efficient combination of equipment while reducing the average weight of the combat load by more than 19 percent for both the assault load and the approach march load. Also, by balancing the loads across the members of the squad, the model reduces the variation of weight across the squad positions from as much as 38 percent to less than 2 percent for all loads. By examining the trade space between equipment weight and equipment value, we assist in the creation of future Marine Corps doctrine by providing senior Marine leaders a starting point analysis for addressing this difficult problem.

This thesis focuses on the Binary Integer Modulo-Division Algorithm that is essential for the permutation process in Sunar-Koc ONB Type II Multiplier and also for other general purposes. This thesis explains the new algorithm developed based on the systolic array architecture which gives a systematic approach to the iterative process for the Modulo-Division. The scheduling and projection timing functions are proposed for the processor array allocation and the matlab code has been implemented to verify the efficiency of the algorithm. The thesis also explores the possibility of word based algorithm for design optimisation. / Graduate / 0544 / 0984 / m.shubha8@gmail.com

Integer Programming problems are difficult to solve. The goal is to find an optimal solution that minimizes cost. With the help of Groebner based algorithms the optimal solution can be found if it exists. The application of the Groebner based algorithm and how it works is the topic of research. The Algorithms are The Conti-Traverso Algorithm and the Original Conti-Traverso Algorithm. Examples are given as well as proofs that correspond to the algorithms. The latter algorithm is more efficient as well as user friendly. The algorithms are not necessarily the best way to solve and integer programming problem, but they do find the optimal solution if it exists.

Virginia’s Department of Conservation and Recreation (DCR) assigns all of Virginia localities to Regional Offices to help conserve the natural resources in a certain region. In this paper, we present a mathematical model for optimizing such assignments by minimizing the travel time and cost of these assignments. With the growing increase in fuel costs and tighter budgets, our solution finds alternate assignments that will help cut costs by 14% annually. We have used integer programming techniques to find optimal assignments which satisfy requirements, respect limitations and minimize cost. Several plans are suggested, some keeping soil and water conservation districts together and some without.

Title: NP search problems Author: Tomáš Jirotka Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc. Abstract: The thesis summarizes known results in the field of NP search pro- blems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems. Keywords: Computational complexity, TFNP, integer factorization. 1

Mixed-integer programming provides a natural framework for modeling optimization problems which require discrete decisions. Valid inequalities, used as cutting-planes and cuttingsurfaces in integer programming solvers, are an essential part of today’s integer programming technology. They enable the solution of mixed-integer programs of greater scale and complexity by providing tighter mathematical descriptions of the feasible solution set. This dissertation presents new structural results on general-purpose valid inequalities for mixedinteger linear and mixed-integer conic programs. Cut-generating functions are a priori formulas for generating a cutting-plane from the data of a mixed-integer linear program. This concept has its roots in the work of Balas, Gomory, and Johnson from the 1970s. It has received renewed attention in the past few years. Gomory and Johnson studied cut-generating functions for the corner relaxation of a mixedinteger linear program, which ignores the nonnegativity constraints on the basic variables in a tableau formulation. We consider models where these constraints are not ignored. In our first contribution, we generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry, and periodicity. Our analysis also exposes shortcomings in the usual definition of minimality in our general setting. To remedy this, we consider stronger notions of minimality and show that these impose additional structure on cut-generating functions. A stronger notion than the minimality of a cut-generating function is its extremality. While extreme cut-generating functions produce powerful cutting-planes, their structure can be very complicated. For the corner relaxation of a one-row integer linear program, Gomory and Johnson identified continuous, piecewise linear, minimal cut-generating functions with only two distinct slope values as a “simple” class of extreme cut-generating functions. In our second contribution, we establish a similar result for a one-row problem which takes the nonnegativity constraint on the basic variable into account. In our third contribution, we consider a multi-row model where only continuous nonbasic variables are present. Conforti, Cornuéjols, Daniilidis, Lemaréchal, and Malick recently showed that not all cutting-planes can be obtained from cut-generating functions in this framework. They also conjectured a natural condition under which cut-generating functions might be sufficient. In our third contribution, we prove that this conjecture is true. This justifies the recent research interest in cut-generating functions for this model. Despite the power of mixed-integer linear programming, many optimization problems of practical and theoretical interest cannot be modeled using a linear objective function and constraints alone. Next, we turn to a natural generalization of mixed-integer linear programming which allows nonlinear convex constraints: mixed-integer conic programming. Disjunctive inequalities, introduced by Balas in the context of mixed-integer linear programming in the 1970s, have been a principal ingredient in the practical success of mixed-integer programming in the last two decades. In order to extend our understanding of disjunctive inequalities to mixed-integer conic programming, we pursue a principled study of two-term disjunctions on conic sets. In our fourth contribution, we consider two-term disjunctions on a general regular cone. A result of Kılınç-Karzan indicates that conic minimal valid linear inequalities are all that is needed for a closed convex hull description of such sets. First we characterize the structure of conic minimal and tight valid linear inequalities for the disjunction. Then we develop structured nonlinear valid inequalities for the disjunction by grouping subsets of valid linear inequalities. We analyze the structure of these inequalities and identify conditions which guarantee that a single such inequality characterizes the closed convex hull of the disjunction. In our fifth and sixth contributions, we extend our earlier results to the cases where the regular cone under consideration is a direct product of second order cones and nonnegative rays and where it is the positive semidefinite cone. Disjunctions on these cones deserve special attention because they provide fundamental relaxations for mixed-integer second-order cone and mixed-integer semidefinite programs. We identify conditions under which our valid convex inequalities can be expressed in computationally tractable forms and present techniques to generate low-complexity relaxations when these conditions are not satisfied. In our final contribution, we provide closed convex hull descriptions for homogeneous two-term disjunctions on the second-order cone and general two-term disjunctions on affine cross-sections of the second-order cone. Our results yield strong convex disjunctive inequalities which can be used as cutting-surfaces in generic mixed-integer conic programming solvers.