4 Presentations

• 
  03:30 PM - 03:55 PM

  New Steiner travelling salesman problem formulation and its location extension

  • Jessica Rodríguez Pereira, presenter, HEC Montréal
  • Elena Fernandez, Universitat Politècnica de Catalunya
  • Gilbert Laporte, HEC Montréal
  • Enrique Benavent, Universidad de Valencia
  • Antonio Martinez-Sykora, Southampton Business School, University of Southampton, United Kingdom

  In this work we present a new compact formulation with two-index variables and an exact branch-and-cut algorithm for the Steiner Traveling Salesman Problem (STSP). We also study its location extension (LSTSP). Computational results obtained confirm the good performance of the algorithms. Instances with up to 500 vertices are solved optimally.

  Keywords: Steiner Traveling Salesman Problem; integer linear programming; branch-and-cut
• 
  03:55 PM - 04:20 PM

  A flexible natural formulation for the network design problem with vulnerability constraints

  • Okan Arslan, presenter, GERAD, HEC Montréal
  • Ola Jabali, Politecnico di Milano
  • Gilbert Laporte, HEC Montréal

  Given a graph, a set of origin-destination (OD) pairs with communication requirements and an integer k, the network design problem with vulnerability constraints (NDPVC) is to identify a subgraph with the minimum total edge costs such that between each OD pair, there exist a hop-constrained primary path, and a hop-constrained backup path after any k-1 edges of the graph fail. We develop a natural formulation based on the notion of length-bounded cuts. Experimental results show that for single edge failures, our formulation increases the number of solved benchmark instances from 61% to over 95%. Our formulation also efficiently solves the NDPVC for multi-edge failures (k≥3).
• 
  04:20 PM - 04:45 PM

  On strengthening the RLT relaxations of mixed 0-1 polynomial programs

  • Franklin Djeumou Fomeni, presenter, ESG-UQAM (CIRRELT)
  • Konstantinos Kaparis, Athens University of Economics and Business
  • Adam Letchford, Lancaster University

  We present a procedure that generates strong cutting planes at any given relaxation level of the RLT hierarchy, by optimally weakening linear inequalities that are valid at any given higher RLT level. We also show that in some particular cases, the cutting planes are facets defining. Computational results will be discussed.
• 
  04:45 PM - 05:10 PM

  A comparison of different mathematical programming formulations for strategical cargo planification

  • Nabil Ouakil, presenter, GERAD
  • Patrick Munroe, GERAD - Polytechnique Montréal
  • Francois Soumis, GERAD et Polytechnique

  Cargo companies, just like any other company, are striving to do better and be more profitable. In order to do so, this continuous improvement has to include strategic decisions about evaluating and adapting the network, the company has to study the optimal shipment of the forcasted demand in the network for the following season. Given a set of demands to be transported from origins to destinations and a set of flights, the objective is to deliver the freight to destination through the network as efficiently as possible. However, operations are constrained by the physical characteristics of the infrastructure and the operational policies of the airports. To this end, we describe three different formulations of the problem and their implementations.