Restless bandits, partial conservation laws and indexability

We show that if performance measures in a stochastic scheduling problem satisfy a set of so-called partial conservation laws (PCL), which extend previously studied generalized conservation laws (GCL), then the problem is solved optimally by a priority-index policy for an appropriate range of linear performance objectives, where the optimal indices are computed by a one-pass adaptive-greedy algorithm, based on Klimov's. We further apply this framework to investigate the indexability property of restless bandits introduced by Whittle, obtaining the following results: (1) we identify a class of restless bandits (PCL-indexable) which are indexable; membership in this class is tested through a single run of the adaptive-greedy algorithm, which also computes the Whittle indices when the test is positive; this provides a tractable sufficient condition for indexability; (2) we further indentify the class of GCL-indexable bandits, which includes classical bandits, having the property that they are indexable under any linear reward objective. The analysis is based on the so-called achievable region method, as the results follow fromnew linear programming formulations for the problems investigated.

On Certain Greedoid Polyhedra, Partially Indexable Scheduling Problems, and Extended Restless Bandit Allocation Indices

We present a polyhedral framework for establishing general structural properties on optimal solutions of stochastic scheduling problems, where multiple job classes vie for service resources: the existence of an optimal priority policy in a given family, characterized by a greedoid (whose feasible class subsets may receive higher priority), where optimal priorities are determined by class-ranking indices, under restricted linear performance objectives (partial indexability). This framework extends that of Bertsimas and Niño-Mora (1996), which explained the optimality of priority-index policies under all linear objectives (general indexability). We show that, if performance measures satisfy partial conservation laws (with respect to the greedoid), which extend previous generalized conservation laws, then the problem admits a strong LP relaxation over a so-called extended greedoid polytope, which has strong structural and algorithmic properties. We present an adaptive-greedy algorithm (which extends Klimov's) taking as input the linear objective coefficients, which (1) determines whether the optimal LP solution is achievable by a policy in the given family; and (2) if so, computes a set of class-ranking indices that characterize optimal priority policies in the family. In the special case of project scheduling, we show that, under additional conditions, the optimal indices can be computed separately for each project (index decomposition). We further apply the framework to the important restless bandit model (two-action Markov decision chains), obtaining new index policies, that extend Whittle's (1988), and simple sufficient conditions for their validity. These results highlight the power of polyhedral methods (the so-called achievable region approach) in dynamic and stochastic optimization.

Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable,nondecreasing and convex on the number of jobs in eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.

On certain greedoid polyhedra, partially indexable scheduling problems and extended restless bandit allocation indices

We present a polyhedral framework for establishing general structural properties on optimal solutions of stochastic scheduling problems, where multiple job classes vie for service resources: the existence of an optimal priority policy in a given family, characterized by a greedoid(whose feasible class subsets may receive higher priority), where optimal priorities are determined by class-ranking indices, under restricted linear performance objectives (partial indexability). This framework extends that of Bertsimas and Niño-Mora (1996), which explained the optimality of priority-index policies under all linear objectives (general indexability). We show that, if performance measures satisfy partial conservation laws (with respect to the greedoid), which extend previous generalized conservation laws, then theproblem admits a strong LP relaxation over a so-called extended greedoid polytope, which has strong structural and algorithmic properties. We present an adaptive-greedy algorithm (which extends Klimov's) taking as input the linear objective coefficients, which (1) determines whether the optimal LP solution is achievable by a policy in the given family; and (2) if so, computes a set of class-ranking indices that characterize optimal priority policies in the family. In the special case of project scheduling, we show that, under additional conditions, the optimal indices can be computed separately for each project (index decomposition). We further apply the framework to the important restless bandit model (two-action Markov decision chains), obtaining new index policies, that extend Whittle's (1988), and simple sufficient conditions for their validity. These results highlight the power of polyhedral methods (the so-called achievable region approach) in dynamic and stochastic optimization.

Nonideal particle distributions from kinetic freeze-out models

In fluid dynamical models the freeze-out of particles across a three-dimensional space-time hypersurface is discussed. The calculation of final momentum distribution of emitted particles is described for freeze-out surfaces, with both spacelike and timelike normals, taking into account conservation laws across the freeze-out discontinuity.

Freeze-out in hydrodynamical models

We study the effects of strict conservation laws and the problem of negative contributions to final momentum distribution during the freeze-out through 3-dimensional hypersurfaces with spacelike normal. We study some suggested solutions for this problem, and demonstrate it in one example.

Many worlds in one

A generic prediction of inflation is that the thermalized region we inhabit is spatially infinite. Thus, it contains an infinite number of regions of the same size as our observable universe, which we shall denote as O regions. We argue that the number of possible histories which may take place inside of an O region, from the time of recombination up to the present time, is finite. Hence, there are an infinite number of O regions with identical histories up to the present, but which need not be identical in the future. Moreover, all histories which are not forbidden by conservation laws will occur in a finite fraction of all O regions. The ensemble of O regions is reminiscent of the ensemble of universes in the many-world picture of quantum mechanics. An important difference, however, is that other O regions are unquestionably real.

Mecánica clásica en el espacio de Hilbert

We continue our study of classical mechanics using the methods of quantum mechanics. A Hilbert space is introduced, new conservation laws deduced, and the possibility of representing by new methods the many body classical problem discussed.

Discretized integral hydrodynamics

Using an interpolant form for the gradient of a function of position, we write an integral version of the conservation equations for a fluid. In the appropriate limit, these become the usual conservation laws of mass, momentum, and energy. We also discuss the special cases of the Navier-Stokes equations for viscous flow and the Fourier law for thermal conduction in the presence of hydrodynamic fluctuations. By means of a discretization procedure, we show how the integral equations can give rise to the so-called particle dynamics of smoothed particle hydrodynamics and dissipative particle dynamics.

A broadband leptonic model for gamma-ray emitting microquasars

Observational and theoretical studies point to microquasars (MQs) as possible counterparts of a significant fraction of the unidentified gamma-ray sources detected so far. At present, a proper scenario to explain the emission beyond soft X-rays from these objects is not known, nor what the precise connection is between the radio and the high-energy radiation. We develop a new model where the MQ jet is dynamically dominated by cold protons and radiatively dominated by relativistic leptons. The matter content and power of the jet are both related with the accretion process. The magnetic field is assumed to be close to equipartition, although it is attached to and dominated by the jet matter. For the relativistic particles in the jet, their maximum energy depends on both the acceleration efficiency and the energy losses. The model takes into account the interaction of the relativistic jet particles with the magnetic field and all the photon and matter fields. Such interaction produces significant amounts of radiation from radio to very high energies through synchrotron, relativistic Bremsstrahlung, and inverse Compton (IC) processes. Variability of the emission produced by changes in the accretion process (e.g. via orbital eccentricity) is also expected. The effects of the gamma-ray absorption by the external photon fields on the gamma-ray spectrum have been taken into account, revealing clear spectral features that might be observed. This model is consistent to the accretion scenario, energy conservation laws, and current observational knowledge, and can provide deeper physical information of the source when tested against multiwavelength data.

Ullals de Baltasar -Delta de l'Ebre: proposta de pla de gestió i ús social

Les zones humides han sofert durant anys les velles concepcions de gestió de l'aigua, promovent la seva dessecació fins els anys 60. Com a resposta han sorgit un seguit de directives europees i lleis estatals i autonòmiques per intentar recuperar i restaurar aquests hàbitats amenaçats.

Testing low-altitude infrared digital photography from a mini-UAV to retrieve information for biological conservation

Satellite remote sensing imagery is used for forestry, conservation and environmental applications, but insufficient spatial resolution, and, in particular, unavailability of images at the precise timing required for a given application, often prevent achieving a fully operational stage. Airborne remote sensing has the advantage of custom-tuned sensors, resolution and timing, but its price prevents using it as a routine technique for the mentioned fields. Some Unmanned Aerial Vehicles might provide a “third way” solution as low-cost techniques for acquiring remotely sensed information, under close control of the end-user, albeit at the expense of lower quality instrumentation and instability. This report evaluates a light remote sensing system based on a remotely-controlled mini-UAV (ATMOS-3) equipped with a color infra-red camera (VEGCAM-1) designed and operated by CATUAV. We conducted a testing mission over a Mediterranean landscape dominated by an evergreen woodland of Aleppo pine (Pinus halepensis) and (Holm) oak (Quercus ilex) in the Montseny National Park (Catalonia, NE Spain). We took advantage of state-of-the-art ortho-rectified digital aerial imagery (acquired by the Institut Cartogràfic de Catalunya over the area during the previous year) and used it as quality reference. In particular, we paid attention to: 1) Operationality of flight and image acquisition according to a previously defined plan; 2) Radiometric and geometric quality of the images; and 3) Operational use of the images in the context of applications. We conclude that the system has achieved an operational stage regarding flight activities, although with meteorological limits set by wind speed and turbulence. Appropriate landing areas can be sometimes limiting also, but the system is able to land on small and relatively rough terrains such as patches of grassland or short matorral, and we have operated the UAV as far as 7 km from the control unit. Radiometric quality is sufficient for interactive analysis, but probably insufficient for automated processing. A forthcoming camera is supposed to greatly improve radiometric quality and consistency. Conventional GPS positioning through time synchronization provides coarse orientation of the images, with no roll information.

Regularity and mass conservation for discrete coagulation-fragmentation equations with diffusion

We present a new a-priori estimate for discrete coagulation fragmentation systems with size-dependent diffusion within a bounded, regular domain confined by homogeneous Neumann boundary conditions. Following from a duality argument, this a-priori estimate provides a global L2 bound on the mass density and was previously used, for instance, in the context of reaction-diffusion equations. In this paper we demonstrate two lines of applications for such an estimate: On the one hand, it enables to simplify parts of the known existence theory and allows to show existence of solutions for generalised models involving collision-induced, quadratic fragmentation terms for which the previous existence theory seems difficult to apply. On the other hand and most prominently, it proves mass conservation (and thus the absence of gelation) for almost all the coagulation coefficients for which mass conservation is known to hold true in the space homogeneous case.

Technological innovation in creative clusters. The case of laser in conservation of artworks in Florence

The field of laser application to the restoration and cleaning of cultural assets is amongst the most thriving developments of recent times. Ablative laser technological systems are able to clean and protect inestimable works of art subject to atmospheric agents and degradation over time. This new technology, which has been developing for the last forty year, is now available to restorers and has received a significant success all over Europe. An important contribution in the process of laser innovation has been carried out in Florence by local actors belonging to a creative cluster. The objects of the analysis are the genesis of this innovation in this local Florentine context, and the relationships among the main actors who have contributed in it. The study investigates how culture can play a part in the generation of ideas and innovations, and which are the creative environments that can favour it. In this context, the issue of laser technologies for the restoration of cultural heritage has been analysed as a case study in the various paths taken by the Creative Capacity of the Culture (CCC).

Power laws and scaling of rain events and dry spells in the Catalonia region

We analyze the statistics of rain-event sizes, rain-event durations, and dry-spell durations in a network of 20 rain gauges scattered in an area situated close to the NW Mediterranean coast. Power-law distributions emerge clearly for the dryspell durations, with an exponent around 1.50 ± 0.05, although for event sizes and durations the power-law ranges are rather limited, in some cases. Deviations from power-law behavior are attributed to finite-size effects. A scaling analysis helps to elucidate the situation, providing support for the existence of scale invariance in these distributions. It is remarkable that rain data of not very high resolution yield findings in agreement with self-organized critical phenomena.