Local branching

The availability of effective exact or heuristic solution methods for general Mixed-Integer Programs (MIPs) is of paramount importance for practical applications. In the present paper we investigate the use of a generic MIP solver as a black-box ``tactical' tool to explore effectively suitable solution subspaces defined and controlled at a ``strategic' level by a simple external branching framework. The procedure is in the spirit of well-known local search metaheuristics, but the neighborhoods are obtained through the introduction in the MIP model of completely general linear inequalities called local branching cuts. The new solution strategy is exact in nature, though it is designed to improve the heuristic behavior of the MIP solver at hand. It alternates high-level strategic branchings to define the solution neighborhoods, and low-level tactical branchings to explore them. The result is a completely general scheme aimed at favoring early updatings of the incumbent solution, hence producing high-quality solutions at early stages of the computation. The method is analyzed computationally on a large class of very difficult MIP problems by using the state-of-the-art commercial software ILOG-Cplex 7.0 as the black-box tactical MIP solver. For these instances, most of which cannot be solved to proven optimality in a reasonable time, the new method exhibits consistently an improved heuristic performance: in 23 out of 29 cases, the MIP solver produced significantly better incumbent solutions when driven by the local branching paradigm. Mathematics Subject Classification (2000):90C06, 90C10, 90C11, 90C27, 90C59     

Numerical solution of the Burgers’ equation by automatic differentiation

We compute the solution of the one-dimensional Burgers’ equation by marching the solution in time using a Taylor series expansion. Our approach does not require symbolic manipulation and does not involve the solution of a system of linear or non-linear algebraic equations. Instead, we use recursive formulas obtained from the differential equation to calculate exact values of the derivatives needed in the Taylor series. We illustrate the effectiveness of our method by solving four test problems with known exact solutions. The numerical solutions we obtain are in excellent agreement with the exact solutions, while being superior to other previously reported numerical solutions.     

Analyzing and visualizing a discretized semilinear elliptic problem with Neumann boundary conditions

A semilinear elliptic equation dΔu ? u + u^p =0 over the unit ball in ?² with positive solution and the homogeneous Neumann boundary condition is considered. This equation models applications like chemotactic aggregation and biological pattern formation. Recent theoretical analyses on the equation suggest little continuous solution properties. Focusing on solving the discretized version of the equation, this work proposes an efficient algorithm that combines a newly developed discretization scheme on polar coordinates with a fast Fourier solver. An analysis of the induced matrix structures proves the algorithm converges to positive solutions; the analysis also establishes the q‐axial symmetry and monotonicity behavior of the solutions. Based on the q‐axial symmetry property, Numerical experiments were conducted to visualize various solution forms that are new to the best of our knowledge. The experiments also illustrated sensitivity behavior of the solutions. © 2002 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 18: 261–279, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/num.10006     

Lp-Lq time decay estimate to the solution of the Cauchy problem of the system of equations for nonlocal model of hyperbolic thermoelasticity theory

The aim of this paper is to present a new system of equations describing nonlocal model of hyperbolic thermoelasticity theory. We used the Papkin and Gurtin approach based on the constitutive relations for internal energy e(x), and heat flux q(x), with integral terms. Such system of equations describes the propagation of thermal perturbation with finite velocity. Using the modified Cagniard–de Hoop's method we constructed the matrix of fundamental solutions for this system of equations in three–dimensional space. Basing on the constructed matrix of fundamental solutions in the explicit formula we represent the solution of the Cauchy problem to this system of equations in the form of some kind of convolutions. Next, applying the method of Sobolev spaces, we obtain the L^p−L^q time decay estimate to the solution of the Cauchy problem. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Using and extending fix-and-relax to solve maritime inventory routing problems

The paper presents a new way of optimising maritime inventory routing problems (IRP) by using a heuristic approach based on fix-and-relax time decomposition extended with two new features. The purpose of the extensions is to reduce computation time during the fix-and-relax process and to improve solution quality after a first solution is found. The feature which improves solution quality is independent of the method used for calculating the first solution. In this study, the algorithm and extensions have been tested on four liquefied natural gas (LNG) cases and the impacts on computational time and objective function value are reported. The results show that using fix-and-relax reduces computing time considerably while the objective function value is only slightly worse compared to a general MILP solver. Furthermore, the results confirm that the extensions work according to the intentions when compared to the original fix-and-relax heuristic. For relatively complex cases, it appears advantageous to use the extensions developed.     

Lorenz‐gauged vector potential formulations for the time‐harmonic eddy‐current problem with L∞‐regularity of material properties

In this paper, we consider some Lorenz‐gauged vector potential formulations of the eddy‐current problem for the time‐harmonic Maxwell equations with material properties having only L^∞‐regularity. We prove that there exists a unique solution of these problems, and we show the convergence of a suitable finite element approximation scheme. Moreover, we show that some previously proposed Lorenz‐gauged formulations are indeed formulations in terms of the modified magnetic vector potential, for which the electric scalar potential is vanishing. Copyright © 2007 John Wiley & Sons, Ltd.     

High Performance Computing Techniques for the FEM Simulation in Structural Mechanics

For the solution of large scale simulations in structural mechanics iterative solving methods are mandatory. The efficiency of such methods can crucially depend on different factors: choice of material parameters, quality of the underlying computational mesh and number of processors in a parallel computing system. We distinguish between three aspects of ‘efficiency’: processor efficiency (degree to which the solving algorithm is able to exploit the processor's computational power), parallel efficiency (ratio between computation and communication times) and numerical efficiency (convergence behaviour). With the new FEM software package Feast we pursue the aim to develop a solver mechanism which at the same time gains high efficiencies in all three aspects, while trying to minimise the mentioned dependencies. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Dirichlet Problem for the Total Variation Flow

We introduce a new concept of solution for the Dirichlet problem for the total variational flow named entropy solution. Using Kruzhkov's method of doubling variables both in space and in time we prove uniqueness and a comparison principle in L¹ for entropy solutions. To prove the existence we use the nonlinear semigroup theory and we show that when the initial and boundary data are nonnegative the semigroup solutions are strong solutions.     

Weakly Nonlinear Geometric Optics for Hyperbolic Systems of Conservation Laws

We present a new approach to analyze the validation of weakly nonlinear geometric optics for entropy solutions of nonlinear hyperbolic systems of conservation laws whose eigenvalues are allowed to have constant multiplicity and corresponding characteristic fields to be linearly degenerate. The approach is based on our careful construction of more accurate auxiliary approximation to weakly nonlinear geometric optics, the properties of wave front-tracking approximate solutions, the behavior of solutions to the approximate asymptotic equations, and the standard semigroup estimates. To illustrate this approach more clearly, we focus first on the Cauchy problem for the hyperbolic systems with compact support initial data of small bounded variation and establish that the L ¹-estimate between the entropy solution and the geometric optics expansion function is bounded by O(?²), independent of the time variable. This implies that the simpler geometric optics expansion functions can be employed to study the behavior of general entropy solutions to hyperbolic systems of conservation laws. Finally, we extend the results to the case with non-compact support initial data of bounded variation.     

Two energy-conserving and compact finite difference schemes for two-dimensional Schrödinger-Boussinesq equations

In this paper, we study two compact finite difference schemes for the Schrödinger-Boussinesq (SBq) equations in two dimensions. The proposed schemes are proved to preserve the total mass and energy in the discrete sense. In our numerical analysis, besides the standard energy method, a “cut-off” function technique and a “lifting” technique are introduced to establish the optimal H¹ error estimates without any restriction on the grid ratios. The convergence rate is proved to be of O(τ² + h⁴) with the time step τ and mesh size h. In addition, a fast finite difference solver is designed to speed up the numerical computation of the proposed schemes. The numerical results are reported to verify the error estimates and conservation laws.

     

Supply capacity acquisition and allocation with uncertain customer demands

We study a class of capacity acquisition and assignment problems with stochastic customer demands often found in operations planning contexts. In this setting, a supplier utilizes a set of distinct facilities to satisfy the demands of different customers or markets. Our model simultaneously assigns customers to each facility and determines the best capacity level to operate or install at each facility. We propose a branch-and-price solution approach for this new class of stochastic assignment and capacity planning problems. For problem instances in which capacity levels must fall between some pre-specified limits, we offer a tailored solution approach that reduces solution time by nearly 80% over an alternative approach using a combination of commercial nonlinear optimization solvers. We have also developed a heuristic solution approach that consistently provides optimal or near-optimal solutions, where solutions within 0.01% of optimality are found on average without requiring a nonlinear optimization solver.     

Eigenvalues of a symmetric tridiagonal matrix: A divide-and-conquer approach

Summary The Symmetric Tridiagonal Eigenproblem has been the topic of some recent work. Many methods have been advanced for the computation of the eigenvalues of such a matrix. In this paper, we present a divide-and-conquer approach to the computation of the eigenvalues of a symmetric tridiagonal matrix via the evaluation of the characteristic polynomial. The problem of evaluation of the characteristic polynomial is partitioned into smaller parts which are solved and these solutions are then combined to form the solution to the original problem. We give the update equations for the characteristic polynomial and certain auxiliary polynomials used in the computation. Furthermore, this set of recursions can be implemented on a regulartree structure. If the concurrency exhibited by this algorithm is exploited, it can be shown that thetime for computation of all the eigenvalues becomesO(nlogn) instead ofO(n ²) as is the case for the approach where the order is increased by only one at every step. We address the numerical problems associated with the use of the characteristic polynomial and present a numerically stable technique for the eigenvalue computation.     

An efficient approach to solve very large dense linear systems with verified computing on clusters

Automatic result verification is an important tool to guarantee that completely inaccurate results cannot be used for decisions without getting remarked during a numerical computation. Mathematical rigor provided by verified computing allows the computation of an enclosure containing the exact solution of a given problem. Particularly, the computation of linear systems can strongly benefit from this technique in terms of reliability of results. However, in order to compute an enclosure of the exact result of a linear system, more floating‐point operations are necessary, consequently increasing the execution time. In this context, parallelism appears as a good alternative to improve the solver performance. In this paper, we present an approach to solve very large dense linear systems with verified computing on clusters. This approach enabled our parallel solver to compute huge linear systems with point or interval input matrices with dimensions up to 100,000. Numerical experiments show that the new version of our parallel solver introduced in this paper provides good relative speedups and delivers a reliable enclosure of the exact results. Copyright © 2014 John Wiley & Sons, Ltd.     

Ordinal Optimization of G/G/1/K Polling Systems with <Emphasis Type="Italic">k</Emphasis>-Limited Service Discipline

In this paper, we propose an ordinal optimization theory based algorithm to solve the optimization problem of G/G/1/K polling system with k-limited service discipline for a good enough solution using limited computation time. We assume that the arrival rates do not deteriorate visibly within a very short period. Our approach consists of two stages. In the first stage, we employ a typical genetic algorithm to select N=1024 roughly good solutions from the huge discrete solution space Ω using an offline trained artificial neural network as a surrogate model for fitness evaluation. The second stage consists of several substages to select estimated good enough solutions from the previous N, and the solution obtained in the last substage is the good enough solution that we seek. Using numerous tests, we demonstrate: (i) the computational efficiency of our algorithm in the aspect that we can apply our algorithm in real-time based on the arrival rate assumption; (ii) the superiority of the good enough solution, which achieves drastic objective value reduction in comparison with other existing service disciplines. We provide a performance analysis for our algorithm based on the derived models. The results show that the good enough solution that we obtained is among the best 3.31×10⁻⁶% in the solution space with probability 0.99. This research work was supported in part by the National Science Council of Taiwan, ROC, Grant NSC95-2221-E-009-099-MY2.     

Lp – Lq time decay estimate to the solution of the Cauchy problem for the system of equations describing nonlocal model of the thermoviscoelastic body

The aim of this paper is to present a new system of equations describing nonlocal model of thermoviscoelastic theory. We used the Papkin and Gurtin approach based on the constitutive relations for stress tensor σ(x), internal energy e(x) and heat flux q(x), with integral terms. Using the modified Cagniard-de Hoop's method we constructed the matrix of fundamental solutions for this system of equations in three-dimensional space. Basing on this matrix we represent in the explicit formula the solution of the Cauchy problem to this system of equations. Next, applying the method of Sobolev spaces, we proved the L^p–L^q time decay estimate to the solution of the Cauchy problem. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Sparse Approximations of the Schur Complement for Parallel Algebraic Hybrid Solvers in 3D

<正>In this paper we study the computational performance of variants of an algebraic additive Schwarz preconditioner for the Schur complement for the solution of large sparse linear systems.In earlier works,the local Schur complements were computed exactly using a sparse direct solver.The robustness of the preconditioner comes at the price of this memory and time intensive computation that is the main bottleneck of the approach for tackling huge problems.In this work we investigate the use of sparse approximation of the dense local Schur complements.These approximations are computed using a partial incomplete LU factorization.Such a numerical calculation is the core of the multi-level incomplete factorization such as the one implemented in pARMS. The numerical and computing performance of the new numerical scheme is illustrated on a set of large 3D convection-diffusion problems;preliminary experiments on linear systems arising from structural mechanics are also reported.     

A decision-theoretic approach to robust optimization in multivalued graphs

This paper is devoted to the search of robust solutions in finite graphs when costs depend on scenarios. We first point out similarities between robust optimization and multiobjective optimization. Then, we present axiomatic requirements for preference compatibility with the intuitive idea of robustness in a multiple scenarios decision context. This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of Lorenz optima, we show how the search can be embedded in algorithms designed to enumerate k best solutions. Then, we apply it in order to enumerate Lorenz optimal spanning trees and paths. We investigate possible refinements of Lorenz dominance and we propose an axiomatic justification of OWA operators in this context. Finally, the results of numerical experiments on randomly generated graphs are provided. They show the numerical efficiency of the suggested approach.     

Numerical simulation of bubble growth in a supersaturated solution

In this paper, a Volume of Fluid (VOF) based approach to simulate the growth of a pre-existing bubble in a supersaturated solution is developed and implemented in OpenFOAM^Ⓡ. The model incorporates the Compressive Continuous Species Transfer approach to describe the transport of dissolved gas and surface tension is treated using the Sharp Surface Force method. The driving force for bubble growth is defined using Fick’s 1^st law and a Sherwood number based correlation. The source terms for the governing equations are implemented by extending the work by Hardt and Wondra, J. Comp. Phys. 227 (2008) 5871–5895. The predictions of the proposed solver is compared against theoretical models for bubble growth in supersaturated solutions. The effect of spurious currents, which are generated while modelling surface tension, on bubble growth is also investigated. The proposed approach is used to model the growth of a rising bubble in the supersaturated solution.     

Accuracy of the Adomian decomposition method applied to the Lorenz system

In this paper, the Adomian decomposition method (ADM) is applied to the famous Lorenz system. The ADM yields an analytical solution in terms of a rapidly convergent infinite power series with easily computable terms. Comparisons between the decomposition solutions and the fourth-order Runge–Kutta (RK4) numerical solutions are made for various time steps. In particular we look at the accuracy of the ADM as the Lorenz system changes from a non-chaotic system to a chaotic one.     

On the utility of the homotopy analysis method for non-analytic and global solutions to nonlinear differential equations

In recent work on the area of approximation methods for the solution of nonlinear differential equations, it has been suggested that the so-called generalized Taylor series approach is equivalent to the homotopy analysis method (HAM). In the present paper, we demonstrate that such a view is only valid in very special cases, and in general, the HAM is far more robust. In particular, the equivalence is only valid when the solution is represented as a power series in the independent variable. As has been shown many times, alternative basis functions can greatly improve the error properties of homotopy solutions, and when the base functions are not polynomials or power functions, we no longer have that the generalized Taylor series approach is equivalent to the HAM. In particular, the HAM can be used to obtain solutions which are global (defined on the whole domain) rather than local (defined on some restriction of the domain). The HAM can also be used to obtain non-analytic solutions, which by their nature can not be expressed through the generalized Taylor series approach. We demonstrate these properties of the HAM by consideration of an example where the generalizes Taylor series must always have a finite radius of convergence (and hence limited applicability), while the homotopy solution is valid over the entire infinite domain. We then give a second example for which the exact solution is not analytic, and hence, it will not agree with the generalized Taylor series over the domain. Doing so, we show that the generalized Taylor series approach is not as robust as the HAM, and hence, the HAM is more general. Such results have important implications for how iterative solutions are calculated when approximating solutions to nonlinear differential equations.