Optimization by Unconventional Ant Algorithms
Nicolas Zufferey, University of Geneva, Switzerland
A Robust Approach to Solve Mixed Integer Linear Optimization Problems with Uncertain Data
Marie-Christine Costa, ENSTA - ParisTech, France
Applications and Formulations of the Travelling Salesman Problem
Paul Williams, Independent Researcher, United Kingdom
Optimization by Unconventional Ant Algorithms
Nicolas Zufferey
University of Geneva
Switzerland
![]()
Brief Bio
Nicolas Zufferey is a full professor of operations management at the University of Geneva in Switzerland. His research activities are focused on designing metaheuristics for difficult and large combinatorial optimization problems, with applications mainly in transportation, scheduling, production, inventory management, network design, and telecommunications. He received his BSc and MSc degrees in Mathematics at EPFL (the Swiss Federal Institute of Technology in Lausanne), as well as his PhD degree in operations research (2002). He was then successively a post-doctoral trainee at the University of Calgary (2003 – 2004) and an assistant professor at Laval University (2004 – 2007). He is the (co)author of more than 70 publications (papers in professional journals, proceedings of conferences, and book chapters) and has reviewed papers for 35 international journals. With above 30 coauthors, he has had research activities with 18 Universities in Europe and North America, as well as with 11 private companies.
Abstract
Ant algorithms are well-known metaheuristics which have been widely studied since two decades. The recent evolution of such methods could be roughly characterized with the following sentence: “Ant colony optimization: from cumbersome and inefficient constructive algorithms to aggressive powerful techniques”.
In classical ant algorithms, the role of each ant is to build a solution in a constructive way, where each decision is based on a tradeoff between the greedy force and the trail system. The greedy force (also called visibility or heuristic information) represents the self-adaptation ability of an ant. The trail system represents the collaboration ability of the ants: it is usually a central memory containing relevant information on the history of the search process.
Other types of ant algorithms have recently emerged out of the common framework of the constructive ant algorithms. On the one hand, different roles are designed for each individual ant, ranging from a negligible help in the decision process to a refined local search method. On the other hand, different ways to select a decision are proposed, which outperform the standard tradeoff between the greedy force and the trail system.
The goal of this talk is to classify and benchmark the unconventional ant algorithms, as well as to highlight their successful elements. Numerical experiments will be presented for problems in the following fields: graph coloring, production scheduling, and network design. Moreover, various criteria (e.g., quality, speed, robustness, ease of adaptation, ability to take advantage of the problem structure) will be used to measure the performance of the methods.
A Robust Approach to Solve Mixed Integer Linear Optimization Problems with Uncertain Data
Marie-Christine Costa
ENSTA - ParisTech
France
Brief Bio
Marie-Christine Costa is a Professor of Operations Research at ENSTA Paris-Tech, University of Paris-Saclay, France. She works with the team Combinatorial Optimization of the CEDRIC laboratory from the Conservatoire National des Arts et Métiers in Paris where she has taught for many years. She was secretary and then president of the French operational research society ROADEF from 2002 to 2005 and she belongs to the scientific council of Gaspard Monge Program for Optimization and operations research (PGMO), launched by EDF and the Jacques Hadamard Mathematical Foundation. She is a regular visiting professor at EPFL (the Swiss Federal Institute of Technology in Lausanne). She is at the head of the Master Parisien de Recherche Opérationnelle which groups six French graduate schools of engineering with the support of twelve large companies. She received her PHD in Computer Science-Operations Research from University Pierre et Marie Curie (Paris) in 1980 and her HDR from University Paris Nord in 1994. Her current research interests are in two directions. The first one is graph optimization, such as integer multi-flow problems or the search for blockers and transversals of optimal solutions of some combinatorial optimization problems. The second one is mixed-integer programming problems taking into account uncertain data, with an application to the design of hybrid energy parks. She also worked for seven years in collaboration with the telecommunication French company Orange for optimizing the deployment of optical networks.
Abstract
The ever growing performances of mathematical programming solvers allows to be thinking of solving more and more complex problems, and in particular, optimization problems with uncertain data. Here we suppose that the decision-maker makes decisions in two stages: first before discovering the actual value taken by the data, second once uncertainty has been revealed. This second part is called the recourse problem. Two-stage stochastic linear programming is often used in this case but it requires knowing the underlying probability distribution of the data, which is not available in many cases. We present a robust approach that relies only on mild assumptions on the uncertainties involved in the problem, as bounds or reference values of the uncertain data. It looks for a solution that remains satisfactory for all realizations of the data, i.e. for worst scenarios. We first study a general theoretical model with mixed integer decision variables and continuous recourse variables. Then we show that the approach can be generalized, even when the full recourse property is not verified, that is when the problem can have no solution for some values of the first stage decision variables. We finally present two applications: the design of a hybrid energy park for which the recourse variables are continuous, and the design of a telecommunication optical network for which the recourse variables are integer.
Applications and Formulations of the Travelling Salesman Problem
Paul Williams
Independent Researcher
United Kingdom
![]()
Brief Bio
H.P (Paul) Williams is Emeritus Professor of Operational Research at the London School of Economics. After graduating from Cambridge University with a degree in Mathematics he did a PhD in Mathematical Logic. Then he worked for IBM. Following this he has held chairs in three leading UK universities He has published many papers, mainly in Mathematical Programming, and is a recipient of the Beale Medal of the UK Operational Research Society.Paul Williams’ work has mainly been in Linear and Integer Programming. He was one of the first people to put modelling, in these areas, on a systematic footing. He is well known for his publications including two of his books: ‘Model Building in Mathematical Programming’ (first published in 1978 and now in a 5th edition) and ‘Logic and Integer Programming’. His current research is primarily in Integer Programming covering modelling, applications and theory. In particular he is using Projection as a method of creating a theoretically satisfactory Dual of an Integer Programme. This would have Mathematical, Computational and Economic implications eg an analogue of pricing for discrete decision making such as allocating fixed costs. In his spare time Professor Williams is attempting to walk around the 7,000 mile coastline of mainland Britain, in stages. So far he has covered about half the coastline.
Abstract
The Travelling Salesman Problem (TSP) is well known because of its ease of stating but difficulty of solving.
This talk will describe applications of the TSP, including some more unusual ones, and outline the state-of-the-art with regard to their solution. Then a number of alternative formulations of the (asymmetric) TSP as an Integer Programme (IP) will be described. It will be shown (surprisingly) that these formulations can be ranked (independently of problem instance) in order of the strength of their Linear Programming Relaxations (ie the optimal objective value when the integrality condition is ignored).
Some computational experience will be given of the different formulations on a small problem.