IFORS Global Webinar Series - ALIO
O.R. in Latin America: From Theory to Practice (July 29,2020)
Guest Speakers
Title: Parametric relaxation for the quadratic knapsack problem
Marcia Fampa
COPPE - Universidade Federal do Rio de Janeiro (UFRJ)
Abstract:
We consider a parametric convex quadratic programming relaxation for the quadratic knapsack problem (QKP), which maintains partial quadratic information from the original QKP by perturbing the objective function to obtain a concave quadratic term. The nonconcave part generated by the perturbation is then linearized by a standard approach that lifts the problem to matrix space.
We present a primal-dual interior point method to optimize the perturbation of the quadratic function, and propose valid inequalities on the lifted matrix variable, derived from cover inequalities for the QKP.
Our best bounds are obtained with an algorithmic approach that alternates between optimizing the parametric relaxation over the perturbation and applying cutting planes generated by the valid inequalities proposed.
(This is a joint work with Daniela Lubke, Fei Wang and Henry Wolkovicz.)
Title: Level of traffic stress in Bogotá: towards a friendlier city for cyclists”
Andrés L. Medaglia
Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia
Abstract:
The Level of Traffic Stress (LTS) is an indicator that quantifies the stress experienced by a cyclist on the segments of a road network. We propose an LTS-based classification with two components: a clustering component and an interpretative component. Our methodology is comprised of four steps: (i) compilation of a set of variables for road segments, (ii) generation of clusters of segments within a subset of the road network, (iii) classification of all segments of the road network into these clusters using a predictive model, and (iv) assignment of an LTS category to each cluster. At the core of the methodology, we couple a classifier (unsupervised clustering algorithm) with a predictive model (multinomial logistic regression) to make our approach scalable to massive data sets. Our methodology is a useful tool for policy-making, as it identifies suitable areas for interventions; and can estimate their impact on the LTS classification, according to probable changes to the input variables (e.g., traffic density). We applied our methodology on the road network of Bogotá, Colombia, a city with a history of implementing innovative policies to promote biking. To classify road segments, we combined government data with open-access repositories using geographic information systems (GIS). Comparing our LTS classification with city reports, we found that the number of bicyclists’ fatal and non-fatal collisions per kilometer is positively correlated with higher LTS. Finally, to support policy making, we developed a web-enabled dashboard to visualize and analyze the LTS classification and its underlying variables. (This is a joint work with Jorge A. Huertas Alejandro Palacio, Marcelo Botero, Germán A. Carvajal, Thomas van Laake, Diana Higuera-Mendieta, Sergio A. Cabrales, Luis A. Guzman, Olga L. Sarmiento)
Title: A case study on the potential impact of a kidney exchange program in Mexico
Roger Rios
Universidad Autonoma de Nuevo Leon – UANL, Mexico
Abstract:
The application of Operations Research in the medical field has been the key to save more lives in a variety of decision-making problems. With the aid of mathematical models and algorithms developed for specific problems, we can now develop plans and policies, and take decisions that can lead to optimal or near optimal solutions. This is the case of the Kidney Exchange Problem (KEP) addressed in this talk. The KEP is a combinatorial optimization problem arising in the context of transplant programs that allow exchange of kidneys between two or more incompatible patient-donor pairs. The KEP aims at maximizing the number of transplants in a given PDP compatibility graph. Finding cycles or paths in a graph of PDPs leads to finding feasible pairs that can benefit from kidney exchange between pairs.
The KEP has been studied from many angles for the past 15 years. Many studies have shown the tremendous impact and benefit of this type of programs in terms of dramatic reductions to organ waiting lists, and therefore saving the lives of many people. Nation-wide kidney exchange programs have been successfully developed in a few countries; however, in many developing countries, including Mexico, nation-wide programs do not exist. For instance, the kidney waiting list in Mexico is over 17,000 and growing at a very fast rate.
In this talk, we will give a brief introduction to the KEP, its basic models and solution algorithms. In addition, a case study of optimal kidney transplant assignments in the state of Nuevo Leon, Mexico, is presented. The study, carried out by using data from Mexican population and hospitals, pretends to assess the potential impact of implementing a kidney exchange program in Mexico.