Department of Statistics and Operations Research

Seminar Schedule: Year 2005


AN EXACT APPROACH FOR THE VEHICLE ROUTING PROBLEM WITH TWO-DIMENSIONAL LOADING CONSTRAINTS

CONVIDAT: Daniele Vigo. Dipartimento di Elettronica, Informatica e Sistemistica. Università di Bologna, Italia.

IDIOMA: Anglès

LLOC: Seminari 1, Edifici U, Facultat de Matematiques i Estadistica, C/ Pau Gargallo 5.

DATA: Divendres, 25 de febrer de 2005, 12h30m

RESUM: We consider a special case of the symmetric capacitated vehicle routing problem, in which a fleet of K identical vehicles must serve n customers, each with a given demand consisting in a set of rectangular two-dimensional weighted items. The vehicles have a two-dimensional loading surface and a maximum weight capacity. The aim is to find a partition of the customers into routes of minimum total cost and such that, for each vehicle, the weight capacity is taken into account and a feasible two-dimensional allocation of the items into the loading surface exists. The problem has several practical applications in freight transportation and it is NP-Hard in the strong sense. We propose an exact approach, based on a branch-and-cut algorithm, for the minimization of the routing cost, that iteratively calls a branch-and-bound algorithm for checking the feasibility of the loadings. Heuristics are also used in order to improve the overall performance of the algorithm. The effectiveness of the approach is shown by means of computational results.

Inici
INTRODUCTION TO ADVANCED DISCRETE CHOICE MODELS

CONVIDAT: Michel Bierlaire. Institute of Mathematics, School of Basic Sciences. Ecole Polytechnique Fédérale de Lausanne, Suïssa.

IDIOMA: Anglès

LLOC: Aula 005, Edifici U, Facultat de Matematiques i Estadistica, C/ Pau Gargallo 5.

DATA: Dimecres, 16 de març de 2005, 12h30m

RESUM: The first part of the lecture will consist in an introduction to discrete choice models, with emphasis on the concept of Generalized Extreme Value models. GEV models will be presented and motivated, and common instances will be described. In the second part, some theoretical properties will be emphasized, in order to lead to important concrete applications. The first application will deal with the derivation of new GEV models. The second application will deal with issue of sampling strategies, and sampling of alternatives. In the third part, advanced modeling features, including the concept of mixture of distributions, and nonlinear utility functions will be presented. Finally, the estimation of these models using Biogeme will be discussed.

TRANSPARENCIES DE LA PRESENTACIO: clica aquí

Inici
CONSISTENCY AND ASYMPTOTIC NORMALITY FOR PARTICLE FILTERS

CONVIDAT: Hans Rudolf Künsch. Seminar für Statistik, Department of Mathematics. ETH Zurich, Switzerland.

IDIOMA: Anglès

LLOC: Seminari 1, Edifici U, Facultat de Matematiques i Estadistica, C/ Pau Gargallo 5.

DATA: Divendres, 18 de març de 2005, 12h30m

RESUM: We consider a special case of the symmetric capacitated vehicle routing problem, in which a fleet of K identical vehicles must serve n customers, each with a given demand consisting in a set of rectangular two-dimensional weighted items. The vehicles have a two-dimensional loading surface and a maximum weight capacity. The aim is to find a partition of the customers into routes of minimum total cost and such that, for each vehicle, the weight capacity is taken into account and a feasible two-dimensional allocation of the items into the loading surface exists. The problem has several practical applications in freight transportation and it is NP-Hard in the strong sense. We propose an exact approach, based on a branch-and-cut algorithm, for the minimization of the routing cost, that iteratively calls a branch-and-bound algorithm for checking the feasibility of the loadings. Heuristics are also used in order to improve the overall performance of the algorithm. The effectiveness of the approach is shown by means of computational results.

Inici
THE ANALYSIS OF CORRELATED FAILURE TIMES IN CLINICAL TRIALS

CONVIDAT: John Whitehead. Medical and Pharmaceutical Statistics Research Unit. The University of Reading, UK.

IDIOMA: Anglès

LLOC: Seminari 1, Edifici U, Facultat de Matematiques i Estadistica, C/ Pau Gargallo 5.

DATA: Divendres, 1 d'abril de 2005, 12h30m

RESUM: This talk concerns the derivation and use of a formula for the covariance between two logrank statistics. Typically these will both concern a comparison of the survival experiences of subjects in two treatment groups. Each logrank statistic will be calculated on data from a different time-to-event response. For example, in a clinical trial of a treatment for lung cancer, these could be time to disease progression and time to death from any cause. The estimate of such a covariance is useful for testing "global hypotheses" and for deriving joint confidence regions, amongst other applications. The derivation of the formula follows from a similar expression for score statistics derived for the conditional analysis of a 2x2 contingency table. A comparison is made with the method of Wei, Lin and Weissfeld, which is based on the use of a sandwich estimator.

Inici
SCAN STATISTICS: DEFINICIÓN Y EJEMPLOS

CONVIDAT: Claude Langrand. Université des Sciences et Technologies de Lille (Lille-1). Francia.

IDIOMA: Castellà
LLOC: Seminari 1, Edifici U, Facultat de Matematiques i Estadistica, C/ Pau Gargallo 5.

DATA: Divendres, 15 d'abril de 2005, 12h30m

RESUM: Dados X1, X2,…,Xn distribuidos al azar sobre el intervalo unidad, se nota N[x, x+d[ el número de dichos puntos contenidos en el intervalo [x, x+d[. El scan statistic está definido como el número máximo de puntos en una ventana de longitud d, es decir, el sup{ N[x, x+d[, x[0,1-d[}. Dicho estadístico se utiliza para poner a prueba la presencia de reagrupamientos no aleatorios. Scan statistic tiene numerosas aplicaciones en varios problemas científicos y de ingeniería, en campos como la epidemiología, ls genética, las telecomunicaciones o el márketing.

ARTICLE COMPLET: clica aquí

Inici
ON ROUTING PROBLEMS IN TELECOMMUNICATIONS NETWORKS

CONVIDAT: Adam Ouorou. Co-head of the research program on network modelling and optimization. France Telecom R&D Division.

IDIOMA: Anglès
LLOC: Seminari 1, Edifici U, Facultat de Matematiques i Estadistica, C/ Pau Gargallo 5.

DATA: Divendres, 13 de maig de 2005, 12h30m

RESUM: Given a network with known link capacities and traffic demands, one can compute the paths to be used and the amount of traffic to be send through each path by solving a classical multi-flow problem. In the first part of the talk, we consider the routing problem in which the QOS function is the Kleinrock average delay function. We will review some solution methods with a focus on a proximal-like algorithm using two augmented Lagrangian functions. In the second part, we consider that more quality of service constraints such as delay constraints, may be imposed. The routing problem becomes difficult to solve. We assume that the delay on each link depends on both its capacity and the total flow on it. We then show that satisfying the delay constraints and the capacity constraints is an NP-complete problem. We give a convex relaxation of the delay constrained routing problem and present some ways to get upper and lower bounds on the problem (this second part is a joint work with W. Ben Ameur, INT France).

Inici
SOBRE LA POTENCIA PARA DETECTAR LIGAMENTO GENÉTICO DE LOS CONTRASTES BASADOS EN PROPORCIONES DE ALELOS HEREDADOS DE UN ANCESTRP COMÚN.

CONVIDAT: Sonia Hernández. Universidad Rey Juan Carlos. Madrid.

IDIOMA: Castellà
LLOC: Seminari 1, Edifici U, Facultat de Matematiques i Estadistica, C/ Pau Gargallo 5.

DATA: Divendres, 20 de maig de 2005, 12h30m

RESUM: La finalidad del análisis de ligamiento genético es localizar los genes asociados a un determinado rasgo, por ejemplo a una enfermedad. Para lograr este objetivo se utilizan diferentes técnicas estadísticas que relacionan la similitud genética (genotipo) entre individuos de la especie de interés con su similitud física (fenotipo). En los organismos experimentales se pueden llevar a cabo los cruces que resultan más informativos para el análisis, pero cuando se trabaja con seres humanos la información disponible se limita a la que proporcionan grupos de parientes. Una de las estrategias más extendidas para detectar ligamiento genético en humanos es la de relacionar la similitud del fenotipo de pares de familiares con el número de alelos idénticos por descendencia que comparten, es decir, con el número de genes que han heredado de un mismo ancestro. En este seminario se describirán algunos de los métodos estadísticos que se aplican para analizar este tipo de datos y se compararán dos clases de contrastes para la detección de ligamiento genético en humanos.

Inici
PROPERTIES OF A SEQUENTIAL QUADRATIC PROGRAMMING ITERATION

CONVIDAT: Clovis Gonzaga. Universidade Federal de Santa Catarina. Florianopolis, Brasil.

IDIOMA: Anglès
LLOC: Aula 005, Edifici U, Facultat de Matematiques i Estadistica, C/ Pau Gargallo 5.

DATA: Dilluns, 30 de maig de 2005, 12h30m

RESUM: Most of the modern methods for constrained nonlinear programming are based on sequential quadratic iterations. An iteration starts from an arbitrary, usually infeasible point, and deals with two conflicting objectives: reducing infeasibility and reducing the objective value. The available tools are first and second order models for a Lagrangean function. The conflict between the objectives is resolved either by using a merit function or by the construction of a filter. We relate classical SQP and inexact restoration procedures, showing the role of the trust regions used by each methods and describing their local convergence properties. We also comment on the use of filters and merit functions to ensure global convergence of the methods.

Inici
SOLVING STRUCTURED LINEAR PROGRAMMING PROBLEMS BY INTERIOR POINT METHODS: THE CASE OF NETWORK FLOW PROBLEMS

CONVIDAT: Claudio Gentile. Institute of System Analysis and Computer Science "Antonio Ruberti". Italian National Research Council, Roma, Italia.

IDIOMA: Anglès
LLOC: Aula 005, Edifici U, Facultat de Matematiques i Estadistica, C/ Pau Gargallo 5.

DATA: Dimecres, 1 de juny de 2005, 12h30m

RESUM: In this talk we recall some methods to solve Structured Linear Programming problems by Interior Point methods and then we focus our attention to the case of Minimum Cost Flow (MCF) problems. We propose a new set of preconditioners for the iterative solution, via a Preconditioned Conjugate Gradient (PCG) method, of the KKT systems that must be solved at each iteration of an Interior Point (IP) algorithm for the solution of linear MCF problems. These preconditioners are based on the idea of extracting a proper triangulated subgraph of the original graph which strictly contains a spanning tree. We define a new class of triangulated graphs, called Brother-Connected Trees (BCT), and discuss some fast heuristics for finding BCTs of ``large'' weight. Finally, some computational results are discussed.

Inici
APLICACIÓN DE MODELOS MIXTOS SEMIPARAMÉTRICOS AL ANÁLISIS DE DATOS LONGITUDINALES: AJUSTE DE CURVAS INDIVIDUALES.

CONVIDAT: María Durban. Universidad Carlos III. Madrid.

IDIOMA: Castellà
LLOC: Seminari 1, Edifici U, Facultat de Matematiques i Estadistica, C/ Pau Gargallo 5.

DATA: Dijous, 16 de juny de 2005, 12h30m

RESUM: En este trabajo se presenta un modelo semiparamétric sencillo para el ajuste de curvas individuales en datos longitudinales. Las curvas individuales se modelizan mediante P-splines con coeficientes aleatorios. Este tipo de modelos tiene una representación como modelos mixtos y se implementa de forma sencilla en los paquetes estadísticos más comunes. La metodología presentada se ilustrará con el análisis de datos sobre el efecto a largo plazo de tres terapias en la altura de niños que padecen leucemia linfoblástica.

Inici
OPTIMIZATION OF DISTANCES FOR DECISION MAKING

CONVIDAT: Emilio Carrizosa. Universidad de Sevilla.

IDIOMA: Castellà
LLOC: Aula C5016, Campus Nord, UPC (veure mapa)

DATA: Divendres, 21 d'octubre de 2005, 12h30m

RESUM: Decision-Making literature is full of methods whose cornerstone is an optimization problem related with the optimization of distances in vector spaces. This includes, in particular, instances in Data Mining (Support Vector Machines), Multiple-Criteria Decision Making (Goal Programming, Ideal-Point Methods, ...). The above-mentioned problems share a common structure, and can be analyzed using standard tools of Convex Analysis. In this talk we present a general framework which includes these problems as particular instances. Special emphasis will be made in the geometrical analysis of Support Vector Machines (under the assumptions that distances are measured according to an arbitrary norm and constraints are allowed in the model) and (Generalized) Linear Goal Programming.

TRANSPARÈNCIES DE LA PRESENTACIÓ: clica aquí

Inici
PLANNING PATIENT TRANSPORTS IN HOSPITALS

CONVIDAT: Stefan Nickel. Saarland University, Germany.

IDIOMA: Anglès
LLOC: Aula C5016, Campus Nord, UPC (veure mapa)

DATA: Dimecres 16 de novembre de 2005, 12h30m

RESUM: Planning transport processes in hospitals is a quite complex and involved task. On one hand very different kinds of transports have to be managed: meals have to be delivered, beds have to be relocated upon the arrival and departure of patients, drugs and blood need to be made available in time, and patients have to arrive punctually at treatment rooms. On the other hand, there is a high uncertainty in the data available. This is due not only to the occurrence of emergency tasks but also because of the still underdeveloped availability of well-maintained and accurate data in hospitals. This talk is devoted to an online dial-a-ride problem arising in the transportation of patients in a hospital campus. The talk will focus on routing and scheduling vehicles (e.g., ambulances, transport teams on foot) that serve requests for transporting patients between wards and examination rooms. The efficient organization of these transports strongly affects the planning of activities in other hospital wards (e.g., operation room planning). Based on real-life cases we will show that the problem complexity is increased by a number of specific service-related constraints in addition to those encountered in typical dial-a-rideproblems. Hospital inherent aspects include, among others, accounting for transport priorities (e.g., emergency requests), for transportation aids (a patient transport may generate additional transport requests for material and/or personnel that must accompany the patient), for different vehicle types and personnel skills, and for soft time windows with respect to the desired pickup and/or drop-off times of the patients. Such constraints significantly complicate the construction and modification of high-quality feasible schedules. Therefore, a heuristic approach will be proposed and the results obtained using real data from two German hospitals will be discussed. Moreover, we will briefly present the software tool Opti-Trans in which the optimization algorithms are integrated.

TRANSPARÈNCIES DE LA PRESENTACIÓ: clica aquí

Inici
PROCESOS DE RAMIFICACIÓN BISEXUALES EN UN CONTEXTO GENÉTICO: GENES LIGADOS AL SEXO.

CONVIDAT: Miguel Velasco. Universidad de Extremadura.
IDIOMA: Castellà
LLOC: Aula C5016, Campus Nord, UPC (veure mapa)

DATA: Divendres 25 de novembre de 2005, 12h30m

RESUM: Dentro de la literatura científica sobre dinámica de poblaciones los procesos de ramificación ocupan un lugar preponderante, como lo ponen de manifiesto recientes monografías, por ejemplo Kimmel and Axelrod (2002), Pakes (2003) o Haccou, Jagers and Vatutin (2005). Este Seminario se enmarca dentro de ese ámbito, centrando su atención en los llamados procesos de ramificación bisexuales y en la aplicación de los mismos dentro de un contexto genético.
Es bien conocido que en algunas poblaciones animales el sexo de los individuos viene determinado por un par de cromosomas X (ó Z) e Y (ó W). Una hembra tendrá cromosomas XX, mientras que un macho tendrá cromosomas XY. Algunos caracteres que presentan los individuos son controlados por genes ligados al cromosoma X, otros por genes asociados al cromosoma Y y otros por genes ligados a ambos cromosomas. Teniendo en cuenta este hecho, encontraremos en cualquier población hembras y machos con diferentes genotipos y/o fenotipos. Además estas hembras y machos se unirán formando parejas para generar nuevos individuos. Cada uno de estos descendientes recibirá su estructura genética de acuerdo con las reglas de la herencia asociadas a su especie.
Desde un punto de vista práctico tiene interés analizar la evolución, generación a generación, de genes ligados al sexo. Previamente debemos modelizar dicha evolución mediante un proceso que considere reproducción sexual, puesto que estamos asumiendo que los descendientes son generados por parejas. Hasta ahora, los modelos de ramificación propuestos para el estudio de la evolución genética no han tenido en cuenta la necesidad de una interacción sexual entre hembras y machos antes de la reproducción. En este contexto propondremos un proceso de ramificación bisexual bidimensional adecuado para describir el comportamiento de los genes ligados al cromosoma Y. Presentaremos condiciones para la extinción y/o supervivencia de estos genes en la población, así como resultados sobre sus tasas de crecimiento en caso de no extinguirse.
Referencias
[1] Haccou, P., Jagers, P. and Vatutin, V. (2005). Branching processes: Variation, growth, and extinction of populations. Cambridge University Press.
[2] Kimmel, M. and Axelrod, D.E. (2002). Branching processes in Biology. Springer-Verlag New York, Inc.
[3]Pakes, A. (2003). Biological application of branching processes. Handbook of Statistic Vol. 21 Stochastic Processes: Modelling and Simulation (Shanbhag, D.N. and Rao, C.R., eds.) Chapter 18, 693-773, Elsevier Science B.V.

Inici
MUESTREO DE POBLACIONES FINITAS: MODELOS PARA EL DISEÑO Y ANÁLISIS DE ENCUESTAS

CONVIDAT: Luis Ambrosio. Universidad Politécnica de Madrid.

IDIOMA: Castellà
LLOC: Aula C5016, Campus Nord, UPC (veure mapa)

DATA: Divendres 2 de desembre de 2005, 12h30m

RESUM: El muestreo de poblaciones finitas es un importante sector de la actividad económica. El elevado número de encuestas que anualmente llevan a cabo tanto las Administraciones públicas (la web del INE http://www.ine.es/ioe/ioe.jsp recoge un inventario de más de 150 encuestas anuales con observación directa de datos sobre más de veinte temas), como el sector privado suponen un coste elevado. El diseño de planes de muestreo que permitan reducir el coste del muestreo para un grado de precisión fijado, continúa siendo un tema de investigación y de interés académico.
En éste seminario se consideran dos de las estrategias de muestreo en las que se hace uso de modelos. En una de ellas (la "asistida por modelos") los modelos se utilizan para el diseño de la muestra, pero la inferencia se basa en el diseño. En la otra, la inferencia se basa en modelos. El interés se centra en la eficiencia relativa de esas estrategias. Las estrategias se ilustran a partir de tres casos de estudio: (i) el diseño de muestras sistemáticas en poblaciones espaciales "asistido por modelos", (ii) la estimación en áreas pequeñas o dominios de estudio "basada en modelos" lineales mixtos y (iii) el muestreo de poblaciones en el espacio y en el tiempo "basado en modelos" lineales generalizados mixtos.

Inici
MODELS MULTI-ESTAT I PROCÉS DE SUPERVIVÈNCIA PREDICTIU

CONVIDAT: Malu Calle. Universitat de Vic.

IDIOMA: Català
LLOC: Aula C5016, Campus Nord, UPC (veure mapa)

DATA: Divendres 16 de desembre de 2005, 12h30m

RESUM: Els models de supervivència multi-estat són especialment útils en el context dels assaigs clínics longitudinals on l'evolució de l'estat de salut de cada pacient és observada durant un període de temps. Els models multi-estat permeten analitzar l'efecte sobre la supervivència dels canvis que es produeixen en els pacients durant el seu seguiment. Aquesta metodologia s'il?lustrarà amb un estudi sobre factors pronòstics en geriatria. L'objectiu de l'estudi és analitzar l'efecte de la pèrdua funcional i nutricional sobre la mortalitat de persones grans fràgils. Els models de supervivència multi-estat ens permeten avaluar l'associació entre mortalitat i recuperació dels nivells funcionals i nutricionals considerats normals. Després d'estimar el model i d'identificar els factors pronòstics de mortalitat és possible obtenir un procés predictiu que permet fer prediccions de la supervivència dels pacients en funció de la seva història concreta fins a un determinat moment. Això proporciona un pronòstic més precís de cada grup de pacients, la qual cosa pot ser molt útil per als professionals sanitaris a l'hora de prendre decisions clíniques.

Inici