Formulation and survey of ALE method in nonlinear solid mechanics

This paper investigates the applicability and accuracy of existing formulation methods in general purpose finite element programs to the finite strain deformation problems. The basic shortcomings in using such programs in these applications are then pointed out and the need for a different type of formulation is discussed. An arbitrary Lagrangian-Eulerian (ALE) method is proposed and a concise survey of ALE formulation is given. A consistent and complete ALE formulation is derived from the virtual work equation transformed to arbitrary computational reference configurations. Differences between the proposed formulations and similar ones in the literature are discussed. The proposed formulation presents a general approach to ALE method. It includes load correction terms and is suitable for rate-dependent and rate-independent material constitutive law. The proposed formulation reduces to both updated Lagrangian and Eulerian formulations as special cases.     

伪双曲方程的新混合有限元方法

构造分析一类二阶伪双曲方程的H1-Galerkin扩展混合有限元方法,该方法采用了扩展混合有限元方法和H1-Galerkin混合有限元方法相结合的技巧.新的格式同时保持了扩展混合有限元方法和H1-Galerkin混合有限元方法的优点.该混合格式与标准的混合格式相比能同时逼近三个变量:未知函数、梯度和流量(系数乘以梯度),并且不必满足LBB相容性条件.     

A NEW DETERMINISTIC FORMULATION FOR DYNAMIC STOCHASTIC PROGRAMMING PROBLEMS AND ITS NUMERICAL COMPARISON WITH OTHERS

A new deterministic formulation, called the conditional expectation formulation, is proposed for dynamic stochastic programming problems in order to overcome some disadvantages of existing deterministic formulations. We then check the impact of the new deterministic formulation and other two deterministic formulations on the corresponding problem size, nonzero elements and solution time by solving some typi     

A kinetic formulation for a model coupling free surface and pressurised flows in closed pipes

The aim of this paper is to present a kinetic formulation of a model for the coupling of transient free surface and pressurised flows. Firstly, we revisit the system of Saint-Venant equations for free surface flow: we state some properties of Saint-Venant equations, we propose a kinetic formulation and we verify that this kinetic formulation leads to a Gibbs equilibrium that minimises (in some general case) an energy and preserves the still water steady state. Secondly, we propose a model for pressurised flows in a Saint-Venant-like conservative formulation. We then propose a kinetic formulation and we verify that this kinetic formulation leads to a Gibbs equilibrium that minimises in any case an energy and preserves the still water steady state. Finally, we propose a dual model that couples these two types of flow.     

Robust empty container repositioning considering foldable containers

Because of the extreme imbalance in intercontinental trade, the repositioning of empty containers creates a significant problem for shipping companies. There are many efforts to reduce the cost of repositioning empty containers, one of which is a foldable container. This paper proposes a robust formulation for the empty container repositioning problem considering foldable containers under demand uncertainty. The robust formulation can be used as a tractable approximation of a multistage stochastic programming formulation which is computationally intractable. Moreover, the robust formulation requires only limited information about the distribution of demand to replicate real-world situations. Computational results show that the proposed formulation performs well in terms of operating costs and there exists a significant cost-saving effect when foldable containers are used in maritime transportation.     

A penalty method for rank minimization problems in symmetric matrices

The problem of minimizing the rank of a symmetric positive semidefinite matrix subject to constraints can be cast equivalently as a semidefinite program with complementarity constraints (SDCMPCC). The formulation requires two positive semidefinite matrices to be complementary. This is a continuous and nonconvex reformulation of the rank minimization problem. We investigate calmness of locally optimal solutions to the SDCMPCC formulation and hence show that any locally optimal solution is a KKT point. We develop a penalty formulation of the problem. We present calmness results for locally optimal solutions to the penalty formulation. We also develop a proximal alternating linearized minimization (PALM) scheme for the penalty formulation, and investigate the incorporation of a momentum term into the algorithm. Computational results are presented.     

A div-curl formulation of the stokes boundary value problem based on a harmonic representation formula

On a two-dimensional domain, we establish a div-curl formulation for the Stokes Dirichlet boundary value problem. The derivation of this formulation is based on a Harmonic representation formula given by Kratz. Existence and uniqueness of solutions for the div-curl formulation are proved.     

On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times

Several mixed integer programming formulations have been proposed for modeling capacitated multi-level lot sizing problems with setup times. These formulations include the so-called facility location formulation, the shortest route formulation, and the inventory and lot sizing formulation with (?, S) inequalities. In this paper, we demonstrate the equivalence of these formulations when the integrality requirement is relaxed for any subset of binary setup decision variables. This equivalence has significant implications for decomposition-based methods since same optimal solution values are obtained no matter which formulation is used. In particular, we discuss the relax-and-fix method, a decomposition-based heuristic used for the efficient solution of hard lot sizing problems. Computational tests allow us to compare the effectiveness of different formulations using benchmark problems. The choice of formulation directly affects the required computational effort, and our results therefore provide guidelines on choosing an effective formulation during the development of heuristic-based solution procedures.     

一类单边约束问题的数值方法

本文分别基于原始变分形式与对偶混合变分形式，对一类单边约束问题进行了数值求解，提出了求解离散对偶混合变分问题的Uzawa型算法，并用数值例子验证了算法的有效性．     

二维土壤溶质输运方程的有限体积元格式

本文导出二维的土壤溶质输运方程的有限体积元格式, 并分析其误差.通过数值例子说明, 有限体积元格式比有限元格式稳定.     

A note on a quadratic formulation for linear complementarity problems

In this note, we discuss some properties of a quadratic formulation for linear complementarity problems. Projected SOR methods proposed by Mangasarian apply to symmetric matrices only. The quadratic formulation discussed here makes it possible to use these SOR methods for solving nonsymmetric LCPs. SOR schemes based on this formulation preserve sparsity. For proper choice of a free parameter, this quadratic formulation also preserves convexity. The value of the quadratic function for the solution of original LCP is also known.     

A simplification for some disjunctive formulations

We give sufficient conditions under which a relatively compact integer formulation can be obtained for some instances of multiple-right-hand-side constraints, with the special property that the linear relaxation of this formulation is as small (tight) as possible among all integer formulations. The formulation we obtain is a simplification of the disjunctive formulation, and requires exactly as many additional (nonnegative) variables as alternative r.h.s., with one additional constraint. We conclude with several applications of our results.     

On the analytic representation of the Leximin ordering and its application to flexible constraint propagation

We discuss the basic formulation of constraint propagation problems and extend it to the flexible constraint propagation environment where constraints are represented as fuzzy subsets. Some methods for ordering alternative solutions with respect to a collection of flexible constraints are discussed along with their drawbacks. Among the methods introduced is the Leximin method where we note its lack of an analytic formulation. With the aid of the ordered weighted averaging (OWA) operator we suggest an analytic formulation for the Leximin method. Some properties of this formulation are provided. We then describe the application of this new formulation for the Leximin method to situations in which the constraints are describable in a linear fashion. We show how we can use mixed integer programming techniques to find an optimal solution.     

Column Generation for Extended Formulations

Working in an extended variable space allows one to develop tight reformulations for mixed integer programs (MIP). However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. When the extended formulation stems from a decomposition principle, as typical in practice, a column generation procedure that mimics that for the Dantzig-Wolfe reformulation can be applied to the extended formulation. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solution. Such “column-and-row generation” procedure is reviewed with the goal to analyse the approachʼs potential benefits compared to a standard column generation approach. Numerical experiments highlight a key observation: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.     

Multicommodity network flows: The impact of formulation on decomposition

This paper investigates the impact of problem formulation on Dantzig—Wolfe decomposition for the multicommodity network flow problem. These problems are formulated in three ways: origin-destination specific, destination specific, and product specific. The path-based origin-destination specific formulation is equivalent to the tree-based destination specific formulation by a simple transformation. Supersupply and superdemand nodes are appended to the tree-based product specific formulation to create an equivalent path-based product specific formulation. We show that solving the path-based problem formulations by decomposition results in substantially fewer master problem iterations and lower CPU times than by using decomposition on the equivalent tree-based formulations. Computational results on a series of multicommodity network flow problems are presented.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

A New Formulation for Spanning Trees

Spanning trees are fundamental structures in graph theory. Furthermore, computing them is a central part in many relevant algorithms, used in either practical or theoretical applications. The classical Minimum Spanning Tree problem is solvable in polynomial time but almost all of its variants are NP-Hard. In this paper, a novel polynomial size mixed integer linear programming formulation is introduced for spanning trees. This formulation is based on a new characterization we propose for acyclic graphs. Preliminary computational results show that this formulation is capable of solving small instances of the diameter constrained minimum spanning tree problem. It should be possible to strengthen the formulation to tackle larger instances of that problem. Additionally, our spanning tree formulation may prove to be a more effective model for some related applications.     

A Note on the Set Covering Problem

A previously published work on a ‘probabilistic’ formulation of the set covering problem is discussed. Attention is drawn to the dependence of the feasible locations of facilities on the way the continuous space of incidents is divided into subregions when using either the above formulation or the standard deterministic formulation of the set covering problem.     

A boundary integral formulation of the Stefan problem

This paper considers a boundary integral formulation of the Stefan problem for two spatial dimensions. This formulation has the advantage that its numerical implementation does not require the discretization of the Stefan condition. Furthermore, the formulation is capable of solving problems with complex boundaries. Several illustrative examples are given.     

非饱和土壤水流问题的CN有限元格式

首先给出二维非饱和土壤水流问题基于Crank-Nicolson(CN)方法的具有时间二阶精度的半离散化格式,然后直接从CN时间半离散化格式出发,建立具有时间二阶精度的全离散化CN有限元格式,并给出误差估计,最后用数值例子说明全离散化CN有限元格式的优越性.这种方法可以绕开关于空间变量的半离散化格式的讨论,提高时间离散的精度,极大地减少时间方向的迭代步,从而减少实际计算中截断误差的积累,提高计算精度和计算效率.