Restless bandits, linear programming relaxations and a primal-dual index heuristic

We develop a mathematical programming approach for the classicalPSPACE - hard restless bandit problem in stochastic optimization.We introduce a hierarchy of n (where n is the number of bandits)increasingly stronger linear programming relaxations, the lastof which is exact and corresponds to the (exponential size)formulation of the problem as a Markov decision chain, while theother relaxations provide bounds and are efficiently computed. Wealso propose a priority-index heuristic scheduling policy fromthe solution to the first-order relaxation, where the indices aredefined in terms of optimal dual variables. In this way wepropose a policy and a suboptimality guarantee. We report resultsof computational experiments that suggest that the proposedheuristic policy is nearly optimal. Moreover, the second-orderrelaxation is found to provide strong bounds on the optimalvalue.

Jatkuvavaletun teräksen leikkaussuunnitelman optimointi

Teollisuuden tuotannon eri prosessien optimointi on hyvin ajankohtainen aihe. Monet ohjausjärjestelmät ovat ajalta, jolloin tietokoneiden laskentateho oli hyvin vaatimaton nykyisiin verrattuna. Työssä esitetään tuotantoprosessi, joka sisältää teräksen leikkaussuunnitelman muodostamisongelman. Valuprosessi on yksi teräksen valmistuksen välivaiheita. Siinä sopivaan laatuun saatettu sula teräs valetaan linjastoon, jossa se jähmettyy ja leikataan aihioiksi. Myöhemmissä vaiheissa teräsaihioista muokataan pienempiä kokonaisuuksia, tehtaan lopputuotteita. Jatkuvavaletut aihiot voidaan leikata tilauskannasta riippuen monella eri tavalla. Tätä varten tarvitaan leikkaussuunnitelma, jonka muodostamiseksi on ratkaistava sekalukuoptimointiongelma. Sekalukuoptimointiongelmat ovat optimoinnin haastavin muoto. Niitä on tutkittu yksinkertaisempiin optimointiongelmiin nähden vähän. Nykyisten tietokoneiden laskentateho on kuitenkin mahdollistanut raskaampien ja monimutkaisempien optimointialgoritmien käytön ja kehittämisen. Työssä on käytetty ja esitetty eräs stokastisen optimoinnin menetelmä, differentiaalievoluutioalgoritmi. Tässä työssä esitetään teräksen leikkausoptimointialgoritmi. Kehitetty optimointimenetelmä toimii dynaamisesti tehdasympäristössä käyttäjien määrittelemien parametrien mukaisesti. Työ on osa Syncron Tech Oy:n Ovako Bar Oy Ab:lle toimittamaa ohjausjärjestelmää.

Optimisation des horaires des agents et du routage des appels dans les centres d’appels

Nous étudions la gestion de centres d'appels multi-compétences, ayant plusieurs types d'appels et groupes d'agents. Un centre d'appels est un système de files d'attente très complexe, où il faut généralement utiliser un simulateur pour évaluer ses performances. Tout d'abord, nous développons un simulateur de centres d'appels basé sur la simulation d'une chaîne de Markov en temps continu (CMTC), qui est plus rapide que la simulation conventionnelle par événements discrets. À l'aide d'une méthode d'uniformisation de la CMTC, le simulateur simule la chaîne de Markov en temps discret imbriquée de la CMTC. Nous proposons des stratégies pour utiliser efficacement ce simulateur dans l'optimisation de l'affectation des agents. En particulier, nous étudions l'utilisation des variables aléatoires communes. Deuxièmement, nous optimisons les horaires des agents sur plusieurs périodes en proposant un algorithme basé sur des coupes de sous-gradients et la simulation. Ce problème est généralement trop grand pour être optimisé par la programmation en nombres entiers. Alors, nous relaxons l'intégralité des variables et nous proposons des méthodes pour arrondir les solutions. Nous présentons une recherche locale pour améliorer la solution finale. Ensuite, nous étudions l'optimisation du routage des appels aux agents. Nous proposons une nouvelle politique de routage basé sur des poids, les temps d'attente des appels, et les temps d'inoccupation des agents ou le nombre d'agents libres. Nous développons un algorithme génétique modifié pour optimiser les paramètres de routage. Au lieu d'effectuer des mutations ou des croisements, cet algorithme optimise les paramètres des lois de probabilité qui génèrent la population de solutions. Par la suite, nous développons un algorithme d'affectation des agents basé sur l'agrégation, la théorie des files d'attente et la probabilité de délai. Cet algorithme heuristique est rapide, car il n'emploie pas la simulation. La contrainte sur le niveau de service est convertie en une contrainte sur la probabilité de délai. Par après, nous proposons une variante d'un modèle de CMTC basé sur le temps d'attente du client à la tête de la file. Et finalement, nous présentons une extension d'un algorithme de coupe pour l'optimisation stochastique avec recours de l'affectation des agents dans un centre d'appels multi-compétences.

Sensitivity of complex networks measurements

Complex networks obtained from real-world networks are often characterized by incompleteness and noise, consequences of imperfect sampling as well as artifacts in the acquisition process. Because the characterization, analysis and modeling of complex systems underlain by complex networks are critically affected by the quality and completeness of the respective initial structures, it becomes imperative to devise methodologies for identifying and quantifying the effects of the sampling on the network structure. One way to evaluate these effects is through an analysis of the sensitivity of complex network measurements to perturbations in the topology of the network. In this paper, measurement sensibility is quantified in terms of the relative entropy of the respective distributions. Three particularly important kinds of progressive perturbations to the network are considered, namely, edge suppression, addition and rewiring. The measurements allowing the best balance of stability (smaller sensitivity to perturbations) and discriminability (separation between different network topologies) are identified with respect to each type of perturbation. Such an analysis includes eight different measurements applied on six different complex networks models and three real-world networks. This approach allows one to choose the appropriate measurements in order to obtain accurate results for networks where sampling bias cannot be avoided-a very frequent situation in research on complex networks.

Packing a trunk : a physically based approach with full motional freedom

Geometric packing problems may be formulated mathematically as constrained optimization problems. But finding a good solution is a challenging task. The more complicated the geometry of the container or the objects to be packed, the more complex the non-penetration constraints become. In this work we propose the use of a physics engine that simulates a system of colliding rigid bodies. It is a tool to resolve interpenetration conflicts and to optimize configurations locally. We develop an efficient and easy-to-implement physics engine that is specialized for collision detection and contact handling. In succession of the development of this engine a number of novel algorithms for distance calculation and intersection volume were designed and imple- mented, which are presented in this work. They are highly specialized to pro- vide fast responses for cuboids and triangles as input geometry whereas the concepts they are based on can easily be extended to other convex shapes. Especially noteworthy in this context is our ε-distance algorithm - a novel application that is not only very robust and fast but also compact in its im- plementation. Several state-of-the-art third party implementations are being presented and we show that our implementations beat them in runtime and robustness. The packing algorithm that lies on top of the physics engine is a Monte Carlo based approach implemented for packing cuboids into a container described by a triangle soup. We give an implementation for the SAE J1100 variant of the trunk packing problem. We compare this implementation to several established approaches and we show that it gives better results in faster time than these existing implementations.

Modelling Pinus pinea forest management to attain natural regeneration under present and future climatic scenarios

Natural regeneration-based silviculture has been increasingly regarded as a reliable option in sustainable forest management. However, successful natural regeneration is not always easy to achieve. Recently, new concerns have arisen because of changing future climate. To date, regeneration models have proved helpful in decision-making concerning natural regeneration. The implementation of such models into optimization routines is a promising approach in providing forest managers with accurate tools for forest planning. In the present study, we present a stochastic multistage regeneration model for Pinus pinea L. managed woodlands in Central Spain, where regeneration has been historically unsuccessful. The model is able to quantify recruitment under different silviculture alternatives and varying climatic scenarios, with further application to optimize management scheduling. The regeneration process in the species showed high between-year variation, with all subprocesses (seed production, dispersal, germination, predation, and seedling survival) having the potential to become bottlenecks. However, model simulations demonstrate that current intensive management is responsible for regeneration failure in the long term. Specifically, stand densities at rotation age are too low to guarantee adequate dispersal, the optimal density of seed-producing trees being around 150 stems·ha−1. In addition, rotation length needs to be extended up to 120 years to benefit from the higher seed production of older trees. Stochastic optimization confirms these results. Regeneration does not appear to worsen under climate change conditions; the species exhibiting resilience worthy of broader consideration in Mediterranean silviculture.

Fully adaptive gaussian mixture metropolis-hastings algorithm

Markov Chain Monte Carlo methods are widely used in signal processing and communications for statistical inference and stochastic optimization. In this work, we introduce an efficient adaptive Metropolis-Hastings algorithm to draw samples from generic multimodal and multidimensional target distributions. The proposal density is a mixture of Gaussian densities with all parameters (weights, mean vectors and covariance matrices) updated using all the previously generated samples applying simple recursive rules. Numerical results for the one and two-dimensional cases are provided.

An adaptive population importance sampler

Monte Carlo (MC) methods are widely used in signal processing, machine learning and communications for statistical inference and stochastic optimization. A well-known class of MC methods is composed of importance sampling and its adaptive extensions (e.g., population Monte Carlo). In this work, we introduce an adaptive importance sampler using a population of proposal densities. The novel algorithm provides a global estimation of the variables of interest iteratively, using all the samples generated. The cloud of proposals is adapted by learning from a subset of previously generated samples, in such a way that local features of the target density can be better taken into account compared to single global adaptation procedures. Numerical results show the advantages of the proposed sampling scheme in terms of mean absolute error and robustness to initialization.

Orthogonal MCMC algorithms

Monte Carlo (MC) methods are widely used in signal processing, machine learning and stochastic optimization. A well-known class of MC methods are Markov Chain Monte Carlo (MCMC) algorithms. In this work, we introduce a novel parallel interacting MCMC scheme, where the parallel chains share information using another MCMC technique working on the entire population of current states. These parallel ?vertical? chains are led by random-walk proposals, whereas the ?horizontal? MCMC uses a independent proposal, which can be easily adapted by making use of all the generated samples. Numerical results show the advantages of the proposed sampling scheme in terms of mean absolute error, as well as robustness w.r.t. to initial values and parameter choice.

Cross-validated maximum likelihood enhances crystallographic simulated annealing refinement

Recently, the target function for crystallographic refinement has been improved through a maximum likelihood analysis, which makes proper allowance for the effects of data quality, model errors, and incompleteness. The maximum likelihood target reduces the significance of false local minima during the refinement process, but it does not completely eliminate them, necessitating the use of stochastic optimization methods such as simulated annealing for poor initial models. It is shown that the combination of maximum likelihood with cross-validation, which reduces overfitting, and simulated annealing by torsion angle molecular dynamics, which simplifies the conformational search problem, results in a major improvement of the radius of convergence of refinement and the accuracy of the refined structure. Torsion angle molecular dynamics and the maximum likelihood target function interact synergistically, the combination of both methods being significantly more powerful than each method individually. This is demonstrated in realistic test cases at two typical minimum Bragg spacings (dmin = 2.0 and 2.8 Å, respectively), illustrating the broad applicability of the combined method. In an application to the refinement of a new crystal structure, the combined method automatically corrected a mistraced loop in a poor initial model, moving the backbone by 4 Å.

Estratégias de comercialização e investimento, com ênfase em energias renováveis, suportadas por modelos de otimização especializados para avaliação estocástica de risco x retorno.

A comercialização de energia elétrica de fontes renováveis, ordinariamente, constitui-se uma atividade em que as operações são estruturadas sob condições de incerteza, por exemplo, em relação ao preço \"spot\" no mercado de curto prazo e a geração de energia dos empreendimentos. Deriva desse fato a busca dos agentes pela formulação de estratégias e utilização de ferramentais para auxiliá-los em suas tomadas de decisão, visando não somente o retorno financeiro, mas também à mitigação dos riscos envolvidos. Análises de investimentos em fontes renováveis compartilham de desafios similares. Na literatura, o estudo da tomada de decisão considerada ótima sob condições de incerteza se dá por meio da aplicação de técnicas de programação estocástica, que viabiliza a modelagem de problemas com variáveis randômicas e a obtenção de soluções racionais, de interesse para o investidor. Esses modelos permitem a incorporação de métricas de risco, como por exemplo, o Conditional Value-at-Risk, a fim de se obter soluções ótimas que ponderem a expectativa de resultado financeiro e o risco associado da operação, onde a aversão ao risco do agente torna-se um condicionante fundamental. O objetivo principal da Tese - sob a ótica dos agentes geradores, consumidores e comercializadores - é: (i) desenvolver e implementar modelos de otimização em programação linear estocástica com métrica CVaR associada, customizados para cada um desses agentes; e (ii) aplicá-los na análise estratégica de operações como forma de apresentar alternativas factíveis à gestão das atividades desses agentes e contribuir com a proposição de um instrumento conceitualmente robusto e amigável ao usuário, para utilização por parte das empresas. Nesse contexto, como antes frisado, dá-se ênfase na análise do risco financeiro dessas operações por meio da aplicação do CVaR e com base na aversão ao risco do agente. Considera-se as fontes renováveis hídrica e eólica como opções de ativos de geração, de forma a estudar o efeito de complementaridade entre fontes distintas e entre sites distintos da mesma fonte, avaliando-se os rebatimentos nas operações.

Application of the cross-entropy method to the buffer allocation problem in a simulation-based environment

The buffer allocation problem (BAP) is a well-known difficult problem in the design of production lines. We present a stochastic algorithm for solving the BAP, based on the cross-entropy method, a new paradigm for stochastic optimization. The algorithm involves the following iterative steps: (a) the generation of buffer allocations according to a certain random mechanism, followed by (b) the modification of this mechanism on the basis of cross-entropy minimization. Through various numerical experiments we demonstrate the efficiency of the proposed algorithm and show that the method can quickly generate (near-)optimal buffer allocations for fairly large production lines.

A New Algorithm for Monte Carlo for American Options

2000 Mathematics Subject Classification: 91B28, 65C05.

Learning from Geometry

Subspaces and manifolds are two powerful models for high dimensional signals. Subspaces model linear correlation and are a good fit to signals generated by physical systems, such as frontal images of human faces and multiple sources impinging at an antenna array. Manifolds model sources that are not linearly correlated, but where signals are determined by a small number of parameters. Examples are images of human faces under different poses or expressions, and handwritten digits with varying styles. However, there will always be some degree of model mismatch between the subspace or manifold model and the true statistics of the source. This dissertation exploits subspace and manifold models as prior information in various signal processing and machine learning tasks.

A near-low-rank Gaussian mixture model measures proximity to a union of linear or affine subspaces. This simple model can effectively capture the signal distribution when each class is near a subspace. This dissertation studies how the pairwise geometry between these subspaces affects classification performance. When model mismatch is vanishingly small, the probability of misclassification is determined by the product of the sines of the principal angles between subspaces. When the model mismatch is more significant, the probability of misclassification is determined by the sum of the squares of the sines of the principal angles. Reliability of classification is derived in terms of the distribution of signal energy across principal vectors. Larger principal angles lead to smaller classification error, motivating a linear transform that optimizes principal angles. This linear transformation, termed TRAIT, also preserves some specific features in each class, being complementary to a recently developed Low Rank Transform (LRT). Moreover, when the model mismatch is more significant, TRAIT shows superior performance compared to LRT.

The manifold model enforces a constraint on the freedom of data variation. Learning features that are robust to data variation is very important, especially when the size of the training set is small. A learning machine with large numbers of parameters, e.g., deep neural network, can well describe a very complicated data distribution. However, it is also more likely to be sensitive to small perturbations of the data, and to suffer from suffer from degraded performance when generalizing to unseen (test) data.

From the perspective of complexity of function classes, such a learning machine has a huge capacity (complexity), which tends to overfit. The manifold model provides us with a way of regularizing the learning machine, so as to reduce the generalization error, therefore mitigate overfiting. Two different overfiting-preventing approaches are proposed, one from the perspective of data variation, the other from capacity/complexity control. In the first approach, the learning machine is encouraged to make decisions that vary smoothly for data points in local neighborhoods on the manifold. In the second approach, a graph adjacency matrix is derived for the manifold, and the learned features are encouraged to be aligned with the principal components of this adjacency matrix. Experimental results on benchmark datasets are demonstrated, showing an obvious advantage of the proposed approaches when the training set is small.

Stochastic optimization makes it possible to track a slowly varying subspace underlying streaming data. By approximating local neighborhoods using affine subspaces, a slowly varying manifold can be efficiently tracked as well, even with corrupted and noisy data. The more the local neighborhoods, the better the approximation, but the higher the computational complexity. A multiscale approximation scheme is proposed, where the local approximating subspaces are organized in a tree structure. Splitting and merging of the tree nodes then allows efficient control of the number of neighbourhoods. Deviation (of each datum) from the learned model is estimated, yielding a series of statistics for anomaly detection. This framework extends the classical {\em changepoint detection} technique, which only works for one dimensional signals. Simulations and experiments highlight the robustness and efficacy of the proposed approach in detecting an abrupt change in an otherwise slowly varying low-dimensional manifold.

Metodologia de otimização estocástica para coordenação eólico-fotovoltaica

Esta dissertação incide sobre o tema da coordenação entre sistemas eólicos e fotovoltaicos que participam no mercado de eletricidade. A incerteza da potência eólica e fotovoltaica é uma caraterística predominante nesta coordenação, devendo ser considerada no planeamento ótimo de sistemas eólico-fotovoltaicos. A fim de modelizar a incerteza é apresentada uma metodologia de otimização estocástica baseada em programação linear para maximizar o lucro esperado de uma empresa produtora de energia elétrica que participa no mercado diário. A coordenação entre sistemas eólicos e fotovoltaicos visa mitigar os desequilíbrios de energia, resultantes das ofertas horárias submetidas no mercado diário e, consequentemente, reduzir as penalizações financeiras. Os resultados da coordenação entre um sistema eólico e um sistema fotovoltaico são comparados com os resultados obtidos para a operação não coordenada. Estes resultados permitem concluir que a metodologia desenvolvida aplicada à coordenação apresenta um lucro esperado superior ao lucro obtido para a operação não coordenada; Abstract Stochastic Optimization Methodology for Wind-Photovoltaic Coordination This dissertation focuses on the issue of coordination between wind and photovoltaic systems participating in electricity markets. The uncertainty of wind and photovoltaic power is a main characteristic of these systems, which must be included in the optimal scheduling of the coordination of wind with photovoltaic systems. In order to model the uncertainty is presented a stochastic approach based on linear programming to maximize the profit of a wind photovoltaic power producer which participates in electricity markets. The coordination of wind with photovoltaic systems aims to mitigate the energy deviations, as a result of the participation in day-ahead market and therefore reducing economic penalties. The results obtained by the coordination are compared to results obtained by the separated operation of wind and photovoltaic systems. The results allow concluding that the proposed approach applied to the coordination presents an expected profit higher than the expected profit without coordination.