An overview of advances in combinatorial optimization related topics

This volume of Optimization is devoted to the ECCO XXV Conference, that was held at the Green Palace Hotel in Antalya, Turkey from April 26 to April 28, 2012. The conference attracted nearly 200 delegates from across the OR community in European countries for a three-day meeting of lively discussions and debates. The conference focused on Combinatorial Optimization and on experiences in solving real-world problems, discussing recent advances in theory and applications, reporting on development and implementation of appropriate models and efficient solution methods for combinatorial optimization problems. The conference provided a forum for researchers and practitioners to promote their work on combinatorial optimization to the broader scientific community, identifying challenging research problems for the field, as well as promising research developments both in theory and applications, and promoting interactions with researchers in related research areas.

ECCO, the EURO Working Group on Combinatorial Optimization, was created in 1987 by Catherine Roucairol, Dominique de Werra, and Alexander Rinnooy Kan. Over the years, the group has provided an opportunity to discuss novelties in important areas of combinatorial optimization. The group, which has more than 1,200 members, is open to everybody interested in the field, either in theoretical aspects or in business, industry or public administration. During the first 10 years, Catherine Roucairol coordinated the ECCO activities. The current coordinator is Silvano Martello. The ECCO conferences are held once a year during Spring, and are devoted to all aspects of combinatorial optimization. The meetings are usually attended by about 100 participants, and nicely combine the presentation of scientific works and the exchange of new ideas with an exciting atmosphere. Other gatherings were held in Paris (May 1988), Venice (June 1989), Barcelona (May 1990), Dubrovnik (May 1991, cancelled), Graz (April 1992), Bruxelles (April 1993), Milano (February 1994), Poznan (May 1995), Dublin (April 1996), Tenerife (May 1997), Copenhagen (May 1998), Bendor (May 1999), Capri (May 2000), Bonn (May–June 2001), Lugano (May–June 2002), Molde (June 2003), Beirut (June 2004), Minsk (May 2005), Porto (May 2006), Cyprus (May 2007), Dubrovnik (May 2008), Jerusalem (May 2009), Málaga (May 2010), Amsterdam (May–June 2011), Antalya (April 2012), and Paris (May–June 2013). The next ECCO Conference will be held in Munich in May 2014. In many cases a volume or a special issue of a major international journal is devoted to a peer reviewed selection of the presented papers: in recent years special issues have been edited by Martello and Pesch [1], Gambardella and Martello [2], Hasle et al. [3], Kovalyov and Martello [4], Martello and Vladimirou [5], Blazewicz et al. [6], and Escudero et al. [7].

The organization of the ECCO XXV 2012 conference was a joint responsibility of Professors Silvano Martello – coordinator of European Chapter on Combinatorial Optimization, Gerhard-Wilhelm Weber – a member of the Middle East Technical University, Refail Kasımbeyli – a member of the Anadolu University, and Arslan Örnek – a member of Izmir University of Economics.

The group from Izmir deserves a particular recognition for its devotion to making the organization possible. A cordial thank goes to the company of Dr. Arber, Ankara, that guided and supported the conference professionally and fruitfully, and to all the sponsors and collaborating institutions.The Organizing Committee included:Gerhard-Wilhelm Weber (Co-Chair), Middle East Technical University, Turkey,Refail Kasimbeyli (Co-Chair), Anadolu University, Turkey,Arslan Örnek (Co-Chair), Izmir University of Economics, Turkey,Ugur Eliiyi, Izmir University of Economics, Turkey,Deniz Türsel Eliiyi, Izmir University of Economics, Turkey,Zeynep Alparslan Gök, Süleyman Demirel University, Turkey,Sinan Gürel, Middle East Technical University, Turkey,Erdinç Öner, Izmir University of Economics, Turkey,Özgür Özpeynirci, Izmir University of Economics, Turkey,Selin Özpeynirci, Izmir University of Economics, Turkey,Basak Akteke Öztürk, Middle East Technical University, Turkey,Zeynep Sargut, Izmir University of Economics, Turkey,Yesim Aydin Son, Middle East Technical University, Turkey,Ahmet Tokgözlü, Süleyman Demirel University, Turkey,Gürkan Üstünkar, Vestel Corporation, Turkey,Kasirga Yildirak, Middle East Technical University, Turkey,The Programme Committee included:Gerhard Wilhelm Weber (Co-Chair), Middle East Technical University, Turkey,Refail Kasimbeyli (Co-Chair), Anadolu University, Turkey,Jacek Blazewicz, Poznan University of Technology, Poland,Domingos Moreira Cardoso, University of Aveiro, Portugal,Van-Dat Cung, Grenoble INP, France,Alain Hertz, Ecole Polytechnique Montréal, Canada,Silvano Martello, University of Bologna, Italy,Xiaoling Sun, Fudan University, China,Paolo Toth, University of Bologna, Italy.

During the conference three plenary lectures were delivered:

• Professor Miguel Anjos (Mathematics and Industrial Engineering and Gerad, Ecole Polytechnique de Montréal, Montréal, Quebec, Canada) lectured on the relationship between semidefinite optimization and combinatorial optimization.

• Professor Bernard Ries (Lamsade, Université Paris-Dauphine, Paris, France) discussed on why some vertices/edges are more important than others.

• Professor John Shawe-Taylor (Department of Computer Science, University College, London, United Kingdom) talked on adapting representations for specific tasks by machine learning in Operations Research.

The conference became a special and unforgettable experience also because of two sightseeing tours: one to the ancient cities of Aspendos and Perge, near modern Antalya, and the other to the Old City of Antalya. In fact, many scientists and citizens, in general, from all of Europe do have a particular affinity to the fascinating and vibrating region of Antalya, which is among the most important travel and touristic destinations in the world. For further impressions we refer to the reports [18, 19].

Sponsors for the meeting were Gurobi Optimization, BoyPlast, PASCAL2 and NKD Group Inc.

Topics of interest were applications of combinatorial optimization in logistics and supply chain management, manufacturing, energy production and distribution, telecommunications, bioinformatics, finance, discrete and hybrid dynamical systems, and other fields, exact solution algorithms, approximation algorithms, heuristics, and metaheuristics for combinatorial optimization problems, graph theory and network flows, integer programming, global optimization, stochastic integer programming, and multiobjective programming.

This special issue of Optimization is devoted to the presentation of a selection of the presented papers. After a thorough peer review process, seven papers have been accepted for publication. We are indebted to many anonymous referees for their assistance during the reviewing process.

Zeynep Alparslan Gök and Gerhard-Wilhelm Weber discuss the allocation problem of rewards or costs, a central question for individuals and organizations contemplating cooperation under uncertainty. Involving of uncertainty into cooperative games is motivated by the real world where noise in observation and experimental design, incomplete information and further vagueness in preference structures and decision making play an important role. The theory of cooperative ellipsoidal games provides a new game theoretical angle and suitable tools for answering this question. The authors introduce and study some solution concepts using ellipsoids, namely the ellipsoidal imputation set, the ellipsoidal dominance core and the ellipsoidal stable sets for cooperative ellipsoidal games.

Sergey Astrakov and Adil Erzin consider models for monitoring a band with a preset width using sensor networks shaped as disc covers. Every cover disc is a centered sensor operation area. The researchers determine a minimum-density band cover with the discs of one, two and three radii. The specific requirement for the cover is that the disc centers shall not be inside the band (external monitoring). Various efficient covers models are proposed and their characteristics are determined.

Maria do Céu Marquesa and Joana Matos Dias extend the simple dynamic facility location problem to uncertain realizations of the potential locations. A finite and discrete scenario set is regarded, and it has to be decided when to locate the facilities and how to assign the customers over the entire planning horizon, under every scenario, to minimize the expected total costs. Location decisions have to take into consideration all possible scenarios and cannot be changed for each one specially. For this problem, the authors suggest a mixed LP formulation and introduce a primal-dual heuristic solution method. The heuristic was tested for a set of randomly generated test problems; computational results are given.

Adil Erzin and Sergey Astrakov study the construction of regular minimum-density plane coverings with ellipses of one, two and three types. This problem is relevant, for example, to power-efficient surface sensing by autonomous above-grade sensors. A similar problem, for which disks are used to cover a planar region, has been well studied. On the one hand, the use of ellipses generalizes a mathematical problem; on the other hand, it is necessary to solve these types of problems in real applications of wireless sensor networks. Their work extends some previous results and offers new regular covers that use a small number of ellipses to cover each regular polygon.

Imdat Kara, Özge Nimet Koc, Fulya Altıparmak and Berna Dengiz study one of the variants of the traveling salesman problem, called “Traveling Salesman Problem with Time Windows (TSPTW)”. In this problem, each city (nodes, customers) must be visited within a time window defined by earliest and latest time. The authors propose a new integer linear programming formulation having O(n2) binary variables and O(n2) constraints, where (n) equals the number of nodes of the underlying graph. The performances of the proposed and existing formulations are analyzed with respect to linear programming relaxations and CPU times. They showed that the new formulation considerably outperforms the existing one with respect to both performance criteria.

Krzysztof Ocetkiewicz considers a problem of scheduling deteriorating jobs on a single processor when the processing time of each job is given by a function of its starting time. The jobs are non-preemptive and independent, and there are neither ready times nor deadlines. The goal is to minimize the total weighted completion time. The author shows how to employ the concept of non-dominated schedules to construct an exact algorithm for the problem. Extension of the algorithm to solve problems with precedence constraints and to find all Pareto-optimal solutions are considered.

Fehmi Burcin Ozsoydan and Aydin Sipahioglu consider the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is an extension of the well-known Capacitated Vehicle Routing Problem. In this problem the objective is a minimization of sum of arrival times at nodes instead of minimizing the total tour cost. This type of routing problem arises when a priority is given to customer needs or dispatching vital goods supply after a natural disaster. The paper focuses on comparing the performances of neighborhood and population based approaches for the new problem CCVRP. Genetic Algorithm (GA), an evolutionary algorithm using Particle Swarm Optimization mechanism with GA operators, and Tabu Search are compared in terms of required CPU time and obtained objective values. In addition, a nearest neighborhood based initial solution technique is also proposed in the paper. We refer to [14–17] for further special issues in the journal Optimization supervised by us and our colleagues. The works [8–13] highlight several related editorial and research contributions by some of us.

Silvano Martello
DEI “Guglielmo Marconi”, University of Bologna, Bologna, Italy[email protected]
Gerhard-Wilhelm Weber
Institute of Applied Mathematics, Middle East Technical University, Ankara, Turkey[email protected]
Refail Kasimbeyli
Department of Industrial Engineering, Anadolu University, Eskişehir, Turkey[email protected]

Acknowledgements

We are very grateful to the Editor-in-Chief of Optimization, Prof. Christiane Tammer (Martin Luther University, Halle-Wittenberg, Germany), for her interest, confidence and continuous support at all stages of the preparation of this special issue. Furthermore, we convey many thanks to the Managing Editor of Optimization, Prof. Andreas Löhne from the same university, for his excellent guidance and collaboration during all the review and communication processes related with the submissions, and during the gradual development of this entire special issue. Finally, we extend our heartfelt thanks to previous Editor-in-Chief of Optimization, Prof. Juan Enrique Martinez-Legaz, and to previous Managing Editor of Optimization, Prof. Rosalind Elster, who were with us at the very beginning of this special issue project and its approval.

We guest editors wish all readers a pleasant and entertaining, insightful and inspiring study of the contributions of this Optimization special issue. Indeed, we cordially hope that our special issue will represent Optimization as a premium journal of science which strongly supports Optimization and Operations Research all over Europe and around the world.