Seminar on Computer Science and Applied Mathematics
Upravni odbor Matematickog instituta SANU je na nedavnoj sednici doneo odluku da se dosadasnji Seminar za primenjenu matematiku, sada nazove Seminar za racunarstvo i primenjenu matematiku, a u cilju potenciranja znacaja racunarstva kao jedne od oblasti delatnosti Instituta. Istovremeno, Upravni odbor doneo je odluku o osnivanju Odeljenja za racunarstvo i primenjenu matematiku i vezao rad novog odeljenja za rad Seminara za racunarstvo i primenjenu matematiku.
OBRATITE PAZNJU NA PROMENU TERMINA!!!
Angelo Sifaleras, School of Information Sciences, University of Macedonia, Thessaloniki, Greece
EXTERIOR POINT SIMPLEX-TYPE ALGORITHMS FOR LINEAR AND NETWORK OPTIMIZATION PROBLEMS
Abstract: Two decades of research led to the development of a number of efficient algorithms that can be classified as exterior point simplex-type. This type of algorithms can cross over the infeasible region of the primal (dual) problem and find an optimal solution reducing the number of iterations needed. The main idea of exterior point simplex-type algorithms is to compute two paths/flows. Primal (dual) exterior point simplex-type algorithms compute one path/flow which is basic but not always primal (dual) feasible and the other is primal (dual) feasible but not always basic. The aim of this talk is to present the developments in exterior point simplex-type algorithms for linear and network optimization problems, over the recent years. We also present other approaches that, in a similar way, do not preserve primal or dual feasibility at each iteration such as the monotonic build-up Simplex algorithms and the criss-cross methods. Finally, we discuss about possible future research directions in these algorithmic approaches.
Petar Jevtic, University of Torino, Italy
TWO EXAMPLE APPLICATIONS OF THE DIFFERENTIAL EVOLUTION ALGORITHM IN FINANCE AND INSURANCE
Abstract: The first example pertains to the field of life insurance, specifically the modeling of mortality risk. A cohort-based model which captures the characteristics of a mortality surface with a parsimonious, continuous-time factor approach will be presented. The model is implemented on UK data for the period 1900-2008 and calibration by means of stochastic search and the Differential Evolution optimization algorithm proves to yield robust and stable parameters. The second example pertains to the investment finance domain, specifically exotic options. A new dimension of calibration risk, given by the estimation error in model parameters, in the context of exotic option pricing, is investigated. Looking at two popular option pricing models and various calibration settings such as error functionals, dataset features, and optimization routines (local and global), we analyze the impact of estimation risk on exotic option prices, by computing confidence intervals via non-parametric bootstrap re-sampling.
Anton Eremeev, Discrete Optimization Laboratory, Omsk Branch of Sobolev Institute of Mathematics, Russia
OPTIMAL RECOMBINATION IN GENETIC ALGORITHMS
Abstract: This talk is a survey of results on complexity of the optimal recombination problem (ORP), which consists in finding the best possible offspring as a result of a recombination operator in a genetic algorithm, given two parent solutions. We consider efficient reductions of the ORPs, allowing to establish polynomial solvability or NP-hardness of the ORPs, as well as direct proofs of hardness results.
F. Javier Martin-Campo, Facultad de Ciencias Economicas y Empresariales, Universidad Complutense de Madrid
MULTI-OBJECTIVE MIXED INTEGER NONLINEAR OPTIMIZATION MODELS TO SOLVE THE AIRCRAFT CONFLICT DETECTION AND RESOLUTION PROBLEM BY APPLYING VNS
Abstract: Two general Mixed Integer Nonlinear Optimization models are presented to tackle the Conflict Detection and Resolution problem in Air Traffic Management. Given a set of flights as well as their configurations, the aim of the problem consists of providing a new configuration such that every conflict situation is avoided, being such an event in which two or more aircraft violate the minimum safety distances that they must keep during the flights (5 nm. and 1000 feet as horizontal and vertical distances, respectively). The first model solves the problem by performing only horizontal maneuvers (velocity and heading angle changes) whereas the second performs both, horizontal and vertical maneuvers at once. The proposed models detect and solve the conflict situations. They are based on a geometric construction which involves many trigonometric functions, so that, the model is constrained by a large set of trigonometric and nonconvex inequalities. Three different criteria based on goal programming are presented in order to give some useful information to the air traffic controllers about the maneuvers to perform. As the state-of-the-art Mixed Integer Nonlinear Optimization solver, Minotaur, does not give a solution in almost real time, a VNS procedure is implemented in order to obtain good solutions in shorter computing time.
Joint work with Antonio Alonso-Ayuso, Laureano F. Escudero, Nenad Mladenovic