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.


Spring school

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.

important dates

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

invited speakers

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.

Program committee

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:

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.

special issues

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

accepted regular papers

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

accepted short papers

To download the program in pdf, click here.

Spring school

"Mathematical Programming and Design of Approximation Algorithms"
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

and the k-median problem

The traveling salesman problem

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

and the prize-collecting TSP

spring school

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

Tuesday, April 17, 2012
9:00-10:30 Lecture 1
10:30-10:45 Coffee Break
10:45-12:30 Lecture 2
14:00-16:00 Problem Session 1
16:00-16:15 Coffee Break
16:15-18:00 Lecture 3
18:00-19:00 Problem Solutions 1
Wednesday, April 18, 2012
9:00-10:30 Lecture 4
10:30-10:45 Coffee Break
10:45-12:30 Lecture 5
14:00-16:00 Problem Session 2
16:00-16:15 Coffee Break
16:15-18:00 Lecture 6
18:00-19:00 Problem Solutions 2
organizing committee

Christos Amanatidis, AUEB, Athens
Katerina Kinta, Université Paris Dauphine
Anna Klouvatou, RC-AUEB, Athens
Giorgio Lucarelli, Université Paris Dauphine
A. Ridha Mahjoub, Université Paris Dauphine
Vangelis Markakis, AUEB, Athens
Ioannis Milis, AUEB, Athens
Vangelis Paschos, Université Paris Dauphine
Georgios Zois, AUEB, Athens

registration - fees

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

Registration Fees


up to 24/02/12


from 25/02/12

 ISCO 2012 Regular  360€ 480€
 ISCO 2012 Student  200€ 280€
 Spring School  10€ 20€
The ISCO 2012 registration fees include:
Welcome reception (on April 18th)
Coffee breaks
Conference final program
Conference proceedings
Conference social events and dinner

The Spring School fee applies for administrative purposes only.


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.

View ISCO 2012 in a larger map

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
  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
  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
  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

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


For any further information please write to