On the simplex algorithm ‘revised form’

The purpose of this paper is an amelioration of the ‘product form of the inverse’ related to the revised simplex method. We give an algorithm to compute the inverse of the current basic matrix. This calculation requires approximately m² operations by using a tensor product and matrix addition. We apply this idea to the Gauss and Gauss–Jordan algorithms.     

A unified analysis of stochastic gradient-free Frank–Wolfe methods

In this paper, we consider a class of constrained stochastic programs in which the gradient of the random function in the objective and the projection onto the feasible set are assumed to be prohibitive to compute. We propose a class of mini-batch gradient-free Frank–Wolfe methods. Under mild conditions, we conduct a unified convergence analysis for both convex and nonconvex problems.     

Stochastic switching for partially observable dynamics and optimal asset allocation

In industrial applications, optimal control problems frequently appear in the context of decision-making under incomplete information. In such framework, decisions must be adapted dynamically to account for possible regime changes of the underlying dynamics. Using stochastic filtering theory, Markovian evolution can be modelled in terms of latent variables, which naturally leads to high-dimensional state space, making practical solutions to these control problems notoriously challenging. In our approach, we utilise a specific structure of this problem class to present a solution in terms of simple, reliable, and fast algorithms. The algorithms presented in this paper have already been implemented in an R package.     

Hyperbolic Penalty: A New Method for Nonlinear Programming with Inequalities

This work intends to present and to analyze a new penalty method that purposes to solve the general nonlinear programming problem subject to inequality constraints. The proposed method has the important feature of being completely differentiable and combines features of both exterior and interior penalty methods. Numerical results for some problems are commented on.     

Improving a Lagrangian decomposition for the unconstrained binary quadratic programming problem

This paper presents a new alternative of Lagrangian decomposition based on column generation technique to solve the unconstrained binary quadratic programming problem. We use a mixed binary linear version of the original quadratic problem with constraints represented by a graph. This graph is partitioned into clusters of vertices forming subproblems whose solutions use the dual variables obtained by a coordinator problem. Computational experiments consider a set of difficult instances and the results are compared against other methods reported recently in the literature.     

Fully Lagrangian and Lattice Boltzmann Methods for the Advection-Diffusion Equation

In the last decade or so, the Lattice–Boltzmann method (LBM) has achieved great success in computational fluid dynamics. The Fully–Lagrangian method (FLM) is the generalization of LBM for conservation systems. LBM can also be developed from FLM. In this paper a FL model and a LB model are developed for D-dimensional advection-diffusion equation. The LB model can be viewed as an improved version of the FL model. Numerical results of simulation of 1-dimensional advection-diffusion equation are presented. The numerical results are found to be in good agreement with the analytic solution.     

State estimation using model order reduction for unstable systems

The problem of state estimation occurs in many applications of fluid flow. For example, to produce a reliable weather forecast it is essential to find the best possible estimate of the true state of the atmosphere. To find this best estimate a nonlinear least squares problem has to be solved subject to dynamical system constraints. Usually this is solved iteratively by an approximate Gauss–Newton method where the underlying discrete linear system is in general unstable. In this paper we propose a new method for deriving low order approximations to the problem based on a recently developed model reduction method for unstable systems. To illustrate the theoretical results, numerical experiments are performed using a two-dimensional Eady model – a simple model of baroclinic instability, which is the dominant mechanism for the growth of storms at mid-latitudes. It is a suitable test model to show the benefit that may be obtained by using model reduction techniques to approximate unstable systems within the state estimation problem.     

A two-stage stochastic integer programming model for a thermal power system expansion

In this paper the obtaining of an optimum policy in the capacity expansion planning of a particular thermal‐electric power system is proposed. Therefore, a two‐stage stochastic integer programming is formulated. The model includes, through a finite group of scenarios, the existent uncertainty related to the future availability of the thermal plants currently under operation. The resultant model is solved numerically by the application of the L‐shaped method, whose implementation and development were executed using the software AMPL, with CPLEX as a solver. The results reached are shown, which validate the use of the methodology adopted in this work.     

Stability and Duality of Nonconvex Problems via Augmented Lagrangian

A nonconvex mathematical programming problem on a topological linear space in the presence of an inequality constraint is considered. An augmented Lagrangian function is constructed by using supporting cones to the epigraph of a usual perturbation function. Extremal values of prime and dual problems are shown to be equivalent under the stability conditions derived.     

The ‘Idiot’ crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems

ABSTRACT

We provide the first meaningful documentation and analysis of the ‘Idiot’ crash implemented by Forrest in Clp that aims to obtain an approximate solution to linear programming (LP) problems for warm-starting the primal simplex method. The underlying algorithm is a penalty method with naive approximate minimization in each iteration. During initial iterations an approach similar to augmented Lagrangian is used. Later the technique corresponds closely to a classical quadratic penalty method. We discuss the extent to which it can be used to obtain fast approximate solutions of LP problems, in particular when applied to linearizations of quadratic assignment problems.     

Measuring the overhead of Intel C++ Concurrent Collections over Threading Building Blocks for Gauss–Jordan elimination

The most efficient way to parallelize computation is to build and evaluate the task graph constrained only by the data dependencies between the tasks. Both Intel's C++ Concurrent Collections (CnC) and Threading Building Blocks (TBB) libraries allow such task‐based parallel programming. CnC also adapts the macro data flow model by providing only single‐assignment data objects in its global data space. Although CnC makes parallel programming easier, by specifying data flow dependencies only through single‐assignment data objects, its macro data flow model incurs overhead. Intel's C++ CnC library is implemented on top of its C++ TBB library. We can measure the overhead of CnC by comparing its performance with that of TBB. In this paper, we analyze all three types of data dependencies in the tiled in‐place Gauss–Jordan elimination algorithm for the first time. We implement the task‐based parallel tiled Gauss–Jordan algorithm in TBB using the data dependencies analyzed and compare its performance with that of the CnC implementation. We find that the overhead of CnC over TBB is only 12%– 15% of the TBB time, and CnC can deliver as much as 87%– 89% of the TBB performance for Gauss–Jordan elimination, using the optimal tile size. Copyright © 2012 John Wiley & Sons, Ltd.     

Particle‐based simulation of bubbles in water–solid interaction

In this paper, a particle‐based multiphase method for creating realistic animations of bubbles in water–solid interaction is presented. To generate bubbles from gas dissolved in the water on the fly, we propose an approximate model for the creation of bubbles, which takes into account the influence of gas concentration in the water, the solid material, and water–solid velocity difference. As the air particle on the bubble surface is treated as a virtual nucleation site, the bubble absorbs air from surrounding water and grows. The density and pressure forces of air bubbles are computed separately using smoothed particle hydrodynamics; then, the two‐way coupling of bubbles with water and solid is solved by a new drag force, so the generated bubbles’ flow on the surface of solid and the deformation in the rising process can be simulated. Additionally, touching bubbles merge together under the cohesion forces weighted by the smoothing kernel and velocity difference. The experimental results show that this method is capable of simulating bubbles in water–solid interaction under different physical conditions. Copyright © 2012 John Wiley & Sons, Ltd.