This thesis gives an overall survey of preprocessing and postprocessing techniques in linear optimization (LO) and its implementations in the software package McMaster Interior Point Method (McIPM). We first review the basic concepts and theorems in LO. Then we present all the techniques used in preprocessing and the corresponding operations in postprocessing. Further, we discuss the implementation issues in our software development. Finally we test a series of problems from the Netlib test set and compare our results with state of the art software, such as LIPSOL and CPLEX. / Thesis / Master of Science (MS)

This dissertation provides several techniques for solving a class of nonconvex optimization problems that arise in the thermal analysis of electronic chip packages. The topic is of interest because in systems containing delicate electronic components both performance and reliability are impacted by thermal behavior. A modeling paradigm, called Compact Thermal Modeling (CTM), has been demonstrated to show promise for accurately estimating steady state thermal behavior without resorting to computationally intensive finite element models or expensive direct experimentation. The CTM is a network model that gives rise to a nonconvex optimization problem. A solution to this nonconvex optimization problem provides a reasonably accurate characterization of the steady state temperature profile the chip will attain under arbitrary boundary conditions, which allows the system designer to model the application of a wide range of thermal design strategies with useful accuracy at reasonable computational cost. This thesis explores several approaches to solving the optimization problem. We present a heuristic technique that is an adaptation of the classical coordinate search method that has been adapted to run efficiently by exploiting the algebraic structure of the problem. Further, the heuristic is able to avoid stalling in poor local optima by using a partitioning scheme that follows from an examination of special structure in the problem's feasible region. We next present several exact approaches using a globally optimal method based on the Reformulation Linearization Technique (RLT). This approach generates and then solves convex relaxations of the original problem, tightening the approximations within a branch and bound framework. We then explore several approaches to improving the performance of the RLT technique by introducing variable substitutions and valid inequalities, which tighten the convex relaxations. Computational results, conclusions, and recommendations for further research are also provided.

Digital medical atlases can contain anatomical information which is valuable for medical doctors in diagnosing and treating illnesses. The increased availability of such atlases has created an interest for computer algorithms which are capable of integrating such atlas information into patient specific dataprocessing. The field of medical image registration aim at calculating how to match one medical image to another. Here the atlas information could give important hints of which kinds of motion are plausible in different locations of the anatomy. Being able to incorporate such atlas specific information could potentially improve the matching of images and plausibility of image registration - ultimately providing a more correct information on which to base health care diagnosis and treatment decisions. In this licentiate thesis a generic signal processing framework is derived : Global Linear Optimization (GLO). The power of the GLO framework is first demonstrated quantitatively in a very high performing image denoiser. Important proofs of concepts are then made deriving and implementing three important capabilities regarding adaptive filtering of vector fields in medica limage registration: Global regularization with local anisotropic certainty metric. Allowing sliding motion along organ and tissue boundaries. Enforcing an incompressible motion in specific areas or volumes. In the three publications included in this thesis, the GLO framework is shown to be able to incorporate one each of these capabilities. In the third and final paper a demonstration is made how to integrate more and more of the capabilities above into the same GLO to perform adaptive processing on relevant clinical data. It is shown how each added capability improves the result of the image registration. In the end of the thesis there is a discussion which highlights the advantage of the contributions made as compared to previous methods in the scientific literature. / Dynamic Context Atlases for Image Denoising and Patient Safety

The modern theory of condition measures for convex optimization problems was initially developed for convex problems in conic format, and several aspects of the theory have now been extended to handle non-conic formats as well. In this theory, the (Renegar-) condition measure C(d) for a problem instance with data d=(A,b,c) has been shown to be connected to bounds on a wide variety of behavioral and computational characteristics of the problem instance, from sizes of optimal solutions to the complexity of algorithms. Herein we test the practical relevance of the condition measure theory, as applied to linear optimization problems that one might typically encounter in practice. Using the NETLIB suite of linear optimization problems as a test bed, we found that 71% of the NETLIB suite problem instances have infinite condition measure. In order to examine condition measures of the problems that are the actual input to a modern IPM solver, we also computed condition measures for the NETLIB suite problems after pre-preprocessing by CPLEX 7.1. Here we found that 19% of the post-processed problem instances in the NETLIB suite have infinite condition measure, and that log C(d) of the post-processed problems is fairly nicely distributed. Furthermore, there is a positive linear relationship between IPM iterations and log C(d) of the post-processed problem instances (significant at the 95% confidence level), and 42% of the variation in IPM iterations among the NETLIB suite problem instances is accounted for by log C(d) of the post-processed problem instances. / Singapore-MIT Alliance (SMA)

We introduce methods for dealing with linear programming (LP) problems with uncertain data, using the notion of weighted analytic centers. Our methods are based on high interaction with the decision maker (DM) and try to find solutions which satisfy most of his/her important criteria/goals. Starting with the drawbacks of different methods for dealing with uncertainty in LP, we explain how our methods improve most of them. We prove that, besides many practical advantages, our approach is theoretically as strong as robust optimization. Interactive cutting-plane algorithms are developed for concave and quasi-concave utility functions. We present some probabilistic bounds for feasibility and evaluate our approach by means of computational experiments.

A Residential Energy Management System (REMS) in smart grid provides capability to manage a daily load curve in order to reduce power consumption and energy cost. Consequently, (REMS) offers significant benefits for both the electricity suppliers and consumers in terms of control and schedule time of use of major appliances. In recent years, however, the rate of energy demand has increased rapidly throughout the world while the price of energy has been fluctuating. Numerous methods for (REMS) are used; this thesis analyzes many candidate scenarios during peak load periods comparing to the tariff to reduce the usage and its associated costs. It presents simulated results of proposed (REMS) to provide an automated least cost demand response. The main approach will be to ensure the satisfaction of the requirements with constraints on efficient use of energy. Multiphasic system behaviors of smart appliances in (REMS) with a realistic manner are proposed. / This thesis examines many mathematical models of home appliances in order to calculate the physical quantities that reflect the parameters’ impact and the system behavior. Main contribution determines the optimal solution of (TOU) problem to reduce energy cost and determine the best operation time by using (Linear optimization technique).

We introduce methods for dealing with linear programming (LP) problems with uncertain data, using the notion of weighted analytic centers. Our methods are based on high interaction with the decision maker (DM) and try to find solutions which satisfy most of his/her important criteria/goals. Starting with the drawbacks of different methods for dealing with uncertainty in LP, we explain how our methods improve most of them. We prove that, besides many practical advantages, our approach is theoretically as strong as robust optimization. Interactive cutting-plane algorithms are developed for concave and quasi-concave utility functions. We present some probabilistic bounds for feasibility and evaluate our approach by means of computational experiments.

[pt] Este trabalho está dividido em duas partes. A primeira parte trata das relações entre o problema de otimização d.c. (diferença de duas funções convexas) e o problema de otimização d.c. regularizado por inf-convolução, com núcleo (2 lambda)-1 l l . l l 2 , lambda > 0. Neste sentido se generaliza a relação de TOLAND (1979): inf { g(x) - h(x) } = inf { h(asterístico (y) - g (asterístico(y) }, H H E a relação de GABAY (1982): inf { g(x) - h(x) } = inf { g lambda (x) - h lambda (x) } H H Onde g, h , são funções convexas próprias e semicontínuas inferiormente, g(asterístico), h(asterístico), são conjugadas de g e h, respectivamente, H é um espaço de Hilbert real, e g (lambda), h lambda , são as funções regularizadas respectivas de g e h, por inf-convolução com núcleo (2 lambda)-1 l l . l l 2 , lambda > 0. A segunda parte deste trabalho apresenta um algoritmo novo para tratar com o problema de otimização d.c.. Trata-se de um método de descida do tipo proximal, onde se leva em consideração separadamente as propriedades de convexidade das duas funções convexas. / [en] The work is divided in two parts. The first part is concerned with the relationship between the d.c. optimization problem. In this sence we geralize the TOLAND´s relation (1979): inf { g(x) - h(x) } = inf { h(asteristic)(y) - g (asteristic)(y) }, H H And the GABAY´s relation (1982): inf { g(x) - h(x) } = inf { g lambda (x) - h lambda (x) } H H Where g, h, are l.s.c. convex functions, g(asteristic) and h(asteristic) are their conjugates, H is a real Hilbert space, and g lambda, h lambda, are the inf-convolution of g and h respectively, with the núcleos 8( . ) = (2 lambda)- 1 l l . l l 2 , lambda > 0. In the second part we present a new algorithm for dealing with d.c. functions. It is a descent method of proximal kind which takes in consideration the convex properties of the two convex functions separately

The purpose of this thesis is to provide a new scheduling model of a large constellation of imaging satellites that does not use a heuristic solving method. The objective is to create a mixed-integer linear model that would be competitive in speed and in its closeness to reality against a current model using simulated annealing, while trying to improve both models. Each satellite has the choice between a number of possible events, each event having a utility and a cost, and the chosen schedule must take into account numerous time-related constraints. The main difficulties appeared in modeling realistically a battery level and in handling infeasible configurations due to inaccurate parameters. The obtained linear model has enabled a better understanding of the performance of the simulated annealing solver, and could also be adapted to different real-world scheduling problems.

Linear optimization is concerned with maximizing, or minimizing, a linear objective function over a feasible region defined as the intersection of a finite number of hyperplanes. Pivot-based simplex methods and central-path following interior point methods are the computationally most efficient algorithms to solve linear optimization instances. Discrete optimization further assumes that some of the variables are integer-valued. This dissertation focuses on the geometric properties of the feasible region under some structural assumptions. In the first part, we consider lattice (d,k)-polytopes; that is, the convex hull of a set of points drawn from {0,1,...,k}^d, and study the largest possible diameter, delta(d,k), that a lattice (d,k)- polytope can achieve. We present novel properties and an enumeration algorithm to determine previously unknown values of delta(d,k). In particular, we determine the values for delta(3,6) and delta(5,3), and enumerate all the lattice (3,3)-polytopes achieving delta(3,3). In the second part, we consider the convex hull of all the 2^(2^d - 1) subsums of the 2^d - 1 nonzero {0,1}-valued vectors of length d, and denote by a(d) the number of its vertices. The value of a(d) has been determined until d =8 as well as asymptotically tight lower and upper bounds for loga(d). This convex hull forms a so-called primitive zonotope that is dual to the resonance hyperplane arrangement and belongs to a family that is conjectured to include lattice polytopes achieving the largest possible diameter over all lattice (d,k)-polytopes. We propose an algorithm exploiting the combinatorial and geometric properties of the input and present preliminary computational results. / Thesis / Doctor of Philosophy (PhD)