Risk models for the Prize Collecting Steiner Tree problems with interval data

Given a connected graph G=(V,E)with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree(PCST)problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c+e]while taking risk(c+e xe)/(c+e c e)of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p+v]for its inclusion in T while taking risk(yv p v)/(p+v p v)of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.     

Interactive Diffusions for Global Optimization

We present a novel approach, in which parallel annealing processes interact in a manner that expedites the identification of a globally optimal solution. A first annealing process operates at a faster time scale and has a drift function that converges to a non-zero (but relatively small) noise level. A second annealing process (operating at a slower time scale) is subject to a modified drift term in which the steepest descent direction is perturbed with the first annealing process density gradient. This additional term ensures that the second process is “repelled” from regions already explored. As a result, the first annealing process (which quickly identifies locally optimal solutions) allows the second annealing process to bypass locally optimal solutions recently identified, so that it can be made to converge to global optima at a faster rate. We show that, when compared to independent annealing processes, the proposed interactive diffusions can increase the speed of convergence at the expense of minimal additional computational overhead.     

Analyzing completeness of axiomatic functional systems for temporal × modal logics

In previous works, we presented a modification of the usual possible world semantics by introducing an independent temporal structure in each world and using accessibility functions to represent the relation among them. Different properties ofthe accessibility functions (being injective, surjective, increasing, etc.) have been considered and axiomatic systems (called functional) which define these properties have been given. Only a few ofthese systems have been proved tobe complete. The aim ofthis paper is to make a progress in the study ofcompleteness for functional systems. For this end, we use indexes as names for temporal flows and give new proofs of completeness. Specifically, we focus our attention on the system which defines injectivity, because the system which defines this property without using indexes was proved to be incomplete in previous works. The only system considered which remains incomplete is the one which defines surjectivity, even ifwe consider a sequence ofnatural extensions ofthe previous one (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On elliptic equations with piecewise constant coefficients

In this work we prove an existence and uniqueness theorem for solutions in ²(R^t) of second order elliptic equations with coefficients that are constant on the half-spaces R+ⁿ and R ?ⁿ     

Lower bounds on the number of crossing-free subgraphs of KN

We improve previous lower bounds on the number of simple polygonizations, and other kinds of crossing-free subgraphs, of a set of N points in the plane by analyzing a suitable configuration. We also prove that the number of crossing-free perfect matchings and spanning trees is minimum when the points are in convex position.     

On the numerical solution of the quadratic eigenvalue complementarity problem

The Quadratic Eigenvalue Complementarity Problem (QEiCP) is an extension of the Eigenvalue Complementarity Problem (EiCP) that has been introduced recently. Similar to the EiCP, the QEiCP always has a solution under reasonable hypotheses on the matrices included in its definition. This has been established in a previous paper by reducing a QEiCP of dimension n to a special 2n-order EiCP. In this paper we propose an enumerative algorithm for solving the QEiCP by exploiting this equivalence with an EiCP. The algorithm seeks a global minimum of a special Nonlinear Programming Problem (NLP) with a known global optimal value. The algorithm is shown to perform very well in practice but in some cases terminates with only an approximate optimal solution to NLP. Hence, we propose a hybrid method that combines the enumerative method with a fast and local semi-smooth method to overcome the latter drawback. This algorithm is also shown to be useful for computing a positive eigenvalue for an EiCP under similar assumptions. Computational experience is reported to demonstrate the efficacy and efficiency of the hybrid enumerative method for solving the QEiCP.     

The PELskin project-part V: towards the control of the flow around aerofoils at high angle of attack using a self-activated deployable flap

During the flight of birds, it is often possible to notice that some of the primaries and covert feathers on the upper side of the wing pop-up under critical flight conditions, such as the landing approach or when stalking their prey (see Fig. 1) . It is often conjectured that the feathers pop up plays an aerodynamic role by limiting the spread of flow separation . A combined experimental and numerical study was conducted to shed some light on the physical mechanism determining the feathers self actuation and their effective role in controlling the flow field in nominally stalled conditions. In particular, we have considered a NACA0020 aerofoil, equipped with a flexible flap at low chord Reynolds numbers. A parametric study has been conducted on the effects of the length, natural frequency, and position of the flap. A configuration with a single flap hinged on the suction side at 70 % of the chord size c (from the leading edge), with a length of \(L=0.2c\) matching the shedding frequency of vortices at stall condition has been found to be optimum in delivering maximum aerodynamic efficiency and lift gains. Flow evolution both during a ramp-up motion (incidence angle from \(\alpha _0=0\) to \(\alpha _s=20^\circ\) with a reduced frequency of \(k= 0.12\, U_{\infty }/c\), \(U_{\infty }\) being the free stream velocity magnitude), and at a static stalled condition (\(\alpha =20^\circ\)) were analysed with and without the flap. A significant increase of the mean lift after a ramp-up manoeuvre is observed in presence of the flap. Stall dynamics (i.e., lift overshoot and oscillations) are altered and the simulations reveal a periodic re-generation cycle composed of a leading edge vortex that lift the flap during his passage, and an ejection generated by the relaxing of the flap in its equilibrium position. The flap movement in turns avoid the interaction between leading and trailing edge vortices when lift up and push the trailing edge vortex downstream when relaxing back. This cyclic behaviour is clearly shown by the periodic variation of the lift about the average value, and also from the periodic motion of the flap. A comparison with the experiments shows a similar but somewhat higher non-dimensional frequency of the flap oscillation. By assuming that the cycle frequency scales inversely with the boundary layer thickness, one can explain the higher frequencies observed in the experiments which were run at a Reynolds number about one order of magnitude higher than in the simulations. In addition, in experiments the periodic re-generation cycle decays after 3–4 periods ultimately leading to the full stall of the aerofoil. In contrast, the 2D simulations show that the cycle can become self-sustained without any decay when the flap parameters are accurately tuned.     

A new algorithm for computing the Geronimus transformation with large shifts

A monic Jacobi matrix is a tridiagonal matrix which contains the parameters of the three-term recurrence relation satisfied by the sequence of monic polynomials orthogonal with respect to a measure. The basic Geronimus transformation with shift α transforms the monic Jacobi matrix associated with a measure dμ into the monic Jacobi matrix associated with dμ/(x − α) + Cδ(x − α), for some constant C. In this paper we examine the algorithms available to compute this transformation and we propose a more accurate algorithm, estimate its forward errors, and prove that it is forward stable. In particular, we show that for C = 0 the problem is very ill-conditioned, and we present a new algorithm that uses extended precision.