New lower bounds for the three-dimensional finite bin packing problem

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.     

Solution of the stationary problem of heat conduction of laminated anisotropic inhomogeneous plates by the method of initial functions

The problem of stationary heat conduction of laminated plates of constant and variable thickness is formulated in the three-dimensional statement. We reduce the three-dimensional problem to a twodimensional one by the method of initial functions. For plates with layers of variable thickness, a system of resolving equations with variable coefficients is obtained. The obtained two-dimensional boundary-value problems are analyzed. For plates with homogeneous layers of constant thickness, we construct a solution in an analytic form. It is shown that this solution coincides with a solution obtained by the method of separation of variables.     

Differential operator related to the generalized superradiance integral equation

In this paper we consider a class of problems which are generalized versions of the three-dimensional superradiance integral equation. A commuting differential operator will be found for this generalized problem. For the three-dimensional superradiance problem an alternative set of complete eigenfunctions will also be provided. The kernel for the superradiance problem when restricted to one-dimension is the same as appeared in the works of Slepian, Landau and Pollak (cf. Slepian and Pollak (1961) [1], Landau and Pollak (1961, 1962) [2] and [3], Slepian (1964, 1978) [4] and [5]). The uniqueness of the differential operator commuting with that kernel is indicated.     

A vorticity-velocity variational formulation for the exterior stokes problem in weighted sobolev spaces

In this article, we present a mixed variational formulation for the exterior Stokes problem in terms of the velocity and vorticity variables in the two and three-dimensional cases. The existence and the uniqueness of solutions of the variational problem are proved, as well as the equivalence with the primitive variables formulation.     

On Finite Element Methods for Inhomogeneous Dielectric Waveguides

We investigate the problem of computing electromagnetic guided waves in a closed,inhomogeneous, pillared three-dimensional waveguide at a given frequency. The problem is formulated as a generalized eigenvalue problem. By modifying the sesquilinear form associated with the eigenvalue problem, we provide a new convergence analysis for the finite element approximations. Numerical results are reported to illustrate the performance of the method.     

装箱问题的算法及最新进展

装箱问题在经济社会发展中扮演着重要的角色,该问题研究的是寻找较好的布局方式,尽可能实现利益的最大化.装箱问题具有NP-难性质,其理论和应用研究存在一定的挑战,但因其有广泛的应用背景而受到研究者高度的关注.本文主要总结近几十年来装箱问题的研究成果,特别针对一维、二维和三维单目标装箱问题和算法,以及多目标装箱问题的算法进行概括和总结,并提出装箱问题算法上有待进一步的研究工作.     

Solution of the Cauchy Problem for the Three-Dimensional Telegraph Equation and Exact Solutions of Maxwell’s Equations in a Homogeneous Isotropic Conductor with a Given Exterior Current Source

For the solution of the Cauchy problem for the linear telegraph equation in three-dimensional space, we derive a formula similar to the Kirchhoff one for the linear wave equation (and turning into the latter at zero conductivity). Additionally, the problem of determining the field of a given exterior current source in an infinite homogeneous isotropic conductor is reduced to a generalized Cauchy problem for the three-dimensional telegraph equation. The derived formula enables us to reduce this problem to quadratures and, in some cases, to obtain exact three-dimensional solutions with a propagating front, which are of great applied importance for testing numerical methods for solving Maxwell’s equations. As an example, we construct the exact solution of the field from a Hertzian dipole with an arbitrary time dependence of the current in an infinite homogeneous isotropic conductor.     

On the computation of protein backbones by using artificial backbones of hydrogens

NMR experiments provide information from which some of the distances between pairs of hydrogen atoms of a protein molecule can be estimated. Such distances can be exploited in order to identify the three-dimensional conformation of the molecule: this problem is known in the literature as the Molecular Distance Geometry Problem (MDGP). In this paper, we show how an artificial backbone of hydrogens can be defined which allows the reformulation of the MDGP as a combinatorial problem. This is done with the aim of solving the problem by the Branch and Prune (BP) algorithm, which is able to solve it efficiently. Moreover, we show how the real backbone of a protein conformation can be computed by using the coordinates of the hydrogens found by the BP algorithm. Formal proofs of the presented results are provided, as well as computational experiences on a set of instances whose size ranges from 60 to 6000 atoms.     

THE GLOBAL ARTIFICIAL BOUNDARY CONDITIONS FOR NUMERICAL SIMULATIONS OF THE 3D FLOW AROUND A SUBMERGED BODY

We consider the numerical approximations of the three-dimensional steady potential flow around a body moving in a liquid of finite constant depth at constant speed and distance below a free surface in a channel. One vertical side is introduced as the up-stream artificial boundary and two vertical sides are introduced as the downstream arti-ficial boundaries. On the artificial boundaries, a sequence of high-order global artificial boundary conditions are given. Then the original problem is reduced to a problem defined on a finite computational domain, which is equivalent to a variational problem. After solving the variational problem by the finite element method, we obtain the numerical approximation of the original problem. The numerical examples show that the artificial boundary conditions given in this paper are very effective.     

A stream-function–vorticity variational formulation for the exterior Stokes problem in weighted Sobolev spaces

In this paper we derive a mixed variational formulation for the exterior Stokes problem in terms of the vorticity and stream function, or the vector potential in three dimensions. The main steps are the construction of the stream function (or vector potential) and the proof of the Babu?ka–Brezzi ‘inf-sup’ condition. The two- and three-dimensional cases are treated separately because the structure of the stream function differs substantially according to the number of dimensions considered. The conclusion of this work is that if the problem is set in the weighted Sobolev spaces of Hanouzet and Giroire, the analysis of the exterior Stokes problem is quite the same as if the domain were bounded.     

The nullspace method for the three-dimensional Stokes problem

In this paper, we present the preconditioned nullspace method for the iterative solution of the three-dimensional Stokes problem. In the nullspace method, the original saddle point system is reduced to a positive definite problem by representing the solution with respect to a basis of discretely divergence free vectors. The exact, explicit computation of such a basis typically has non-optimal (storage and computational) complexity. There exist some algorithms that exploit the sparsity of the matrix and work well for two dimensional problems but fail for three dimensions. Here, we will exploit an implicit representation of the nullspace basis which can be computed efficiently also in a three-dimensional setting, possibly only as an approximation. We will present some numerical results to illustrate the performance of the resulting solution method. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A model of a homogenized cavity corresponding to a multinozzle droplet generator for continuous ink-jet printers

We modelize the behavior of a vibrating fluid cavity. Small nozzles are uniformly distributed in one direction on a side of the cavity. By means of asymptotic expansion in powers of the smallest dimension of the cavity, including boundary layer terms, we get the convergence of the solution of the three-dimensional problem, as well as the convergence of the solution of the “homogenized” three-dimensional problem towards the solution of the same two-dimensional problem. Numerical experiments have been carried out in order to illustrate the previous theoretical results. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 821–842, 1998     

Electromagnetic Scattering in a Two-layered Medium

The object of this paper is to investigate the three-dimensional electro- magnetic scattering problems in a two-layered background medium. These problems have an important application in today＇s technology, such as to detect objects that are buried in soil. Here, we model both the exterior impedance problem and the inhomogeneous medium problem in R3. We establish uniqueness and existence for the solution of the two scattering problems, respectively.     

Spinorial Method of Terminal Control of Spatial Rotations

In this paper, we introduce the notion of three-dimensional generalized rotations. We obtain relations between the parameters of the spinor representation of the group of three-dimensional generalized rotations and the coordinates of the initial and terminal points of rotation. Simple relations between elements of a three-dimensional orthogonal matrix of the basic representation and the Euler angles, on the one hand, and the coordinates of the initial and terminal points of rotation, on the other hand, were derived. The spinor method of solution of the inverse kinematic problem for spatial mechanisms with spherical pairs is developed and the corresponding algorithm is proposed. The obtained results allow one to reduce the three-dimensional problem of spatial motion control to the one-dimensional problem. Simple adaptive algorithms are suggested, by means of which various partial problems on the terminal control are solved under various terminal conditions. New algorithms of control of spatial rotations of manipulating robots are studied.     

On the nature of turbulence in a problem on the motion of a fluid behind a ledge

In the present paper, we suggest a numerical method for the analysis of the motion of a viscous incompressible fluid under the transition to the turbulent mode for an example of the numerical solution of a three-dimensional space problem on the fluid flow behind a ledge for various values of the Reynolds number. We show that, at the initial stages, the turbulence in the problem is developed via successive bifurcations of generation of a stable cycle, two-dimensional tori, and then three-dimensional tori in the infinite-dimensional phase space of the system.     

Motion of a vortex filament in the half-space

A model equation for the motion of a vortex filament immersed in three-dimensional, incompressible and inviscid fluid is investigated as a preliminary attempt to model the motion of a tornado. We solve an initial–boundary value problem in the half-space, where we impose a boundary condition in which the vortex filament is allowed to move on the boundary.     

Numerical solution of the three-dimensional stationary diffraction problem for elastic waves

Three-dimensional problems concerning the propagation of stationary elastic oscillations in media with three-dimensional inclusions are solved numerically. By applying potential theory methods, the original problem is stated as a system of two singular vector integral equations for the unknown internal and external densities of auxiliary sources of waves. An approximate solution of the original problem is obtained by approximating the integral equations by a system of linear algebraic equations, which is then solved numerically. The underlying algorithm has the property of self-regularization, due to which a numerical solution is found without using cumbersome regularizing algorithms. Results of test computations and numerical experiments are presented that characterize the capabilities of this approach as applied to the diffraction of elastic waves in three-dimensional settings.     

Fluid-structure interaction: analysis of a 3-D compressible model

In this paper, we present an existence result of weak solutions for a three-dimensional problem of fluid-plate interaction in which we take into account the non linearity of the continuity equation. This non linearity does not allow, as is usually the case, to neglect the variations of the domain which leads us to study a problem defined on a time dependent domain.     

A version of Turán’s problem for positive definite functions of several variables

We present a systematic approach to solving the problem of affine homogeneity of real hypersurfaces in the three-dimensional complex space. This question is an important part of the general problem of holomorphic classification of homogeneous real hypersurfaces in three-dimensional complex spaces. In contrast to the two-dimensional case, the whole problem (just as its affine part) has not yet been fully studied, although there exist a large number of examples of homogeneous manifolds. We study only the class of tubular type surfaces, which is defined by conditions imposed on the 2-jet of their canonical equations and generalizes the class of tube manifolds. We discuss the procedure of describing all matrix Lie algebras corresponding to the homogeneous manifolds under consideration. In the class that we study, we distinguish four cases depending on the third-order Taylor coefficients of the canonical equations; in three of these cases, the Lie algebras and the corresponding affine homogeneous surfaces are completely described. The key point of the proposed approach is the solution of a large system of quadratic equations that corresponds to each of the homogeneous surfaces.     

New lower bounds for the three-dimensional orthogonal bin packing problem

In this paper, we consider the three-dimensional orthogonal bin packing problem, which is a generalization of the well-known bin packing problem. We present new lower bounds for the problem from a combinatorial point of view and demonstrate that they theoretically dominate all previous results from the literature. The comparison is also done concerning asymptotic worst-case performance ratios. The new lower bounds can be more efficiently computed in polynomial time. In addition, we study the non-oriented model, which allows items to be rotated.