Optimization Days 2019
HEC Montréal, May 1315, 2019
JOPT2019
HEC Montréal, 13 — 15 May 2019
TD4 Mathematical Modeling II
May 14, 2019 03:30 PM – 05:10 PM
Location: GérardParizeau
4 Presentations

03:30 PM  03:55 PM
New Steiner travelling salesman problem formulation and its location extension
In this work we present a new compact formulation with twoindex variables and an exact branchandcut 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; branchandcut

03:55 PM  04:20 PM
A flexible natural formulation for the network design problem with vulnerability constraints
Given a graph, a set of origindestination (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 hopconstrained primary path, and a hopconstrained backup path after any k1 edges of the graph fail. We develop a natural formulation based on the notion of lengthbounded 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 multiedge failures (k≥3).

04:20 PM  04:45 PM
On strengthening the RLT relaxations of mixed 01 polynomial programs
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
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.