Numerical solution of singular perturbation problems via deviating arguments

We present a new approach to numerically solving linear, singularly perturbed two point boundary value problems in ordinary differential equations with a boundary layer on the left end of the interval. The original problem is divided into outer and inner region problems. A terminal boundary condition in the implicit form is derived. Then, the outer region problem is solved as a two point boundary value problem (TPBVP), and an explicit terminal boundary condition is obtained. In turn, a new inner region problem is obtained and solved as a TPBVP using the explicit terminal boundary condition. The proposed method is iterative on the terminal point of the inner region. Some numerical examples have been solved to demonstrate the applicability of the method.     

Efficient algorithms for buffer space allocation

This paper describes efficient algorithms for determining how buffer space should be allocated in a flow line. We analyze two problems: a primal problem, which minimizes total buffer space subject to a production rate constraint; and a dual problem, which maximizes production rate subject to a total buffer space constraint. The dual problem is solved by means of a gradient method, and the primal problem is solved using the dual solution. Numerical results are presented. Profit optimization problems are natural generalizations of the primal and dual problems, and we show how they can be solved using essentially the same algorithms.     

The use of hybrid techniques at CERFACS for the solution of large problems on parallel machines

Current problems in scientific computing often require the solution of sets of sparse linear equations of very large order. Particularly for three dimensional problems, it may to be impractical to solve them using a direct method but equally iterative methods may not converge and often standard preconditioning techniques do not work. We thus propose using a hybrid method by which we mean that either a nearby problem or a subproblem is solved by a direct method with the overall problem being solved by an iterative method. We discuss two applications of this at CERFACS in the solution of large scale problems from industry. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Approximate method for the numerical solution of singular perturbation problems

We present an approximate method for the numerical solution of linear singularly perturbed two point boundary value problems in ordinary differential equations with a boundary layer on the left end of the underlying interval. It is motivated by the asymptotic behavior of singular perturbation problems. The original problem is divided into inner and outer region problems. The reduced problem is solved to obtain the terminal boundary condition. Then, a new inner region problem is created and solved as a two point boundary value problem. In turn, the outer region problem is also modified and the resulting problem is efficiently treated by employing the trapezoidal formula coupled with discrete invariant imbedding algorithm. The proposed method is iterative on the terminal point. Some numerical experiments have been included to demonstrate its applicability.     

Iterative accelerating algorithms with Krylov subspaces for the solution to large-scale nonlinear problems

Discrete solution to nonlinear systems problems that leads to a series of linear problems associated with non-invariant large-scale sparse symmetric positive matrices is herein considered. Each linear problem is solved iteratively by a conjugate gradient method. We introduce in this paper new solvers (IRKS, GIRKS and D-GIRKS) that rely on an iterative reuse of Krylov subspaces associated with previously solved linear problems. Numerical assessments are provided on large-scale engineering applications. Considerations related to parallel supercomputing are also addressed. This revised version was published online in June 2006 with corrections to the Cover Date.     

A sequential parametric convex approximation method with applications to nonconvex truss topology design problems

We describe a general scheme for solving nonconvex optimization problems, where in each iteration the nonconvex feasible set is approximated by an inner convex approximation. The latter is defined using an upper bound on the nonconvex constraint functions. Under appropriate conditions, a monotone convergence to a KKT point is established. The scheme is applied to truss topology design (TTD) problems, where the nonconvex constraints are associated with bounds on displacements and stresses. It is shown that the approximate convex problem solved at each inner iteration can be cast as a conic quadratic programming problem, hence large scale TTD problems can be efficiently solved by the proposed method.     

最小化加权误工工件数的多代理平行分批排序

考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法.     

Airline crew scheduling from planning to operations

Crew scheduling problems at the planning level are typically solved in two steps: first, creating working patterns, and then assigning these to individual crew. The first step is solved with a set covering model, and the second with a set-partitioning model. At the operational level, the (re) planning period is considerably smaller than during the strategic planning phase. We integrate both models to solve time critical crew recovery problems arising on the day of operations. We describe how pairing construction and pairing assignment are done in a single step, and provide solution techniques based on simple tree search and more sophisticated column generation and shortest-path algorithms.     

Efficient Management of Multiple Sets to Extract Complex Structures from Mathematical Programs

Most of the applied models written with an algebraic modeling language involve simultaneously several dimensions such as materials, location, time or uncertainty. The information about dimensions available in the algebraic formulation is usually sufficient to retrieve different block structures from mathematical programs. These structured problems can then be solved by adequate solution techniques. To illustrate this idea we focus on stochastic programming problems with recourse. Taking into account both time and uncertainty dimensions of these problems, we are able to retrieve different customized structures in their constraint matrices. We applied the Structure Exploiting Tool to retrieve the structure from models built with the GAMS modeling language. The underlying mathematical programs are solved with the decomposition algorithm that applies interior point methods. The optimization algorithm is run in a sequential and in a parallel computing environment.     

On the Use of Augmented Lagrangians in the Solution of Generalized Semi-Infinite Min-Max Problems

We present an approach for the solution of a class of generalized semi-infinite optimization problems. Our approach uses augmented Lagrangians to transform generalized semi-infinite min-max problems into ordinary semi-infinite min-max problems, with the same set of local and global solutions as well as the same stationary points. Once the transformation is effected, the generalized semi-infinite min-max problems can be solved using any available semi-infinite optimization algorithm. We illustrate our approach with two numerical examples, one of which deals with structural design subject to reliability constraints.     

Gruppenkopplungen Mit Zyklischer Ausgangsgruppe Bzv7. Zyklischer Ableitung

Two problems are treated: (A) We look for all couplings of a finite cyclic group G. (B) We try to determine all finite groups G bearing couplings with cyclic derivations. These problems will be solved completely, if G is a p-group and nilpotent, respectively. The results enable us to construct couplings with cyclic Dickson groups.     

Numerical solution of a heat diffusion problem by boundary element methods using the Laplace transform

This paper is concerned with a heat diffusion problem in a half-space which is motivated by the detection of material defects using thermal measurements. This problem is solved by inverting the Laplace transform with respect to time on a contour in the complex plane using an exponentially convergent quadrature rule. This leads to a finite number of time-independent problems, which can be solved in parallel using boundary integral equation methods. We provide a full numerical analysis of this scheme on compact time intervals. Our results are formulated in a way that they can easily be used for other diffusion problems in exterior or interior domains.     

Numerical solution of the fully non-linear weakly dispersive serre equations for steep gradient flows

We demonstrate a numerical approach for solving the one-dimensional non-linear weakly dispersive Serre equations. By introducing a new conserved quantity the Serre equations can be written in conservation law form, where the velocity is recovered from the conserved quantities at each time step by solving an auxiliary elliptic equation. Numerical techniques for solving equations in conservative law form can then be applied to solve the Serre equations. We demonstrate how this is achieved. The system of conservation equations are solved using the finite volume method and the associated elliptic equation for the velocity is solved using a finite difference method. This robust approach allows us to accurately solve problems with steep gradients in the flow, such as those generated by discontinuities in the initial conditions.The method is shown to be accurate, simple to implement and stable for a range of problems including flows with steep gradients and variable bathymetry.     

Estimating the influence zone of a vertical magnetic dipole in aerial prospecting

We consider the direct problem of aerial electric sounding for a layered medium with a vertical cylindrical anomaly. We determine the minimum size of the anomaly when it is indistinguishable from an infinite layer of the same conductivity. The integral equation is solved by the integral current method. The concept of apparent conductivity is introduced for sounding problems using a magnetic dipole. The calculations support the conjecture of the locality of aerial sounding and prove the high efficiency of the integral current method for such problems.     

On the Stability of Sizing Optimization Problems for a Class of Nonlinearly Elastic Materials

In this work we deal with a stability aspect of sizing optimization problems for a class of nonlinearly elastic materials, where the underlying state problem is nonlinear in both the displacements and the stresses. In [14] it is shown under which conditions there exists a unique solution of discrete design problems for a body made of the considered nonlinear material, if the nonlinear state problem is solved exactly. In numerical examples the nonlinear state problem has to be solved iteratively, and therefore it can be solved only up to some small error \eps . The question of interest is how this affects the optimal solution, respectively the set of solutions, of the design problem. We show with the theory of point-to-set mappings that if the material is not too nonlinear, then the optimal design depends continuously on the error \eps . Accepted 15 March 2001. Online publication 14 August 2001.     

An analytical approach to global optimization

Global optimization problems with a few variables and constraints arise in numerous applications but are seldom solved exactly. Most often only a local optimum is found, or if a global optimum is detected no proof is provided that it is one. We study here the extent to which such global optimization problems can be solved exactly using analytical methods. To this effect, we propose a series of tests, similar to those of combinatorial optimization, organized in a branch-and-bound framework. The first complete solution of two difficult test problems illustrates the efficiency of the resulting algorithm. Computational experience with the programbagop, which uses the computer algebra systemmacsyma, is reported on. Many test problems from the compendiums of Hock and Schittkowski and others sources have been solved.The research of the first and the third authors has been supported by AFOSR grants #0271 and #0066 to Rutgers University. Research of the second author has been supported by NSERC grant #GP0036426 and FCAR grants #89EQ4144 and #90NC0305.     

A reduced Newton method for constrained linear least-squares problems

We propose an iterative method that solves constrained linear least-squares problems by formulating them as nonlinear systems of equations and applying the Newton scheme. The method reduces the size of the linear system to be solved at each iteration by considering only a subset of the unknown variables. Hence the linear system can be solved more efficiently. We prove that the method is locally quadratic convergent. Applications to image deblurring problems show that our method gives better restored images than those obtained by projecting or scaling the solution into the dynamic range.     

Symmetries of plane partitions

We introduce a new symmetry operation, called complementation, on plane partitions whose three-dimensional diagram is contained in a given box. This operation was suggested by work of Mills, Robbins, and Rumsey. There then arise a total of ten inequivalent problems concerned with the enumeration of plane partitions with a given symmetry. Four of these ten problems had been previously considered. We survey what is known about the ten problems and give a solution to one of them. The proof is based on the theory of Schur functions, in particular the Littlewood-Richardson rule. Of the ten problems, seven are now solved while the remaining three have conjectured simple solutions.     

具有时间与位置相关及维修限制的单机排序问题

考虑时间和位置相关的单机排序问题, 且机器具有退化的维修限制. 工件的实际加工时间是工件加工位置相关的函数, 目标函数为最大完工时间和总完工时间两个函数, 并利用匹配算法给出这两个问题的多项式时间算法. 最后得出工件满足一定条件时最大完工时间满足组平衡规则.     

Precedence constrained parallel-machine scheduling of position-dependent jobs

We consider parallel-machine job scheduling problems with precedence constraints. Job processing times are variable and depend on positions of jobs in a schedule. The objective is to minimize the maximum completion time or the total weighted completion time. We specify certain conditions under which the problem can be solved by scheduling algorithms applied earlier for fixed job processing times.