An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts

This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation, pricing and cut generation. The third attempts to close the duality gap left by the first two procedures using a classical pricing and cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved by an integer programming solver. Computational results over the main instances from the literature show the effectiveness of the proposed algorithm.      

The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case

The Two-Dimensional Finite Bin Packing Problem (2BP) consists of determining the minimum number of large identical rectangles, bins, that are required for allocating without overlapping a given set of 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. In this paper we describe new lower bounds for the 2BP where the items have a fixed orientation and we show that the new lower bounds dominate two lower bounds proposed in the literature. These lower bounds are extended in Part II (see Boschetti and Mingozzi 2002) for a more general version of the 2BP where some items can be rotated by . Moreover, in Part II a new heuristic algorithm for solving both versions of the 2BP is presented and computational results on test problems from the literature are given in order to evaluate the effectiveness of the proposed lower bounds.     

Particle size Effects on Optical Transport through strongly scattering media

Measurements of transmission and enhanced backscattering from powder beds of α-AI ₂O₃ consisting of particles with different average sizes are reported. The values of the mean free path and the absorption length, as inferred from these measurements, are compared and good agreement between the two measurement is found when the internal reflections are properly taken into account. A particle size measurement method is suggested on the basis of the linear dependence found experimentally between the transport mean free path and the mean particle size.     

Correlation matrix of a completely polarized, statistically stationary electromagnetic field

It is shown that, for a 3 x 3 correlation matrix Wij(r, r, omega), (i, j = x, y, z) of the electric vector of a random, stationary electromagnetic field to represent a field that is completely polarized at a point r and frequency omega, each element of the matrix must factorize. More precisely, a necessary and sufficient condition for the correlation matrix to represent a fully polarized field at a point r is that the matrix has the form Wij(r, r, omega) = epsilon(i)*(r, omega)epsilon(j)(r, omega), where epsilon(i)(r, omega) (i = x, y, z) are deterministic functions, i.e., that all pairs of the Cartesian components of the electric field at a point r and frequency omega are completely correlated.     

Closed similarity Lorentzian affine manifolds

A affine manifold is an -dimensional affine manifold whose linear holonomy lies in the similarity Lorentzian group but not in the Lorentzian group. In this paper, we show that a compact affine manifold is incomplete. Let be the Lorentz form, and the map on defined by . We show that for a compact radiant affine manifold , if a connected component of intersects the image of the universal cover of by the developing map, then either or a connected component of , where is a hyperplane, is contained in this image.

     

Contributions to the quadratic assignment problem

Tree search procedures for solving the Koopmans Beckmann quadratic assignment problem (QAP) are unable to solve any reasonable size QAP's mainly because good quality lower bounds for this problem cannot be computed.The purpose of this paper is to propose a bounding technique based on the extraction from the QAP formulation, of a large linear assignment problem (which can then be solved optimally), leaving as a residual problem as ‘small’ a QAP as possible. The solution of this residual QAP can then be bounded by a separate procedure. This 2-step method produces improved bounds as compared with those produced by the direct application of the bounding algorithms to the original QAP. In addition, a procedure is described for the a priori fixing of variables in the QAP formulation, thus reducing the number of variables in the problem.     

Well-conditioned computation for H ∞ controller near the optimum

The present paper gives a procedure for determining a H optimal controller in the assumption that the game Riccati equations have stabilizing positive definite solutions at the optimum value. A specific feature of the construction is its first step consisting in balancing with respect to the positive definite stabilizing solutions of the Riccati equations. The justification is based on singular perturbations reduction.     

Numerical investigation of the submonolayer growth and relaxation of stepped Ag (110) and Au (110) surfaces

The terrace width distribution (TWD) as well as the adatom and island densities for some stepped fcc?(110) surfaces with parallel and equidistant steps of equal stiffness are studied by means of kinetic Monte Carlo simulations. Reliable energy barriers for surface diffusion are used. They have been calculated by means of many-body potentials derived within the second moment approximation to the tight-binding model. The effects of the temperature, atom deposition flux and surface diffusion on quantities of interest in the early stage of the surface evolution process have been singled out. In most cases, linear, logarithmic and power-law behaviors are recovered for the evolution of the step width and terrace defects. The TWD is well described by the Gaussian distribution (GD) in the domain of temperature investigated but deviates from the Generalized Wigner Distribution (GWD).     

New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem

The two-dimensional orthogonal non-guillotine cutting stockproblem (NGCP) appears in many industries (e.g. the wood andsteel industries) and consists of cutting a rectangular mastersurface into a number of rectangular pieces, each with a givensize and value. The pieces must be cut with their edges alwaysparallel to the edges of the master surface (orthogonal cuts).The objective is to maximize the total value of the pieces cut. New upper bounds on the optimal solution to the NGCP are described.The new bounding procedures are obtained by different relaxationsof a new mathematical formulation of the NGCP. Various proceduresfor strengthening the resulting upper bounds and reducing thesize of the original problem are discussed. The proposed newupper bounds have been experimentally evaluated on test problemsderived from the literature. Comparisons with previous boundingprocedures from the literature are given. The computationalresults indicate that these bounds are significantly betterthan the bounds proposed in the literature.