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^Tx: Ax=b, x≥0, x∈Zⁿ} where A∈Z^m×n, b∈Z^m and c∈Zⁿ. We show that such an integer program can be solved in time (mΔ)^O(m)⋅‖b‖²_∞, where Δ is an upper bound on each absolute value of an entry in A. This improves upon the longstanding best bound of Papadimitriou (1981) of (m⋅Δ)^{O(m^2)}, where in addition, the absolute values of the entries of b also need to be bounded by Δ. Our result relies on a lemma of Steinitz that states that a set of vectors in R^m that 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. We also use the Steinitz lemma to show that the ℓ₁-distance of an optimal integer and fractional solution, also under the presence of upper bounds on the variables, is bounded by m⋅(2m⋅Δ+1)^m. Here Δ is again an upper bound on the absolute values of the entries of A. The novel strength of our bound is that it is independent of n. 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

Friedrich Eisenbrand's main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems.

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.

Marcia Fampa is a Full Professor at the Federal University of Rio de Janeiro (UFRJ), where she has been since 1997. She is at the Alberto Luiz Coimbra Institute for Graduate Studies and Research in Engineering (COPPE), at UFRJ, where she has supervised more than 25 PhD and master's students. She is currently a board member of the Brazilian Society of Operations Research (SOBRAPO), and a PC member of the Brazilian Symposium of Operational Research (SBPO), and of the Latin-Iberoamerican Conference on Operations Research (CLAIO). Marcia did her undergraduate studies at the Pontifical Catholic University of Rio de Janeiro (PUC/RJ), receiving an engineering degree in 1987. She received her PhD Degree in Systems and Computer Engineering from the Federal University of Rio de Janeiro in 1996. In 1995 and in 2005 she was a visiting researcher at the University of Iowa. Her main research interest is Mixed Integer Nonlinear Programming (MINLP), with focus on the development of convex relaxations for MINLP problems.

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)