ISCO 2012

ISCO is a new biannual symposium with its first issue held in Hammamet, Tunisia in March 2010. The symposium aims to bring together researchers from all the communities related to combinatorial optimization, including algorithms and complexity, mathematical programming and operations research. It is intended to be a forum for presenting original research in these areas and especially in their intersections. Quality papers on all aspects of combinatorial optimization, from mathematical foundations and theory of algorithms to computational studies and practical applications, are solicited.

ISCO 2012 will be preceded by a spring school on "Mathematical Programming and Design of Approximation Algorithms". David Shmoys and David Williamson will give 16 hours of lectures on April 17-18, 2012.

Submissions deadline: December 1, 2011 December 8, 2011, 11:59 UTC -11 time
Notification of authors: January 30, 2012
Early registration deadline: February 24, 2012
Spring School: April 17-18, 2012
Conference: April 19-21, 2012
Camera ready version: May 4, 2012

Giorgio Ausiello, Università di Roma "La Sapienza"
Hyperpaths in directed hypergraphs: Properties and algorithms

Abstract: Directed hypergraphs are a natural generalization of digraphs and are a combinatorial model that turns out to be useful in several application domains (databases, logic, artificial intelligence etc.). Although in general the computation of shortest hyperpaths in directed hypergraphs is an NP-hard problem, for suitable cost measures such problem becomes tractable. In this paper, after discussing the structural properties of hyperpaths (with particular attention to the role of cycles in hyperpaths and to canonic form of hyperpaths), we present a taxonomy of hyperpath cost functions and we study the relationships between the classes of cost functions on hyperpaths and the structure of the corresponding optimal hyperpaths. Finally we illustrate for what classes in the taxonomy shortest hyperpaths can be computed in polynomial time.

George Nemhauser, Georgia Tech
Branch-and-Price Guided Search

Abstract: We present an approach for structured integer programs that solves well-chosen restrictions of the problem to produce high-quality solutions quickly. Column generation is used both for automatically generating the restrictions and for producing bounds on the value of an optimal solution. We present computational experience for fixed-charge multi-commodity flow and inventory routing problems.

Christos Papadimitriou, UC Berkeley
Computational Insights and the Theory of Evolution

Abstract: I shall discuss recent work (much of it joint with biologists Adi Livnat and Marcus Feldman) on some central problems in Evolution that was inspired and informed by computational ideas. Considerations about the performance of genetic algorithms led to a novel theory on the role of sex in Evolution based on the concept of mixability. And a natural random process on Boolean functions can help us understand better Waddington’s genetic assimilation phenomenon, in which an acquired trait becomes genetic.

Paolo Toth, Università di Bologna
Models and Algorithms for the Train Unit Assignment Problem

Abstract: Passenger railway systems are highly complex systems requiring the solution of several planning problems that can be analyzed and solved through the application of mathematical models and optimization techniques, which generally lead to an improvement in the performance of the system, and also to a reduction in the time required for solving these problems.
The planning process is generally divided into several phases: Line Planning, Train Timetabling, Train Platforming, Rolling Stock Circulation and Crew Planning. In this lecture, after a description of the whole planning process and of its main phases, the Train-Unit Assignment Problem, an important NP-hard problem arising in the Rolling Stock Circulation phase, is considered in detail.
In the Train-Unit Assignment Problem (TUAV), we are given a set of timetabled trips, each with a required number of passenger seats, and a set of different train units, each having a cost and consisting of a self-contained train with an engine and a set of wagons with a given number of available seats. TUAV calls for the minimum cost assignment of the train units to the trips, possibly combining more than one train unit for a given trip, so as to fulfil the seat requests.
Two Integer Linear Programming (ILP) formulations of TUAV are presented, and valid inequalities are introduced for strengthening the corresponding Linear Programming (LP) relaxation. Additional relaxations, based on the Lagrangian approach and on the solution of a restricted problem associated with a peak period (i.e., with a subset of simultaneous trips that must be assigned to distinct train units), are considered for the effective computation of tight lower bounds. Constructive heuristic algorithms, based on the previously considered relaxations, are proposed, and their solutions are improved by applying local search procedures.
Extensive computational results on real-world instances are reported, showing the effectiveness of the proposed bounding procedures and heuristic algorithms.

Mourad Baïou, Université Blaise Pascal, Clermont-Ferrand
Evripidis Bampis, Université Pierre et Marie Curie
Francisco Barahona, IBM T.J. Watson, New York
Walid Ben-Ameur, TELECOM SudParis
Jaroslaw Byrka, University of Wrocław
William Cook, Georgia Tech
Gerard Cornuéjols, CMU
Federico Della Croce, Politecnico di Torino
Josep Diaz, Universitat Politecnica de Catalunya
Bruno Escoffier, Université Paris Dauphine
Satoru Fujishige, Kyoto University
Eric Gourdin, Orange Labs, Paris
Luis Gouveia, University of Lisbon
Anupam Gupta, CMU
Mohamed Haouari, INSAT, Tunis
Brahim Hnich, Izmir University of Economics
Klaus Jansen, Christian-Albrechts-Universität, Kiel
Stavros Kolliopoulos, NKUA, Athens
Jochen Könemann, University of Waterloo
Andrea Lodi, Università di Bologna
Nelson Maculan, Universidade Federal do Rio de Janeiro
A. Ridha Mahjoub, Université Paris Dauphine (co-chair)
Alberto Marchetti-Spaccamela, Università di Roma "La Sapienza"
Vangelis Markakis, AUEB, Athens
Tom McCormick, University of British Columbia
Ioannis Milis, AUEB, Athens (co-chair)
Jérôme Monnot, Université Paris Dauphine
Vangelis Paschos, Université Paris Dauphine
Gerhard Reinelt, Universität Heidelberg
Giovanni Rinaldi, IASI-CNR, Roma
Amin Saberi, Stanford University
François Vanderbeck, Université Bordeaux 1
Peter Widmayer, ETH, Zürich
Gerhard Woeginger, Eindhoven University of Technology
Hande Yaman, Bilkent University, Ankara
Vassilis Zissimopoulos, NKUA, Athens

The submission deadline is Thursday December 8, 2011, 11:59 UTC -11 time.

Paper submission will be handled via Easy Chair.

Papers presenting original unpublished results in all areas of combinatorial optimization and its applications are welcome.

Topics of interest include, but are not limited to:

• Approximation algorithms
• Branch-and-bound algorithms
• Branch-and-cut-and-price algorithms
• Computational biology
• Computational complexity
• Computational geometry
• Constraint Programming
• Cutting plane algorithms
• Exact and parameterized algorithms
• Graph and network algorithms
• Interior point methods
• Linear and nonlinear integer programming
• Local search algorithms
• Metaheuristics
• On-line algorithms
• Polyhedral combinatorics
• Randomized algorithms
• Scheduling algorithms

There will be two types of submissions:

a) Regular papers

They should be of at most 12 pages, including front matter and bibliography, in LNCS style. Proofs omitted due to space constraints should be included in a clearly marked appendix which will be taken into account by the program committee members and the reviewers, but it will not be published in the proceedings. Simultaneous submissions to other conferences with published proceedings or journals are not allowed.

Accepted regular papers will be published by Springer-Verlag in the Lecture Notes in Computer Science (LNCS) series in a post-conference proceedings volume. The authors will have to prepare their camera-ready version two weeks after the end of ISCO 2012.

b) Short papers

They should be of at most 4 pages (including front matter and bibliography) with no optional appendix. Accepted short papers will be included in a volume of local proceedings.

The following Special Issues of International Journals will be associated with ISCO 2102:

• A special issue of Mathematical Programming Series B on "Combinatorial Optimization". See here for the CFP for this issue.
• A special issue of Theoretical Computer Science on "Combinatorial Optimization: Theory of algorithms and complexity". See here for the CFP for this issue.
• A special issue of RAIRO-Operations Research on "Combinatorial Optimization". See here for the CFP for this issue.

To be published in the LNCS post-conference proceedings volume.
(37 out of 94, acceptance rate 39.4%)

• Cid C. De Souza and Breno Piva.
  The Minimum Stabbing Triangulation Problem: IP Models and Computational Evaluation
• Matteo Fischetti and Leo Liberti
  Orbital shrinking
• Laura Galli, Konstantinos Kaparis and Adam Letchford
  Gap Inequalities for the Max-Cut Problem: a Cutting-Plane Algorithm
• Trivikram Dokka, Ioannis Mourtos and Frits Spieksma
  Fast Separation Algorithms for Three-Index Assignment problems
• Yuri Faenza, Samuel Fiorini, Roland Grappe and Hans Raj Tiwary
  Extended formulations, non-negative factorizations, and randomized communication protocols
• Gábor Braun and Sebastian Pokutta
  An algebraic approach to symmetric extended formulations
• Alexandre Freire, Vicente Acuna, Pierluigi Crescenzi, Carlos Ferreira, Vincent Lacroix, Paulo Vieira Milreu, Eduardo Moreno and Marie-France Sagot
  Minimum ratio cover of matrix columns by extreme rays of its induced cone
• Gabriela Argiroffo, Graciela Nasini and Pablo Torres
  The Packing Coloring Problem for (q,q-4) graphs
• Leonardo Martinez and Alexandre Cunha
  A Parallel Lagrangian Relaxation Algorithm for the Min-Degree Constrained Minimum Spanning Tree Problem
• Sophie Toulouse
  Differential Approximation of the Multiple Stacks TSP
• Yuichi Asahiro, Jesper Jansson, Eiji Miyano and Hirotaka Ono
  Graph Orientations Optimizing the Number of Light or Heavy Vertices
• James Ostrowski
  Using Symmetry to Optimize Over the Sherali-Adams Relaxation
• Luis Gouveia, Markus Leitner and Ivana Ljubic
  On the Hop Constrained Steiner Tree Problem with multiple Root Nodes
• Satoru Fujishige and Jens Massberg
  Dual Consistent Systems of Linear Inequalities and Cardinality Constrained Polytopes
• Agostinho Agra, Marielle Christiansen, Rosa Figueiredo, Lars Magnus Hvattum, Michael Poss and Cristina Requejo
  Layered Formulation for the Robust Vehicle Routing Problem with Time Windows
• Monique Laurent and Antonios Varvitsiotis
  The Gram dimension of a graph
• Jianqiang Cheng, Celine Gicquel and Abdel Lisser
  A second-order Cone programming approximation to joint chance-constrained linear Programs
• Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau and Jean-Claude König
  Sum-Max Graph Partitioning Problem
• Eduardo Álvarez-Miranda, Valentina Cacchiani, Tim Dorneth, Michael Jünger, Frauke Liers, Andrea Lodi, Tiziano Parriani and Daniel R. Schmidt
  Models and Algorithms for Robust Network Design with Several Traffic Scenarios
• Fabio Furini, Carlo Alfredo Persiani and Paolo Toth
  Aircraft sequencing problems via a rolling horizon algorithm
• Manuel Sorge, Hannes Moser, Rolf Niedermeier and Mathias Weller
  Exploiting a Hypergraph Model for Finding Golomb Rulers
• Pierre Fouilhoux and Aurélien Questel
  The Non-Disjoint m-Ring-Star Problem : polyhedral results and SDH/SONET network design
• Monaldo Mastrolilli and Georgios Stamoulis
  Constrained Matching Problems in Bipartite Graphs
• Anna Huber and Vladimir Kolmogorov
  Towards Minimizing k-Submodular Functions
• Pierre Bonami, Viet Hung Nguyen, Michel Klein and Michel Minoux
  On the Solution of a Graph Partitioning Problem under Capacity Constraints
• Marie-Emilie Voge and François Clautiaux
  Theoretical investigation of aggregation in pseudo-polynomial network-flow models
• Mario Ruthmair and Günther Raidl
  On Solving the Rooted Delay- and Delay-Variation-Constrained Steiner Tree Problem
• Rafael Schouery and Cristina Fernandes
  Second-Price Ad Auctions with Binary Bids and Markets with Good Competition
• Agnes Gorge, Abdel Lisser and Riadh Zorgati
  Semidefinite Relaxations for Mixed 0-1 Second-Order Cone Program
• Sylvie Borne, Roland Grappe and Mathieu Lacroix
  The Uncapacitated Asymmetric Traveling Salesman Problem with Multiple Stacks
• Marc Demange, Jérôme Monnot, Petrica Pop and Bernard Ries
  Selective Graph Coloring in Some Special Classes of Graphs
• Tommy Färnqvist
  Counting Homomorphisms via Hypergraph-based Structural Restrictions
• Konstantinos Papalamprou and Leonidas Pitsoulis
  Recognition algorithms for binary signed-graphic matroids
• Bo Xiong and Christine Chung
  Completion Time Scheduling and the WSRPT Algorithm
• Mikhail Kovalyov, Ammar Oulamara and Ameur Soukhal
  Two agent scheduling on a serial batching machine
• Dennis Weyland, Roberto Montemanni and Luca Maria Gambardella
  Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines
• Mathieu Lacroix, Ridha Mahjoub and Sebastien Martin
  Polyhedral Analysis and Branch-and-Cut for the Structural Analysis Problem

• Céline Gicquel, Abdel Lisser and Michel Minoux.
  Tight lower bounds by semidefinite relaxation for a lot-sizing problem with sequence-dependent changeover costs
• Bendotti Pascale, Pierre Fouilhoux and Podkanski Karol.
  Permutation Problem using a Unit-Capacity Robot : Feasibility Recovery and Cutting-plane based Formulation with MTZ strengthening
• Alain Billionnet, Fethi Jarray, Ghassen Tlig and Ezzedine Zagrouba.
  Combining simulated annealing and linear programming approaches for reconstructing hv-convex colored images
• Michaël Gabay, Gerd Finke and Nadia Brauner.
  Identical coupled task scheduling problem: the finite case
• Hipolito Hernandez Perez and Juan Jose Salazar Gonzalez.
  Solving the multi-commodity many-to-many Pickup-and-Delivery Traveling Salesman Problem
• Luis Gouveia and Juan Jose Salazar.
  Polynomial Separation of the Enhanced Reverse Multistar Inequalities
• Irène Charon and Olivier Hudry.
  A branch and bound method for the aggregation of symmetric relations
• Tolga Bektas and Luis Gouveia.
  A polyhedral approach for generalizing the Miller-Tucker-Zemlin subtour elimination constraints for routing problems
• Alexandre Cunha.
  Algorithms for the Multi-period Degree Constrained Minimum Spanning Tree Problem
• Mette Gamst.
  A route-based decomposition for the Multi-Commodity k-splittable Maximum Flow Problem
• Stefan Gollowitzer, Bernard Gendron and Ivana Ljubic.
  Capacitated Network Design with Facility Location
• Nicolas Dupin.
  A 2-stage robust optimization model for planning nuclear maintenances with uncertain maintenance durations
• Monaldo Mastrolilli and Georgios Stamoulis.
  Restricted Max-Min Fair Allocation with Inclusion-free Intervals
• Miriam Kießling, Sascha Kurz and Jörg Rambau.
  An exact column-generation approach for the lot-type design problem
• Valeria Leoni, Erica Hinrichsen and María Patricia Dobson.
  Generalized Limited packings of P4-tidy graphs
• Walid Ben-Ameur, Pierre Bauguion and Eric Gourdin.
  An efficient tree-based model for multicommodity flow problems
• Eric Gourdin and Yuhui Wang.
  Bottleneck and Maxmin Transportation Problems with Degree Constraints
• Fabio Salassa, Wim Vancroonenburg, Tony Wauters, Federico Della Croce and Greet Vanden Berghe.
  Matheuristics for the Eternity II puzzle
• Didem Gözüpek, Mordechai Shalom, Ariella Voloshin and Shmuel Zaks.
  On the Complexity of Constructing Minimum Reload Cost Path-Trees
• Roland Grappe.
  Polynomial cases of hypergraph local edge-connectivity augmentation
• Houssein Alaeddine, Emmanuel Neron, Kamal Serrhini and Mindjid Maizia.
  Planning for evacuation
• Rafaelli Coutinho, Lúcia Drummond, Yuri Frota, Luidi Simonetti and Eduardo Uchoa.
  A Distributed Transportation Simplex Applied to a Content Distribution Network Problem
• Pierre Fouilhoux.
  Clique-branching formulation for the vertex coloring problem
• Laurent Alfandari, Anass Nagih, Agnès Plateau and Jalila Sadki.
  Generalizations of Dobson approximation algorithm and cooperation with Column Generation for large-size Covering Integer Programs
• Pierre Le Bodic and Cédric Bentz.
  On the complexity of Partial Colored Multiterminal Cut problems
• Eduardo Álvarez-Miranda, Ivana Ljubic, S. Raghavan and Paolo Toth.
  The Recoverable Robust Two-Level Network Design Problem
• Sophie Toulouse, Jean-François Culus and Roupin Frédéric.
  DIFFERENTIAL APPROXIMATION OF SNP OPTIMIZATION PROBLEMS
• Denis Cornaz, Herve Kerivin and Ridha Mahjoub.
  A combinatorial linearization of the quadratic acyclic vertex-induced subgraph problem
• Mourad Baiou and Francisco Barahona.
  The classical facility location polytope for graphs with no g-odd Y-cycle
• Amal Benhamiche, Ridha Mahjoub, Nancy Perrot and Eduardo Uchoa.
  A Branch-and-Price Algorithm for the Optical Multi-Band Network Design Problem
• Hassene Aissi and A. Ridha Mahjoub.
  On the constrained minimum s − t cut problem

To download the program in pdf, click here.

"Mathematical Programming and Design of Approximation Algorithms"
by
David Shmoys and David Williamson

The material for the course will be drawn from our recent book The Design of Approximation Algorithms (DAA), and be augmented by several recent papers. We list below the topics of the course, the associated sections of the book and the related additional papers (though the papers cited in these book sections might also be covered more completely than in the text). The list below is probably somewhat too ambitious for the allotted time.

The uncapacitated facility location problem

• Deterministic (DAA 4.5) and randomized rounding (DAA 5.8, DAA 12.1), primal-dual method (DAA 7.6) and local search (DAA 9.1)

and the k-median problem

• Lagrangean relaxation (DAA 7.7) and local search (DAA 9.2)

The traveling salesman problem

• Greedy algorithms (DAA 2.4)
• L. A. Wolsey, Heuristic analysis, linear programming and branch and bound, In Combinatorial Optimization II, volume 13, Mathematical Programming Studies, pages 121-134. Springer, 1980
• T. Mömke and O. Svensson, Approximating graphic TSP by matchings, Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 560-569, 2011
• M. Mucha, 13/9-approximation for the graphic TSP, to appear in Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), 2012
• H.-C. An, R. Kleinberg, and D. Shmoys, Improving Christofides’ Algorithm for the s-t path TSP, to appear in Proceedings of the 44th Annual ACM Symposium on Theory of Computing
• F. Schalekamp, D. Williamson, A. van Zuylen, A proof of the Boyd-Carr conjecture, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1477-1486, 2012

The Steiner tree problem (primal-dual method, DAA 7.4) and the generalized Steiner tree problem (randomized rounding, DAA 12.3)

The bounded-degree minimum spanning tree problem (deterministic rounding, DAA 11.2)

The minimum-cost knapsack problem (primal-dual method, DAA 7.5)

The prize-collecting Steiner tree problem

• Deterministic rounding (DAA 4.4), randomized rounding (DAA 5.7) and primal-dual method (DAA 14.1)

and the prize-collecting TSP

• M. X. Goemans, Combining approximation algorithms for the prize-collecting TSP

"Mathematical Programming and Design of Approximation Algorithms"
by
David Shmoys and David Williamson

To register click here (you will be redirected to our bank page for ISCO 2012 registration).

Registration Fees

For lunch (near AUEB) and dinner (in Athens) options click here.

How to reach your hotel from the airport

There are various options to reach the downtown hotels depending on whether you want to use public transportation or taxi.
By public transport: The blue metro line goes all the way from the airport to downtown and passes through the Syndagma metro station (where you can connect with the red line) and the Monastiraki metro station (where you can connect with the green line that goes towards AUEB). Please do not confuse the metro line with the suburban railway system, which departs from the adjacent platform and is not convenient for going downtown. The metro line takes about 35-40 minutes to Syndagma and the ticket from the airport costs 8 euros (note that a regular metro ticket costs only 1.40 as long as you use it within the city, it is only for the airport that costs 8 euros). The metro operates from 5:30 am till around midnight. Within the city it runs pretty frequently but the departures to/from the airport are only every 30 minutes (normally at 5 and 35 past every hour).
Apart from the metro, and especially if you arrive late, you can also take the bus X95 which also goes to Syndagma square. The bus departs every 15 minutes and the ticket costs 5 euros.
By taxi: During the day there is now a standard rate of 35 euros to the city center from the airport. If you arrive past midnight, the tariff is 50 euros.

How to come to the conference venue

The conference will take place in the main building of AUEB (the Athens University of Economics and Business). AUEB is located in the city center, and the main building is on 76 Patission st. If your hotel is not within walking distance, the best way to come to AUEB is by using the green line and getting off at Victoria station. It is then a 5 minute walk till the main building. There are also several buses and trolleys that stop just outside AUEB such as the buses 608, 622, A8, B8, Γ8 and the trolleys 3, 5, 11, 13, 14. In the map below you can have a better view of where the main building of AUEB is located.

How to reach the Acropolis Museum for the social event

To come to the social event on Friday evening, one option is to take the metro from Victoria station near AUEB and switch in Omonoia to the red line. Then you get off at the Akropolis station and the museum is just a few minutes walk from there. Alternatively you can take the trolley 5 (just across from the main building) and get off at the Makrygianni stop.

The Athens University of Economics and Business (AUEB), where the conference will take place, is located in the centre of Athens where many hotels can be found. We include here some recommended hotels, in walking distance from AUEB, and their offers for ISCO 2012.

1. Radisson Park Hotel                                     ISCO 2012 offer and booking form
   (~5 min walking distance from AUEB)
   Alexandras ave 10, 10682 Athens
   Tel.: +30 210 8894500
   Fax : +30 210 8238420
   anna.agrafa@rbathenspark.com
2. Areos Hotel                                                  ISCO 2012 offer
   (~5 min walking distance from AUEB)
   19 Mpoumpoulinas Street. 10682 Athens
   Tel: +30 210 8259540
   Fax: +30 210 8259244
   rsv@athensareoshotel.gr
3. Zafolia Hotel                                                 ISCO 2012 offer and booking form
   (~15 min walking distance from AUEB)
   87-89, Alexandras Av. 11474 Athens
   Tel: +30 210 6449 002
   Fax: +30 210 6442 042
   info@zafoliahotel.gr
4. Meliá Athens                                                ISCO 2012 offer and booking form
   (~15 min walking distance from AUEB)
   14 Chalkokondili & 28 October (Patision), 10677 Athens
   Tel: +30 210 3320100
   Fax: +30 210 3320200
   melia.athens@melia.com

Recommended areas for other accommodation options include: Panepistimiou street, Stadiou street, Syntagma square, Kolonaki.

For any further information please write to isco12@cs.aueb.gr