In the rapidly changing world of today, people have to make decisions under some degree of uncertainty. At the same time, the development of computing technologies enables people to take uncertain factors into considerations while making their decisions.Stochastic programming techniques have been widely applied in finance engineering, supply chain management, logistics, transportation, etc. Such applications often involve a large, possibly infinite, set of scenarios. Hence the resulting programstend to be large in scale.The need to solve large scale programs calls for a combination of mathematical programming techniques and sample-based approximation. When using sample-based approximations, it is important to determine the extent to which the resulting solutions are dependent on thespecific sample used. This dissertation research focuses on computational evaluation of the solutions from sample-based two-stage/multistage stochastic linear programming algorithms, with a focus on the effectiveness of optimality tests and the quality ofa proposed solution.In the first part of this dissertation, two alternative approaches of optimality tests of sample-based solutions, adaptive and non-adaptive sampling methods, are examined and computationally compared. The results of the computational experiment are in favor of the adaptive methods. In the second part of this dissertation, statistically motivated bound-based solution validation techniques in multistage linear stochastic programs are studied both theoretically and computationally. Different approaches of representations of the nonanticipativity constraints are studied. Bounds are established through manipulations of the nonanticipativity constraints.

No description available.

An installment option is a European option in which the premium, instead of being paid up-front, is paid in a series of installments. If all installments are paid the holder receives the exercise value, but the holder has the right to terminate payments on any payment date, in which case the option lapses with no further payments on either side. We discuss pricing and risk management for these options, in particular the use of static hedges, and also study a continuous-time limit in which premium is paid at a certain rate per unit time. (author's abstract) / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

Στη παρούσα εργασία ασχοληθήκαμε με ιδιότητες μονοτονίας των Τροποποιημένων συναρτήσεων Bessel 1ου και 2ου είδους. Συγκεκριμένα ομαδοποιήσαμε ήδη υπάρχοντα φράγματα για τα κλάσματα των συναρτήσεων αυτών. Η εύρεση φραγμάτων για τα κλάσματα των Τροποποιημένων Συναρτήσεων Bessel είναι σημαντική, λόγω της χρησιμότητάς τους σε διάφορους κλάδους των Μαθηματικών και όχι μόνο, όπως ενδεικτικά, στην Πεπερασμένη Ελαστικότητα, στην Στατιστική και στις Πιθανότητες, στην Ειδική Θεωρία Σχετικότητας, στην Μηχανική των Ρευστών, στην Ηλεκτρομηχανική, στη Βιοφυσική, στη Μαθηματική Φυσική και αλλού. Αρχικά, στο Κεφάλαιο 1, παρατέθηκαν κάποια βασικά στοιχεία, όπως ορισμοί των συναρτήσεων Bessel 1ου και 2ου είδους (Τροποποιημένων και μη) και αναδρομικές σχέσεις που ικανοποιούν. Στο Κεφάλαιο 2, γίνεται η καταγραφή και σύγκριση άνω και κάτω φραγμάτων για τα διάφορα κλάσματα των Τροποποιημένων συναρτήσεων Bessel 1ου είδους, καθώς και αναφορά σε ανισότητες τύπου Turán για τις συναρτήσεις αυτές. Επίσης, αναφέρεται η μεθοδολογία στην οποία στηρίχθηκε ο κάθε ερευνητής για να πάρει τα αντίστοιχα αποτελέσματα. Στο Κεφάλαιο 3, γίνεται η αντίστοιχη διαδικασία για τα κλάσματα και εκ νέου αναφορά σε ανισότητες τύπου Turán για αυτές τις συναρτήσεις. / In this project we described properties of Modified Bessel functions of the 1st and 2nd kind. Specifically we have grouped existing bounds for the quotients of these functions. These bounds of the Modified Bessel functions is very importand and could be found in different branches of Mathematics and other sciences, such as in Finite Elasticity, in Statistics and Probability Theory, in Relativity Theory, in Fluid Mechanics, in Engineering, in Biophysics, in Mathematical Physics and so on. Firsty, in Chapter 1, we cited some basic data, such as definitions of definitions of Bessel fynctions of the 1st and 2nd kind (both simple and Modified) and recurrence relations that they satisfy. In Chapter 2, we describe upper and lower bounds of different quotients of Modified Bessel functions of the 1st kind and reference to Turán type Inequalities of those functions. Moreover, we refer to the method that each recearcher based on in order to prove the required results. In Chapter 3, we have the same process but for Modified Bessel functons of the 2nd kind as well as reference to Turán type Inequalities for the corresponding functions.

De nos jours, le problème de transport de marchandise occupe une place importante dans la vie économique des sociétés modernes. Le problème de ramassage et de livraison (pick-up and delivery problem) est l’un des problèmes dont une grande partie des chercheurs s’y est intéressée.Il s’agit de déterminer un circuit de plusieurs véhicules, de façon à servir à coût minimal un ensemble de clients et de fournisseurs répartis dans un réseau, satisfaisant certaines contraintes relatives aux véhicules, à leurs capacités et à des précédences entre les nœuds. Les travaux de recherche développés dans cette thèse portent sur le PDPTW (Pickup and Delivery Problem with Time Windows) à plusieurs véhicules (m-PDPTW). Ce dernier a été traité dans les deux cas : statique et dynamique. Nous avons proposé plusieurs approches de résolution du m-PDPTW basées sur les algorithmes génétiques, l’optimisation multicritère et le calcul des bornes inférieures, et ceci pour minimiser un certain nombre de critères comme : le nombre de véhicules utilisés, la somme des retards ou le coût total de transport. Ces approches ont donné de bons résultats, principalement au niveau de la minimisation de la somme des retards où nous avons obtenu, dans plusieurs cas, un retard nul avec un coût de transport tolérable / Nowadays, the transport goods problem occupies an important place in the economic life of modern societies. The PDPTW (Pickup and delivery problem with Time Windows) is one which a large part of researchers was interested. This is an optimization vehicles routing problem which must meet requests for transport between suppliers and customers satisfying precedence and capacity.Researchers developed in this thesis concerns the resolution of the PDPTW with multiple vehicles (m-PDPTW). The latter was treated in two cases: static and dynamic.We have proposed some approaches to solving the m- PDPTW, based on genetic algorithms, multicriteria optimization and the lower bounds, and this to minimize a number of criteria such as: the vehicles number, the total travel cost, and the total tardiness time.Computational results indicate that the proposed approach gives good results with a total tardiness equal to zero with a tolerable cost

Orientador: Silvio Alexandrede Araujo / Banca: Bernardo Sobrinho Simões de Almada Lobo / Banca: Franklina Maria Bragion Toledo / Resumo: O problema de dimensionamento de lotes é um problema de otimização da produção, em que o objetivo é planejar a quantidade de itens a ser produzida em várias, ou única, máquinas em cada período ao longo do horizonte de tempo, de modo a tender uma demanda e otimizar uma função objetivo. Este trabalho aborda o problema de dimensionamento de lotes em um único estágio em um ambiente com máquinas paralelas distintas. Cada item pode ser produzido em qualquer máquina, acarretando um tempo de preparação que é gasto antes de começar a produção. O objetivo do trabalho consiste em obter limitantes inferiores de boa qualidade para este problema. Para tanto, é desenvolvido um método de solução baseado numa reformulação do problema a e na relaxação lagrangiana de um conjunto de restrições. Alguns resultados computacionais são apresentados algumas propostas futuras para a continuidade do trabalho. / Abstract: The lot-sizing problem is a production optimization problem, where the objective is to plan the quantity of items to be produced in multiple, or single, machines in each period over a time horizon, in order to satisfy a demand and optimize an objective function. This work addresses the single stage parallel machine lot-sizing problem. Each item can be produced on any machine, and incur a setup time before to start the production. The objective of this work is to lower bounds of good quality for this problem. A solution method is developed based on a reformulation of the problem and the Lagrangian relaxation of a set of constrainsts. Some computational results are presented comparing the proposed method with a method from the literature, and, some future researches are proposed. / Mestre

Title: Complexity Theory in Feasible Mathematics Author: Ján Pich Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc., MAE Abstract: We study the provability of statements and conjectures from Complex- ity Theory in Bounded Arithmetic. First, modulo a hardness assumption, we show that theories weaker in terms of provably total functions than Buss's theory S1 2 cannot prove nk -size circuit lower bounds for SAT formalized as a Σb 2-formula LB(SAT, nk ). In particular, the true universal first-order theory in the language containing names for all uniform NC1 algorithms denoted TNC1 does not prove LB(SAT, n4kc ) where k ≥ 1, c ≥ 2 unless each function f ∈ SIZE(nk ) can be approximated by formulas Fn of subexponential size 2O(n1/c) with subexponential advantage: Px∈{0,1}n [Fn(x) = f(x)] ≥ 1/2 + 1/2O(n1/c) . Unconditionally, V 0 does not prove quasipolynomial nlog n -size circuit lower bounds for SAT. Considering upper bounds, we prove the PCP theorem in Cook's theory PV1. This includes a formalization of the (n, d, λ)-graphs in PV1. A consequence of the result is that Extended Frege proof system admits p-size proofs of tautologies encoding the PCP theorem. Keywords: Circuit Lower Bounds, Bounded Arithmetic, The PCP theorem

Les travaux de cette thèse réalisée sous contrat CIFRE portent sur des problématiques d’ordonnancement de projets mufti-compétences. Définis en collaboration avec des experts de gestion de projet au sein de la société Néréide, deux modèles d’ordonnancement de projet font l’objet de cette étude. Dans le premier modèle, une tâche est définie par l’ensemble des compétences dont elle a besoin, la charge nécessaire de chaque compétence ainsi que la possibilité d’être interrompue ou non. Pour l’élaboration d’un planning prédictif respectant toutes les contraintes et minimisant la date de fin du projet, nous proposons des heuristiques de liste et métaheuristiques. Un modèle mathématique linéaire en nombres entiers ainsi que des bornes inférieures sont également développés. Dans un second temps, nous proposons, à partir d’un planning prédéfini, des méthodes pour ajuster le planning et répondre aux aléas survenus lors du déroulement du projet. Pour résoudre ce problème réactif, nous proposons une approche exacte itérative basée sur une formulation linéaire en nombres entiers ainsi qu’un algorithme génétique de type NSGA-II. Il s’agit donc d’une approche réactive bicritère où les solutions calculées doivent minimiser à la fois la date d’achèvement du projet et le nombre maximum de changements d’affectation de tâches aux employés. Dans le deuxième modèle, un cas particulier du modèle préemptif précédent est étudié. Nous nous intéressons au cas où une tâche nécessite une seule compétence avec possibilité de préemption seulement si les ressources ne sont pas disponibles (absence, congés, etc.). Dans ce modèle, une tâche est définie également par sa date de disponibilité et une date de fin souhaitée. Un coût d’utilisation personne/compétence est introduit. Pour ce dernier modèle, il s’agit d’un problème d’ordonnancement de projet bicritère, pour lequel les solutions calculées doivent minimiser le retard maximum et le coût global d’affectation des personnes aux tâches. Des heuristiques et métaheuristiques sont proposées pour ce modèle. Certaines méthodes de résolution proposées ont été implémentées sous forme d’add-ons intégrables au framework OFBiz. / The work presented in this thesis deals with multi-skill project scheduling problems. We have studied two models of project scheduling which are defined in collaboration with project management experts in Néréide company. In the first model, a task is defined by a set of required skills, the load needed for each skill as welI as the possibility of preemption. To build a predictive planning which respects aIl problem constraints and minimize the project completion time (makespan), we propose heuristics and meta-heuristics methods. A mixed integer mathematical linear programming model and lower bounds are also proposed. From a predefined planning, we propose an exact method based on a mathematical program as weIl as a genetic algorithm of type NSGA-II allowing to deal with disruptions occurred during the project realization. It is, therefore, a reactive approach in which we look for feasible solutions minimizing both the project completion date and the maximum number of resources assignment changes. In the second studied model, we focus on a case where a task exactly requires one skill with preemption possibility only in case of resources unavailability. In this model, a task is also characterized by its release and due date. A cost per person/skill is given. It is, therefore, a bi-objective problem in which the computed solutions must minimize both the maximum tardiness and the project global cost. Heuristics and meta-heuristics are proposed for solving this problem. Some proposed methods are integrated in the framework OFBiz as add-ons.

In this dissertation we first derive a new unified upper solution bound for the continuous coupled algebraic Riccati equation, which arises from the optimal control of a Markovian jump linear system. In particular, we address the issue of rank deficiency with the control matrices. In the case of rank deficiency the existing matrix upper bounds are inapplicable. Moreover, our new result is not restricted to rank deficiency cases only. It now contains the existing results as special cases. Next, an iterative refinement is presented to improve our new unified matrix upper solution bounds. In particular, this iterative refinement determines a monotonically decreasing sequence of upper bounds for the solution of the continuous coupled algebraic Riccati equation. We formulate a new iterative algorithm by modifying this iterative refinement. We also prove that this new algorithm generates a monotonically decreasing sequence of matrix upper solution bounds that converges to the maximal solution of the continuous coupled algebraic Riccati equation. Furthermore, we prove the convergence of an accelerated Riccati iteration which computes a positive semidefinite solution of the continuous coupled algebraic Riccati equation. In particular, we establish sufficient conditions for the convergence of this algorithm. We also prove that for particular initial values this algorithm determines a monotonically increasing sequence of positive semidefinite matrices that converge to the minimal solution of the continuous coupled algebraic Riccati equation. Additionally, we show that for specific initial values this algorithm generates a monotonically decreasing sequence that converges to the maximal solution of the continuous coupled algebraic Riccati equation. In addition, we prove that this accelerated Riccati iteration converges faster than the Riccati iteration. Finally, we formulate a weighted modified accelerated Riccati iteration which is a more generalized Riccati type iteration. All of the existing Riccati iterations are now the special cases of this algorithm. Furthermore, we establish sufficient conditions for the convergence of this algorithm and we prove the monotonic convergence of the sequence generated by this algorithm. We also discuss how the weight and other quantities affect the rate of convergence of this algorithm. Illustrative numerical examples are also presented.

Cette thèse porte sur le phénomène de superconcentration qui apparaît dans l'étude des fluctuations de divers modèles de la recherche actuelle (matrices aléatoires, verres de spins, champ libre gaussien discret, percolation,...). Plus particulièrement, la thèse est consacrée à l'examen d'inégalités de superconcentration à l'échelle exponentielle ; notamment pour des supremum de familles gaussiennes. Les outils mis en œuvre comprennent la propriété d'hypercontractivité de semi-groupes de Markov. Par ailleurs, celle-ci a conduit à une version d'ordre supérieur d'une inégalité sur la variance de M. Talagrand. La première partie de la thèse présente brièvement les notions essentielles de la théorie classique de la concentration de la mesure ainsi que les principaux outils, à savoir : méthodes d'interpolations à l'aide de semi-groupes markoviens, inégalités fonctionnelles, transport optimal et isopérimétrie. Un survol de la littérature existante est ensuite proposé. La deuxième partie du manuscrit rassemble, dans différents chapitres, les travaux que nous avons effectués durant cette thèse. Une grande partie de ceux-ci repose sur la représentation dynamique de la variance le long du semi-groupe d'Ornstein-Uhlenbeck et sa propriété d'hypercontractivité. De nouvelles inégalités de superconcentration sont obtenues au niveau exponentiel et illustrées sur des exemples provenant de la théorie des extrêmes. Le cadre de l'hypercontractivité a également conduit à une nouvelle inégalité sur le cube discret, celle-ci permettant une application sur l'influence d'ordre deux de fonctions booléennes. Enfin, le dernier chapitre aborde la phénomène de superconcentration par le transport optimal. Des majorations de la variance et des inégalités de déviations non asymptotiques pour le maximum de variables aléatoires indépendantes et de même loi sont obtenues. A nouveau, des illustrations pour des lois usuelles, appartenant aux différents domaines d'attraction de la théorie des extrêmes, sont proposées / The thesis focuses on the superconcentration phenomenon which appears in the study of the fluctuations of various moelds from current research (random matrices, spin glasses, discrete Gaussien free field, percolation,...). More precisely, the thesis mainly deals with superconcentration inequalities at an exponentiel level ; in particular for supremum of familu of Gaussian random variables. The principal tools used during this study are the hypercontractive property satisfied by some Markov semi-groups ; this approach leads to an extension of higher order of an inequality due to M. Talagrand. The first part of the thesis exposes the fundamental notions of concentration of measure, interpolation methods with Markovians semi-groups, functional inequalities, optimal transport and isoperimetry. Then, a survey of the literature concerning superconcentration phenomenon is done. The second part of the manuscript bring together, in different chapters, the results obtained during the thesis. Most of them are based on the dynamical representation of the variance along the semi-group of Ornstein-Uhlenbeck and its hypercontractive property. New ineqaulities are obtained at an exponential level and are illustrated on examples coming from extreme theory. This hypercontractive framework also gave birth to a new inequality on the discrete cube which leads to an application on the influence of second order of boolean functions. Finally, the last chapter is about the superconcentration phenomenon with an optimal transport approach. Some non asymptotic bounds on the variance and deviations inequalities are obtained for the maximum of an i.i.d. sample. Again, illustrations for usual laws of probability, belonging to different domain of attraction from extreme theory, are given.