Seminar schedule: Year 2012
- Tuesday, November 20, 2012, Time: 12:30
Joaquim J. Júdice, Instituto de Telecomunicações, Portugal
- Friday, november 16, 2012, Time: 12:30
M. Grazia Speranza. University of Brescia, Italy
- Friday, October 19, 2012, Time: 12:30
Enrique Benavent, Statistics and Operations Research Department, University of Valencia
- Friday, september 21st 2012, Time: 12:30
Eligius M.T. Hendrix, Universitat de Malaga/Wageningen University
- Friday, May 18th 2012, Time: 12:30
- Wednesday, April 18th 2012, Time: 12:30
Maarten van der Vlerk, Department of Operations, University of Groningen, The Netherlands
- Thursday, March 15th 2012, Time: 12:30
Albert Sorribas, Department de Ciències Mèdiques Bàsiques, Universitat de Lleida
- Friday, January 27th 2012, Time: 12:30
Complementarity Problems and Variational Inequalities
SPEAKER: Joaquim J. Júdice
PLACE: C5 Building, Room C5016, Campus Nord, UPC (see map)
DATE: Tuesday, november 20, 2012. TIME: 12:30
A Complementarity Problem (CP) is an optimization problem containing a number of comple-
mentary variables xi and wi satisfying constraints of the form xiwi = 0. This problem has found
many applications in different areas of science, engineering, economics and finance. A number
of extensions of this problem have been considered in the literature, namely Variational Inequali-
ties (VI), Optimization Problems with Complementarity Constraints (OPTCC) and more recently
Eigenvalue Complementarity Problems (EiCP). In this talk all these problems are defined together
with a brief summary of their applications. Some existence results for these problems are reviewed.
A number of efficient direct and iterative algorithms have been proposed to process the CP, VI,
OPTCC and EiCP by finding stationary points of appropriate merit functions. These algorithms
are introduced, together with their benefits and drawbacks. In particular, these techniques require
special classes of matrices for guaranteeing that those stationary points are solutions of the prob-
lems. In general, only enumerative algorithms are able to solve CP, VI, OPTCC and EiCP. The
most important of these methods are also presented. A number of numerical results are reported
to illustrate the efficacy and efficiency of the techniques discussed in the talk.
Joaquim João Júdice is a Retired Full Professor of the Department of Mathematics of
University of Coimbra, since November 2011. He is also a current member of the Instituto de
Telecomunicações of Portugal. He is an Associate Editor of 13 international research journals in
the areas of Mathematics and Operational Research. He was referee of several papers submitted
to 38 different international journals. He was in the Organizing Committee of 22 national and
international conferences and in the Scientific Committee of 58 conferences. He was Director of
the Department of Mathematics of the University of Coimbra for two years, President of Centro
Internacional de Matem´atica (CIM) for four years, President of the Portuguese Operational Society
(APDIO) for two years and Vice-President of the Portuguese Mathematical Society (SPM) for
two years. He received the 2012 EUROPT Fellow. He is author or co-author of 64 papers in
international research journals, 14 in national journals with referee and 23 in edited volumes with
referee and of 19 books and lecture notes.
Click here for further information on Joaquim Júdice.
Routing problems with profits
SPEAKER: M. Grazia Speranza
PLACE: C5 Building, Room C5016, Campus Nord, UPC (see map)
DATE: Friday, november 16, 2012. Time: 12:30
While the literature is rich of papers that study routing problems where all customers to be served are given, the number of papers on routing problems with profits is much more limited. These problems model situations where a set of customers has to be selected, and have a number of interesting applications, in particular in the context of auctions in the transportation sector. The interest in these problems is growing. Work has been done in the case of one vehicle, while very little is available for the case of multiple vehicles.
In this talk I will overview the state of the art in routing problems with profits, introducing the basic problems of this class. I will then focus on some recently studied problems. I will present two capacitated node routing problems and one arc routing problem with profits. I will also present solution algorithms, both exact, namely a branch-and-price, and heuristic. While the exact algorithms can solve, for each of the problems, instances of small size, the heuristics obtain very good results in terms of solution quality, within a reasonable amount of time. The optimal solution on small instances allows us to evaluate, at least on those instances, the behaviour of the heuristics precisely.
(STTRPSD)SPEAKER: Enrique Benavent
PLACE: Building C5, Room C5016, Campus Nord, UPC (see map)
DATE: Friday, october, 19 TIME: 12:30
En el STTRPSD se dispone de un camión con un remolque desmontable que, partiendo de un depósito, tiene que servir la demanda de un conjunto de clientes que son accesibles sólo con el camión. Así, antes de servir a los clientes, es necesario desmontar el remolque en lugares de aparcamiento apropiados (puntos de recarga) y transferir productos entre el camión y el remolque. La ruta de servicio se puede descomponer entonces en: una ruta que sigue el camión con el remolque que pasa por los puntos de recarga elegidos y un conjunto de rutas, para el camión sólo, que salen de los puntos de recarga y que realizan el servicio a los clientes. Este problema tiene aplicaciones por ejemplo en la recogida de leche en granjas que no son accesibles por vehículos de gran tamaño.
En este trabajo se presenta una formulación del problema como un problema lineal entero. Esta formulación es reforzada con varias familias de desigualdades válidas para las que se ha diseñado diversos algoritmos de separación. Todo ello es la base de un algoritmo de branch-and-cut que permite resolver el STTRPSD para instancias de tamaño medio (hasta 100 nodos) y proporciona cotas inferiores ajustadas en instancias de mayor tamaño.
Éste es un trabajo conjunto con J.G. Villegas, J.M. Belenguer, A. Martínez, C. Prins y C. Prodhon
The speaker: Profesor Benavent got a a Ph.D. in Mathematics from the University of Valencia in 1982 with his work on the Quadratic assignment problem. He has been working in this same university since 1984. His teaching and his research are focused in Operations Research, mainly in Discrete Optimization. He has worked specially in problems involving vehicle routing, and the results of this work have been published in the main journals of the area. His research interests include Discrete optimization, Integer Programming, Graph theory, vehicle routing and location problems.
Generating solutions to practical decision problems by dynamic programming
SPEAKER: Heligius Hendrix
PLACE: Building C5, Room C5016, Campus Nord, UPC (see map)DATE: Friday, September 21st 2012. Time: 12:30
Abstract: Dynamic programming focuses on the question when, in which situation to take which decision. In our experience it is not straightforward for students and researchers to grasp its concepts and to come to workable implementations. In this presentation we discuss its use for answering several practical questions from engineering and economics.
• How long should queues before traffic lights be in order to switch colour?
• When to release water in reservoir or lake management?
• When to refill the beer in your fridge?
• Is this similar for salad (perishable inventory products)?
• Which actions to take consecutively in an agro-logistics supply chain?
• How fast should the European Union revise fish quota?
• Does price variation influence deforestation in Latin America?
• Will pollution of several industries in Australia lead to closure of some?
We go through the steps and challenges to answer these questions via dynamic programming
The speaker: (Click here for more information)
Eligius M.Th. Hendrix is a researcher in optimisation methods with a so-called Ramon y Cajal contract at the University of Málaga and also associated to Wageningen University. In his teaching experience of 25 years he supervised about 100 Msc and various PhD theses. He is author of numerous articles in international journals and contributions to several books and national papers. His contributions range from questions on how to compute algorithms on modern platforms in an efficient way to game theoretic problems applied to agricultural and environmental science; agro-logistics, design of experiments, risk, water management, fodder industry etc. Most fundamental research questions deal with Global Optimisation, Robustness, Coalition Formation and Location problems, where he also organises workshops and writes books.
Locating Lottery Retail Stores in Spain
SPEAKER: Daniel Serra
PLACE: C5 Building, Room C5016, Campus Nord, UPC (see map)DATE: Friday, May 18th 2012. Time: 12:30
Abstract: A Lottery ticket is a very homogeneous good, with no price or product differentiation, and therefore the location of lottery outlets is a key factor in the success of the business. In Spain there are almost 10.000 retail stores that sell lottery. In this study we present a model to locate new stores so as to maximize customers' capture, but with the constraint of trying to minimize the impact on existing customers. Results on its implementation in Spain are presented.
Daniel Serra graduated in 1984 in Economics from the Autonomous University of Barcelona, and obtained a master in systems analysis and his PhD in the Whiting School of Engineering at Johns Hopkins University in 1989. He is actually professor of management at the Universitat Pompeu Fabra (UPF). His fields of specialization are logistics and quantitative methods in management. He has more than 30 publications in international journals, such as European Journal of O.R., Computers and O.R., Journal of the Operational Research Society, Network and Spatial Economics, Journal of Regional Science, Geographical Analysis, Papers in Regional Science, among others. He belongs to the editorial board of Geographical Analysis, International Journal of Regional Science, Supply Chain Practice, and International Journal of Operations Research and Information Systems. He is actually the director of the Business Analytics Research Group at UPF and vicerector for Economics, Information Systems and Institutional Relations.
for further information about Daniel Serra
Stochastic programming with mixed-integer variables.
SPEAKER: Maarten van der Vlerk
PLACE: C5 building, room C5016, Campus Nord, UPC (see map)
DATE: Wednesday, April 17th 2012. Time: 12:30
ABSTRACT: Stochastic programming studies models and solution methods to support decision making under uncertainty, thus aiming to explicitly cope with an important characteristic of many real world problems. Instead of assuming that future parameters are known, it is assumed that only probabilistic information is available at the time that decisions have to be made.
We will give an overview of some of the main models studied in stochastic programming. Of particular interest are models involving integer (binary) variables as required for modeling many practical problems. For example, deciding on the localtion of a distribution center could be modeled as an integer stochastic program. However, solving such models is challenging since they combine the difficulties met in both in stochastic and integer programming. Some recent developments in this active research area will be discussed.
The speaker: Maarten H. van der Vlerk is professor of Stochastic Optimization at the University of Groningen.
He is the director of the bachelor program on Econometrics and Operations Research and of the
master program on Econometrics, Operations Research and Actuarial Studies. His main research field is stochastic
integer programming on which he has been very active. Among other work, he has compiled and maintained
a bibliography containing over 4000 references on stochastic programming, he been the COSP chair and founded the
stoprog.org web site. Moreover, he has coauthored over 40 papers published in the most reputed journals.
Click here for more information about Maarten van der Vlerk
Global optimization strategies for detailed kinetic models in systems biology
SPEAKER: Albert Sorribas
PLACE: C5 building, room C5016, Campus Nord, UPC (see map)
DATE: Thursday, March 15th 2012. Time: 12:30
ABSTRACT: Design of newly engineered microbial strains for biotechnological purposes would greatly benefit from the development of realistic mathematical models for the processes one wants to optimize. With the development and application of appropriate optimization techniques, one could identify the modifications that need to be made to the organism in order to achieve the desired biotechnological goal. As appropriate models to perform such an analysis are necessarily non-linear and typically non-convex, finding their global optimum is a challenging task. Canonical modeling techniques, such as Generalized Mass Action (GMA) models based on the power-law formalism, offer a possible solution to this problem because they have a mathematical structure that enables the development of specific algorithms for global optimization.
Based on the GMA canonical representation, we have developed in previous works a highly efficient optimization algorithm and a set of related strategies for understanding the evolution of adaptive responses in cellular metabolism. Here, we explore the possibility of recasting kinetic non-linear models into an equivalent GMA model, so that global optimization on the recast GMA model can be performed. With this technique, optimization is greatly facilitated and the results are transposable to the original non-linear problem. This procedure is straightforward for a particular class of non-linear models known as Saturable and Cooperative (SC) models that extend the power-law formalism.
Our results show that recasting non-linear kinetic models into GMA models is indeed an appropriate strategy that helps overcoming some of the numerical difficulties that arise during the global optimization task.
- Pozo C, Marin-Sanguino A, Guillén-Gosalbez G, Jimenez L, Alves R, Sorribas A. Steady-state global optimization of non-linear dynamic models through recasting into power-law canonical models. (2011) BMC Systems Biology 5:137.
- Sorribas A, Pozo C, Vilaprinyo E, Guillén-Gosálbez G, Jimenez L, Alves R. Optimization and evolution in metabolic pathways: global optimization techniques in Generalized Mass Action models. Journal of Biotechnology 149(3):141-153
- Guillén-Gosálbez-G, Sorribas, A. Identifying quantitative operation principles in metabolic pathways: a systematic method for searching feasible enzyme activity patterns leading to cellular adaptive responses. BMC Bioinformatics 2009, 10:386.
click here for further information on Albert Sorribas' research.
El problema del cartero chino con beneficio máximo
SPEAKER: Ángel Corberán
PLACE: Edifici C5, Aula: C5015, Campus Nord, UPC (veure mapa)
DATE: Friday, January 27th 2012, Time: 12:30
ABSTRACT: El Problema del Cartero Chino con Beneficio Máximo (MBCPP) es un problema NP-difícil que considera varios beneficios asociados con cada arista de un grafo, uno por cada vez que la arista es atravesada realizando el servicio. El objetivo es encontrar un tour con beneficio máximo. El MBCPP tiene su aplicación en la resolución de problemas relacionados con la retirada de nieve de calles y carreteras. Proponemos una formulación como PLE del MBCPP definido sobre un grafo no dirigido y, basándonos en la descripción parcial que hemos obtenido de su poliedro asociado, proponemos un método de ramificación y acotación para su resolución. Presentaremos resultados computacionales en instancias con hasta 1000 vértices y 3000 aristas..
Ángel Corberán is Full Professor at the statistics and operations research department of Universitat de València. His research lies within the area of combinatorial optimization/discrete programming, mainly on problems that arise in distribution, transportation and vehicle routing. He has authored a great deal of papers, published in outstanding journals, related to the study of the above mentioned problems and the design and implementation of exact and approximate solution methods. He is associate editor of Computational Optimization and Applications, Computers & Operations Research and TOP.
click here for further information about Ángel Corberán.