# Keynote Speakers

## Friedrich Eisenbrand (EPFL, Lausanne, Switzerland)

**Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma**

We consider integer programming problems in standard form max{

c^{T}x:Ax=b,x≥0,x∈Z^{n}} whereA∈Z^{m×n},b∈Z^{m}andc∈Z^{n}. We show that such an integer program can be solved in time (mΔ)^{O(m)}⋅‖b‖^{2}_{∞}, where Δ is an upper bound on each absolute value of an entry inA. This improves upon the longstanding best bound of Papadimitriou (1981) of (m⋅Δ)^{O(m^2)}, where in addition, the absolute values of the entries ofbalso need to be bounded by Δ. Our result relies on a lemma of Steinitz that states that a set of vectors inRthat is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by^{m}m. We also use the Steinitz lemma to show that theℓ_{1}-distance of an optimal integer and fractional solution, also under the presence of upper bounds on the variables, is bounded bym⋅(2m⋅Δ+1)^{m}. Here Δ is again an upper bound on the absolute values of the entries ofA. The novel strength of our bound is that it is independent ofn. We provide evidence for the significance of our bound by applying it to general knapsack problems where we obtain structural and algorithmic results that improve upon the recent literature.

Joint work with Robert Weismantel

Before joining EPFL in March 2008, Friedrich Eisenbrand was a full professor of mathematics at the University of Paderborn. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004 and the Otto Hahn medal of the Max Planck Society in 2001. He was a recipient of an Alexander von Humboldt professorship in 2011.

## Marcia Fampa (Federal University of Rio de Janeiro, Brazil)

**Challenges in MINLP - The Euclidean Steiner Tree Problem in n-dimensional space**

The Euclidean Steiner tree problem asks for a network of minimum length interconnecting a given set of points in n-dimensional. We present a historical background for this problem, discuss existing algorithms to solve it, and identify characteristics of the problem that make its solution a big challenge when n is greater than 2, focusing on the application of MINLP solvers to different formulations. We present ideas that have been applied to handle the main difficulties in the solution of the problem, and point out others as future research directions.

## Bernard Gendron (University of Montreal, Canada)

**Lagrangian Relaxations and Reformulations for Network Design**

We consider a general network design model for which we compare theoretically different Lagrangian relaxations. Fairly general assumptions on the model are proposed, allowing us to generalize results obtained for special cases. The concepts are illustrated on the fixed-charge multicommodity capacitated network design problem, for which we present three different Lagrangian relaxations: the well-known shortest path and knapsack relaxations, and a new one, called the facility location relaxation. Dantzig-Wolfe reformulations are derived for each of these Lagrangian relaxations and bundle methods are proposed for solving these reformulations, along with Lagrangian heuristics and branch-and-price algorithms.

Bernard Gendron is a Professor at the Département d'informatique et de recherche opérationelle, Université de Montréal. His research interests focus on the optimization of logistics and transportation networks. He has served as Director of CIRRELT, the Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (2008-2015). He has held positions of Principal Scientist at ILOG, Paris, and of Visiting Professor at MIT, EPFL, Centrale Lille, Pisa, Nice-Sophia-Antipolis, Blaise-Pascal, Versailles and Valenciennes. He has served as Chair of the Canadian Operational Research Society (CORS), Chair of the Montreal Chapter of CORS, and Chair of the Section on Transportation Science & Logistics of INFORMS (the Institue for Operations Research and the Management Sciences). He was awarded the CORS Practice Prize (2004), the CORS Service Award (2006) and the CORS Merit Award (2010).

## Franz Rendl (University of Klagenfurt, Graz, Austria)

**Order through partition: A semidefinite Programming Approach**

Ordering Problems on n objects involve pairwise comparison among all objects. This typically requires n(n-1)/2 decision variables. In this talk we investigate the idea of partitioning the objects into k groups (k-partition) and impose order only among the partition blocks. We demonstrate the efficiency of this approach in connection with the bandwidth minimization on graphs. We consider relaxations of the partition model with the following characteristics: 1) The weakest model is formulated in the space of symmetric n × n matrices and has the Hoffman-Wielandt theorem in combination with eigenvalue optimization as a theoretical basis. 2) We also consider semidefinite relaxations in the space of n × n matrices, involving k semidefinite matrix variables. The idea here is to linearize the quadratic terms using eigenvalue decompositions. 3) Finally, the strongest model is formulated in the space of symmetric nk × nk matrices. It is based on the standard reformulation-linearization idea. We present theoretical results for these relaxations, and also some preliminary computational experience in the context of bandwidth minimization.

Co-authors: Renata Sotirov (Tilburg, Netherlands) and Christian Truden (Klagenfurt, Austria)

Franz Rendl, born 1956 in Austria, studies of applied mathematics at Technical University in Graz, PhD 1983. Academic positions: Assistant and associate professor at TU Graz (Austria) until 1998 since 1998: full professor for applied mathematics at Alpen-Adria University in Klagenfurt, Austria visiting positions in Waterloo (Canada), Augsburg (Germany), Paris 6, IASI Rome, Massey University (New Zealand), Cambridge (UK) Research interests: combinatorial optimization and graph algorithms, algorithmic treatment of conic optimization problems, eigenvalue optimization and matrix analysis, exact algorithms for NP-hard problems, Research support from EU projects and the Austrian Science Foundation. He has published more than 100 publications in international journals, such as SIAM Journal on Optimization, Mathematical Programming, Linear Algebra and Applications, COAP, etc. Associate Editor: SIAM Journal on Optimization (1999-2013), Mathematical Programming (1999-2013), Journal of Combinatorial Optimization (2000-2013), Discrete Optimization (since 2004), Area editor for optimization in: APJOR (2011-2016), RAIRO (since 2011)