Investment in electricity networks with transmission switching

We consider the application of Dantzig-Wolfe decomposition to stochastic integer programming problems arising in the capacity planning of electricity transmission networks that have some switchable transmission elements. The decomposition enables a column-generation algorithm to be applied, which allows the solution of large problem instances. The methodology is illustrated by its application to a problem of determining the optimal investment in switching equipment and transmission capacity for an existing network. Computational tests on IEEE test networks with 73 nodes and 118 nodes confirm the efficiency of the approach.     

Triangularity of the basis in linear programs for material requirements planning

It is shown that the basis in a class of linear programs arising from material requirements planning can be triangularized. This allows for efficient adaptation of the Simplex Method similar to those for network problems. It also suggests that for finite-loading (i.e. capacitated) MRP, a decomposition approach exploiting both subproblem structure and parallel processing can be effective for handling complex problems in multiproduct, multistage, multiperiod production systems.     

A constraint-based parallel local search for the edge-disjoint rooted distance-constrained minimum spanning tree problem

Many network design problems arising in areas as diverse as VLSI circuit design, QoS routing, traffic engineering, and computational sustainability require clients to be connected to a facility under path-length constraints and budget limits. These problems can be seen as instances of the rooted distance-constrained minimum spanning-tree problem (RDCMST), which is NP-hard. An inherent feature of these networks is that they are vulnerable to a failure. Therefore, it is often important to ensure that all clients are connected to two or more facilities via edge-disjoint paths. We call this problem the edge-disjoint RDCMST (ERDCMST). Previous work on the RDCMST has focused on dedicated algorithms and therefore it is difficult to use these algorithms to tackle the ERDCMST. We present a constraint-based parallel local search algorithm for solving the ERDCMST. Traditional ways of extending a sequential algorithm to run in parallel perform either portfolio-based search in parallel or parallel neighbourhood search. Instead, we exploit the semantics of the constraints of the problem to perform multiple moves in parallel by ensuring that they are mutually independent. The ideas presented in this paper are general and can be adapted to other problems as well. The effectiveness of our approach is demonstrated by experimenting with a set of problem instances taken from real-world passive optical network deployments in Ireland, Italy, and the UK. Our results show that performing moves in parallel can significantly reduce the elapsed time and improve the quality of the solutions of our local search approach.     

Network planning under uncertainty with an application to hydropower generation

Summary We present a general modeling framework for therobust optimization of linear network problems with uncertainty in the values of the right-hand side. In contrast to traditional approaches in mathematical programming, we use scenarios to characterize the uncertainty. Solutions are obtained for each scenario and these individual scenarios are aggregated to yield a nonanticipative or implementable policy that minimizes the regret of wrong decisions. A given solution is termed robust if it minimizes the sum over the scenarios of the weighted upper difference between the objective function value for the solution and the objective function value for the optimal solution for each scenario, while satisfying certain nonanticipativity constraints. This approach results in a huge model with a network submodel per scenario plus coupling constraints. Several decomposition approaches are considered, namely Dantzig-Wolfe decomposition, various types of Benders decomposition and different quadratic network approaches for approximating Augmented Lagrangian decomposition. We present computational results for these methods, including two implementation versions of the Lagrangian based method: a sequential implementation and a parallel implementation on a network of three workstations.     

Creating Advanced Bases For Large Scale Linear Programs Exploiting Embedded Network Structure

In this paper, we investigate how an embedded pure network structure arising in many linear programming (LP) problems can be exploited to create improved sparse simplex solution algorithms. The original coefficient matrix is partitioned into network and non-network parts. For this partitioning, a decomposition technique can be applied. The embedded network flow problem can be solved to optimality using a fast network flow algorithm. We investigate two alternative decompositions namely, Lagrangean and Benders. In the Lagrangean approach, the optimal solution of a network flow problem and in Benders the combined solution of the master and the subproblem are used to compute good (near optimal and near feasible) solutions for a given LP problem. In both cases, we terminate the decomposition algorithms after a preset number of passes and active variables identified by this procedure are then used to create an advanced basis for the original LP problem. We present comparisons with unit basis and a well established crash procedure. We find that the computational results of applying these techniques to a selection of Netlib models are promising enough to encourage further research in this area.     

Parallel Interior-Point Method for Linear and Quadratic Programs with Special Structure

This paper concerns the use of iterative solvers in interior-point methods for linear and quadratic programming problems. We state an adaptive termination rule for the inner iterative scheme and we prove the global convergence of the obtained algorithm, exploiting the theory developed for inexact Newton methods. This approach is promising for problems with special structure on parallel computers. We present an application on Cray T3E/256 and SGI Origin 2000/64 arising in stochastic linear programming and robust optimization, where the constraint matrix is block-angular and extremely large.     

Parallel iterative solvers for boundary value methods

A parallel variant of the block Gauss-Seidel iteration for the solution of block-banded linear systems is presented. The coefficient matrix is partitioned among the processors as in the domain decomposition methods and then it is split so that the resulting iterative method has the same spectral properties of the block Gauss-Seidel iteration.The parallel algorithm is applied to the solution of block-banded linear systems arising from the numerical discretization of initial value problems by means of Boundary Value Methods (BVMs). BVMs define a new approach for the solution of ordinary differential equations and seem to be attractive for their interesting stability properties and a possible parallel implementation. In this paper, we refer to BVMs based on the extended trapezoidal rules.     

Parallel interior-point solver for structured quadratic programs: Application to financial planning problems

Many practical large-scale optimization problems are not only sparse, but also display some form of block-structure such as primal or dual block angular structure. Often these structures are nested: each block of the coarse top level structure is block-structured itself. Problems with these characteristics appear frequently in stochastic programming but also in other areas such as telecommunication network modelling. We present a linear algebra library tailored for problems with such structure that is used inside an interior point solver for convex quadratic programming problems. Due to its object-oriented design it can be used to exploit virtually any nested block structure arising in practical problems, eliminating the need for highly specialised linear algebra modules needing to be written for every type of problem separately. Through a careful implementation we achieve almost automatic parallelisation of the linear algebra. The efficiency of the approach is illustrated on several problems arising in the financial planning, namely in the asset and liability management. The problems are modelled as multistage decision processes and by nature lead to nested block-structured problems. By taking the variance of the random variables into account the problems become non-separable quadratic programs. A reformulation of the problem is proposed which reduces density of matrices involved and by these means significantly simplifies its solution by an interior point method. The object-oriented parallel solver achieves high efficiency by careful exploitation of the block sparsity of these problems. As a result a problem with over 50 million decision variables is solved in just over 2 hours on a parallel computer with 16 processors. The approach is by nature scalable and the parallel implementation achieves nearly perfect speed-ups on a range of problems. Supported by the Engineering and Physical Sciences Research Council of UK, EPSRC grant GR/R99683/01     

Path-following gradient-based decomposition algorithms for separable convex optimization

A new decomposition optimization algorithm, called path-following gradient-based decomposition, is proposed to solve separable convex optimization problems. Unlike path-following Newton methods considered in the literature, this algorithm does not require any smoothness assumption on the objective function. This allows us to handle more general classes of problems arising in many real applications than in the path-following Newton methods. The new algorithm is a combination of three techniques, namely smoothing, Lagrangian decomposition and path-following gradient framework. The algorithm decomposes the original problem into smaller subproblems by using dual decomposition and smoothing via self-concordant barriers, updates the dual variables using a path-following gradient method and allows one to solve the subproblems in parallel. Moreover, compared to augmented Lagrangian approaches, our algorithmic parameters are updated automatically without any tuning strategy. We prove the global convergence of the new algorithm and analyze its convergence rate. Then, we modify the proposed algorithm by applying Nesterov’s accelerating scheme to get a new variant which has a better convergence rate than the first algorithm. Finally, we present preliminary numerical tests that confirm the theoretical development.     

Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time

This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first-stage approximation is solved by a branch-and-bound algorithm with its nodes inheriting Benders’ cuts that are valid for their ancestor nodes. In addition, we develop two closely related convexification schemes which use multi-term disjunctive cuts to obtain approximations of the second-stage mixed-integer programs. We prove that the proposed methods are finitely convergent. One of the main advantages of our decomposition scheme is that we use a Benders-based branch-and-cut approach in which linear programming approximations are strengthened sequentially. Moreover as in many decomposition schemes, these subproblems can be solved in parallel. We also illustrate these algorithms using several variants of an SMIP example from the literature, as well as a new set of test problems, which we refer to as Stochastic Server Location and Sizing. Finally, we present our computational experience with previously known examples as well as the new collection of SMIP instances. Our experiments reveal that our algorithm is able to produce provably optimal solutions (within an hour of CPU time) even in instances for which a highly reliable commercial MIP solver is unable to provide an optimal solution within an hour of CPU time.     

A constraint generation scheme to probabilistic linear problems with an application to power system expansion planning

In this paper, we first describe a constraint generation scheme for probabilistic mixed integer programming problems. Next, we present a decomposition approach to the peak capacity expansion planning of interconnected hydrothermal generating systems, with bounds on the transmission capacity between the regions. The objective is to minimize investments in generating units and interconnection links, subject to constraints on supply reliability. The problem is formulated as a stochastic integer program. The constraint generation scheme, which is similar to Benders decomposition, is applied in the solution of the peak capacity expansion problem. The master problem in this decomposition scheme is an integer program, solved by implicit enumeration. The operating subproblem corresponds to a stochastic network flow problem, and is solved by a maximum flow algorithm and Monte Carlo simulation. The approach is illustrated through a case study involving the expansion of the system of the Brazilian Southeastern region.     

A domain decomposition method for linear exterior boundary value problems

In this paper, we present a domain decomposition method, based on the general theory of Steklov-Poincaré operators, for a class of linear exterior boundary value problems arising in potential theory and heat conductivity. We first use a Dirichlet-to-Neumann mapping, derived from boundary integral equation methods, to transform the exterior problem into an equivalent mixed boundary value problem on a bounded domain. This domain is decomposed into a finite number of annular subregions, and the Dirichlet data on the interfaces is introduced as the unknown of the associated Steklov-Poincaré problem. This problem is solved with the Richardson method by introducing a Dirichlet-Robin-type preconditioner, which yields an iteration-by-subdomains algorithm well suited for parallel computations. The corresponding analysis for the finite element approximations and some numerical experiments are also provided.     

Plant location with minimum inventory

We present an integer programming model for plant location with inventory costs. The linear programming relaxation has been solved by Dantzig-Wolfe decomposition. In this case the subproblems reduce to the minimum cut problem. We have used subgradient optimization to accelerate the convergence of the D-W algorithm. We present our experience with problems arising in the design of a distribution network for computer spare parts. In most cases, from a fractional solution we were able to derive integer solutions within 4% of optimality.     

Stochastic multi-site capacity planning of TFT-LCD manufacturing using expected shadow-price based decomposition

This paper presents a stochastic optimization model and efficient decomposition algorithm for multi-site capacity planning under the uncertainty of the TFT-LCD industry. The objective of the stochastic capacity planning is to determine a robust capacity allocation and expansion policy hedged against demand uncertainties because the demand forecasts faced by TFT-LCD manufacturers are usually inaccurate and vary rapidly over time. A two-stage scenario-based stochastic mixed integer programming model that extends the deterministic multi-site capacity planning model proposed by Chen et al. (2010) [1] is developed to discuss the multi-site capacity planning problem in the face of uncertain demands. In addition a three-step methodology is proposed to generate discrete demand scenarios within the stochastic optimization model by approximating the stochastic continuous demand process fitted from the historical data. An expected shadow-price based decomposition, a novel algorithm for the stage decomposition approach, is developed to obtain a near-optimal solution efficiently through iterative procedures and parallel computing. Preliminary computational study shows that the proposed decomposition algorithm successfully addresses the large-scale stochastic capacity planning model in terms of solution quality and computation time. The proposed algorithm also outperforms the plain use of the CPLEX MIP solver as the problem size becomes larger and the number of demand scenarios increases.     

Matrix decomposition MFS algorithms for elasticity and thermo-elasticity problems in axisymmetric domains

In this work, we propose an efficient matrix decomposition algorithm for the Method of Fundamental Solutions when applied to three-dimensional boundary value problems governed by elliptic systems of partial differential equations. In particular, we consider problems arising in linear elasticity in axisymmetric domains. The proposed algorithm exploits the block circulant structure of the coefficient matrices and makes use of fast Fourier transforms. The algorithm is also applied to problems in thermo-elasticity. Several numerical experiments are carried out.     

An interior-point Benders based branch-and-cut algorithm for mixed integer programs

We present an interior-point branch-and-cut algorithm for structured integer programs based on Benders decomposition and the analytic center cutting plane method (ACCPM). We show that the ACCPM based Benders cuts are both pareto-optimal and valid for any node of the branch-and-bound tree. The valid cuts are added to a pool of cuts that is used to warm-start the solution of the nodes after branching. The algorithm is tested on two classes of problems: the capacitated facility location problem and the multicommodity capacitated fixed charge network design problem. For the capacitated facility location problem, the proposed approach was on average 2.5 times faster than Benders-branch-and-cut and 11 times faster than classical Benders decomposition. For the multicommodity capacitated fixed charge network design problem, the proposed approach was 4 times faster than Benders-branch-and-cut while classical Benders decomposition failed to solve the majority of the tested instances.     

Vector and parallel computing for matrix balancing

Estimating the entries of a large matrix to satisfy a set of internal consistency relations is a problem with several applications in economics, urban and regional planning, transportation, statistics and other areas. It is known as theMatrix Balancing Problem. Matrix balancing applications arising from the estimation of telecommunication or transportation traffic and from multi-regional trade flows give rise to huge optimization problems. In this report, we show that the RAS algorithm can be specialized for vector and parallel computing and used for the solution of very large problems. The algorithm is specialized for vector computations on a CRAY X-MP and is parallelized on an Alliant FX/8. A variant of the algorithm — developed here for its potential parallelism — turns out to be more efficient than the original algorithm even when implemented serially. We use the algorithms to estimate disaggregated input/output tables and a multi-regional trade flow table of the U.S. The larger problem solved has approximately 12 000 constraints and over 370 000 nonlinear variables. This is the first of two papers that aim at the solution of very large matrix balancing problems. Zenios [20] is using the same algorithm for the same models on a massively parallel Connection Machine CM-2.Research partially supported by NSF grants ECS-8718971 and CCR-8811135, and AFOSR grant 89-0145. Computing resources were made available through the ACRF at Argonne National Laboratory and CRAY Research, Inc.     

Bidiagonal decomposition of totally positive Bernstein-Vandermonde matrices

The class of Bernstein-Vandermonde matrices (a generalization of Vandermonde matrices arising when the monomial basis is replaced by the Bernstein basis) is considered. A convenient ordering of their rows makes these matrices strictly totally positive. By using results related to total positivity and Neville elimination, an algorithm for computing the bidiagonal decomposition of a Bernstein-Vandermonde matrix is constructed. The use of explicit expressions for the determinants involved in the process serves to make the algorithm both fast and accurate. One of the applications of our algorithm is the design of fast and accurate algorithms for solving Lagrange interpolation problems when using the Bernstein basis, an approach useful for the field of Computer Aided Geometric Design since it avoids the stability problems involved with basis transformations between the Bernstein and the monomial bases. A different application consists of the use of the bidiagonal decomposition as an intermediate step of the computation of the eigenvalues and the singular value decomposition of a totally positive Bernstein-Vandermonde matrix. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A General Decomposition Algorithm for Parallel Queues with Correlated Arrivals

Queueing with correlated arrivals occurs when customers arrive at a set of queues simultaneously. The difficulty in analyzing systems with correlated arrivals is due to the fact that the individual queueing systems are stochastically dependent. Exact methods for analyzing these systems are computationally intensive and are limited to only a few special cases. In this paper, we consider a system of parallel queues with bulk service and correlated arrivals. We show how the matrix-geometric approach can be used to obtain the performance measures of the system. We also develop an algorithm for large systems that efficiently approximates the performance measures by decomposing it into individual queueing systems. Finally, we describe how the principles of our decomposition algorithm can be extended to analyze a variety of different parallel queueing systems with correlated arrivals. We then evaluate the accuracy of our algorithm through a numerical study.     

An improved Benders decomposition applied to a multi-layer network design problem

Benders decomposition has been widely used for solving network design problems. In this paper, we use a branch-and-cut algorithm to improve the separation procedure of Gabrel et al. and Knippel et al. for capacitated network design. We detail experiments on bi-layer networks, comparing with Knippel’s previous results.