Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We study the preconditioning of symmetric indefinite linear systems of equations that arise in interior point solution of linear optimization problems. The preconditioning method that we study exploits the block structure of the augmented matrix to design a similar block structure preconditioner to improve the spectral properties of the resulting preconditioned matrix so as to improve the convergence rate of the iterative solution of the system. We also propose a two-phase algorithm that takes advantage of the spectral properties of the transformed matrix to solve for the Newton directions in the interior-point method. Numerical experiments have been performed on some LP test problems in the NETLIB suite to demonstrate the potential of the preconditioning method discussed.

Security constrained optimal active power flow via network model and interior point method

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Solving the multiobjective environmental/economic dispatch problem using weighted sum and ε-constraint strategies and a predictor-corrector primal-dual interior point method

This paper proposes a technique for solving the multiobjective environmental/economic dispatch problem using the weighted sum and ε-constraint strategies, which transform the problem into a set of single-objective problems. In the first strategy, the objective function is a weighted sum of the environmental and economic objective functions. The second strategy considers one of the objective functions: in this case, the environmental function, as a problem constraint, bounded above by a constant. A specific predictor-corrector primal-dual interior point method which uses the modified log barrier is proposed for solving the set of single-objective problems generated by such strategies. The purpose of the modified barrier approach is to solve the problem with relaxation of its original feasible region, enabling the method to be initialized with unfeasible points. The tests involving the proposed solution technique indicate i) the efficiency of the proposed method with respect to the initialization with unfeasible points, and ii) its ability to find a set of efficient solutions for the multiobjective environmental/economic dispatch problem.

Implementation of an interior point source in the ultra weak variational formulation through source extraction

The Ultra Weak Variational Formulation (UWVF) is a powerful numerical method for the approximation of acoustic, elastic and electromagnetic waves in the time-harmonic regime. The use of Trefftz-type basis functions incorporates the known wave-like behaviour of the solution in the discrete space, allowing large reductions in the required number of degrees of freedom for a given accuracy, when compared to standard finite element methods. However, the UWVF is not well disposed to the accurate approximation of singular sources in the interior of the computational domain. We propose an adjustment to the UWVF for seismic imaging applications, which we call the Source Extraction UWVF. Differing fields are solved for in subdomains around the source, and matched on the inter-domain boundaries. Numerical results are presented for a domain of constant wavenumber and for a domain of varying sound speed in a model used for seismic imaging.

Predictor-Corrector Primal-Dual Interior Point Method for Solving Economic Dispatch Problems: A Postoptimization Analysis

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Interior point method for long-term generation scheduling of large-scale hydrothermal systems

This paper presents an interior point method for the long-term generation scheduling of large-scale hydrothermal systems. The problem is formulated as a nonlinear programming one due to the nonlinear representation of hydropower production and thermal fuel cost functions. Sparsity exploitation techniques and an heuristic procedure for computing the interior point method search directions have been developed. Numerical tests in case studies with systems of different dimensions and inflow scenarios have been carried out in order to evaluate the proposed method. Three systems were tested, with the largest being the Brazilian hydropower system with 74 hydro plants distributed in several cascades. Results show that the proposed method is an efficient and robust tool for solving the long-term generation scheduling problem.

Interior point algorithm for linear programming used in transmission network synthesis

This article presents a well-known interior point method (IPM) used to solve problems of linear programming that appear as sub-problems in the solution of the long-term transmission network expansion planning problem. The linear programming problem appears when the transportation model is used, and when there is the intention to solve the planning problem using a constructive heuristic algorithm (CHA), ora branch-and-bound algorithm. This paper shows the application of the IPM in a CHA. A good performance of the IPM was obtained, and then it can be used as tool inside algorithm, used to solve the planning problem. Illustrative tests are shown, using electrical systems known in the specialized literature. (C) 2005 Elsevier B.V. All rights reserved.

Short term hydroelectric scheduling combining network flow and interior point approaches

In this paper, short term hydroelectric scheduling is formulated as a network flow optimization model and solved by interior point methods. The primal-dual and predictor-corrector versions of such interior point methods are developed and the resulting matrix structure is explored. This structure leads to very fast iterations since it avoids computation and factorization of impedance matrices. For each time interval, the linear algebra reduces to the solution of two linear systems, either to the number of buses or to the number of independent loops. Either matrix is invariant and can be factored off-line. As a consequence of such matrix manipulations, a linear system which changes at each iteration has to be solved, although its size is reduced to the number of generating units and is not a function of time intervals. These methods were applied to IEEE and Brazilian power systems, and numerical results were obtained using a MATLAB implementation. Both interior point methods proved to be robust and achieved fast convergence for all instances tested. (C) 2004 Elsevier Ltd. All rights reserved.

An adaptation of the dual-affine interior point method for the surface flatness problem

This paper presents an adaptation of the dual-affine interior point method for the surface flatness problem. In order to determine how flat a surface is, one should find two parallel planes so that the surface is between them and they are as close together as possible. This problem is equivalent to the problem of solving inconsistent linear systems in terms of Tchebyshev's norm. An algorithm is proposed and results are presented and compared with others published in the literature. (C) 2006 Elsevier B.V. All rights reserved.

Using interior point algorithms for the solution of linear programs with special structural features

Linear Programming (LP) is a powerful decision making tool extensively used in various economic and engineering activities. In the early stages the success of LP was mainly due to the efficiency of the simplex method. After the appearance of Karmarkar's paper, the focus of most research was shifted to the field of interior point methods. The present work is concerned with investigating and efficiently implementing the latest techniques in this field taking sparsity into account. The performance of these implementations on different classes of LP problems is reported here. The preconditional conjugate gradient method is one of the most powerful tools for the solution of the least square problem, present in every iteration of all interior point methods. The effect of using different preconditioners on a range of problems with various condition numbers is presented. Decomposition algorithms has been one of the main fields of research in linear programming over the last few years. After reviewing the latest decomposition techniques, three promising methods were chosen the implemented. Sparsity is again a consideration and suggestions have been included to allow improvements when solving problems with these methods. Finally, experimental results on randomly generated data are reported and compared with an interior point method. The efficient implementation of the decomposition methods considered in this study requires the solution of quadratic subproblems. A review of recent work on algorithms for convex quadratic was performed. The most promising algorithms are discussed and implemented taking sparsity into account. The related performance of these algorithms on randomly generated separable and non-separable problems is also reported.

100-Gb/s point-to-point solutions for long-reach passive optical networks in sparse rural and urban areas

Long reach-passive optical networks (LR-PON) are being proposed as a means of enabling ubiquitous fiber-to-the-home (FTTH) by massive sharing of network resources and therefore reducing per customer costs to affordable levels. In this paper, we analyze the chain solutions for LR-PON deployment in urban and rural areas at 100-Gb/s point-to-point transmission using dual polarization-quaternary phase shift-keying (DP-QPSK) modulation. The numerical analysis shows that with appropriate finite impulse response (FIR) filter designs, 100-Gb/s transmission can be achieved with at least 512 way split and up to 160 km total distance, which is sufficient for many of the optical paths in a practical situation, for point-to-point link from one LR-PON to another LR-PON through the optical switch at the metro nodes and across a core light path through the core network without regeneration.

Interior-exterior point method with global convergence strategy for solving the reactive optimal power flow problem

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems

We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the optimal solution, and (iv) the level of degeneracy of the optimal solution. We compute these measures for the SDPLIB suite problem instances and measure the correlation between these measures and IPM iteration counts (solved using the software SDPT3) when the measures have finite values. Our conclusions are roughly as follows: the aggregate geometry measure is highly correlated with IPM iterations (CORR = 0.896), and is a very good predictor of IPM iterations, particularly for problem instances with solutions of small norm and aspect ratio. The condition measure C(d) is also correlated with IPM iterations, but less so than the aggregate geometry measure (CORR = 0.630). The near-absence of strict complementarity is weakly correlated with IPM iterations (CORR = 0.423). The level of degeneracy of the optimal solution is essentially uncorrelated with IPM iterations.

Um método eficiente para resolução do problema de Despacho Ótimo de Reativos com controle discreto do TAP dos transformadores

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

A modified Primal-Dual Logarithmic-Barrier Method for solving the Optimal Power Flow problem with discrete and continuous control variables

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)