Discrete Optimization Talks (DOTs)
DOTs are virtual discrete optimization talks, organized by Aleksandr M. Kazachkov and Elias B. Khalil. To receive updates (and the Zoom link) for upcoming DOTs, please join our mailing list. If you would like to give a DOT, please fill out this form or email us.
Topics of interest include theoretical, computational, and applied aspects of integer and combinatorial optimization.
The format is two 30-minute talks each session. From September to December 2022, the seminars are scheduled one Friday of every month at 1:00 p.m. ET.
A special feature of DOTs is a social component. After a usual talk, you might grab a tea/coffee and chat with other attendees. Why not here too? Join us for some informal discussion after each DOT, as well as throughout the week on our Discord channel.
Join the mailing list to receive information about our upcoming seminars and how to virtually participate. Joining this list is necessary to receive the password for each DOT (usually sent on the Monday of the week in which there are DOTs). You may also wish to subscribe to our Google calendar (also available in ics format).
MIP-based branch-and-bound for the discrete ordered median problem
Abstract: Given a set N of n points, a non-negative distance matrix D of dimensions n x n, an integer p > 1 and an integer-valued weight vector lambda of size n, we consider the problem of selecting a subset C of exactly p points from N (also referred to as the centres) so as to: 1) assign each point in N to its closest centre in C; 2) sort the resulting distances (between every point and its center) from smallest to largest in a vector that we denote d*; 3) minimize <lambda, d*>. This problem generalizes several classical location problems such as the vertex p-centre problem or the p-median problem. We present a method that decomposes the problem in a series of simpler problems with unit weights to derive a valid dual bound. The subproblems happen to be much easier both theoretically and in practice than the DOMP. We embed the dual bound within a branch-and-bound solver for the DOMP. We present computational results to assess the performance of the proposed approach.
Bio: Claudio Contardo is an Associate Professor of Operations Research at the Department of Mechanical and Industrial Engineering at Concordia University. Prior to joining Concordia, he was a developer for the IBM CPLEX solver, and an Associate Professor at the UQAM Business School before that. He holds a BSc in Applied Mathematics from the U of Chile and a PhD in Computer Science from the U of Montreal. He is a regular member of GERAD. His research interests focus on the application of mathematical programming techniques for optimization problems arising in logistics, transportation and other areas.
Conference scheduling: a clustering-based approach
Abstract: Scheduling the technical sessions of scientific events is an arduous task commonly faced by many organizers worldwide. Due to the particularities of each conference, there is no consensus regarding the problem definition, and researchers have tackled each specific case individually. Despite their distinct characteristics, one often expects the sessions to be composed of presentations of similar scope. This natural assumption led us to define a basic yet sufficiently general version of the problem that aims at maximizing the benefit of clustering papers with common topics in the same session, while leaving the particularities of the event to be addressed by means of side constraints. Three mathematical formulations based on integer linear programming are proposed for the problem, which in turn is shown to be NP-hard. The first model consists of a compact formulation, whereas the second and third models serve as underlying formulations for branch-and-cut (BC) and branch-cut-and-price (BCP) algorithms, respectively. Computational experiments were carried out on real-life and artificial instances derived from two conferences, considering several scenarios. While the compact formulation and the BC procedure could solve instances with moderate size, the BCP approach managed to produce tight bounds for instances with up to 163 presentations.
Bio: Anand Subramanian is an Associate Professor at Universidade Federal da Paraíba (UFPB), Brazil. He received his B.Sc. degree in Mechanical Production Engineering from UFPB in 2006 and his M.Sc. degree in Production Engineering in 2008 from the same institution. He obtained his doctorate in Computing in 2012 from the Universidade Federal Fluminense (UFF), Brazil. His doctoral thesis received the Honorable Mention award from the Brazilian Ministry of Education and it was selected among the top 6 thesis (presented in 2012) by the Brazilian Computing Society. His research interests are mainly related to developing heuristic, exact and hybrid algorithms for combinatorial optimization problems. Anand is an author of more than 50 articles published in prestigious international journals. In 2016 he received the highly cited research award from Elsevier for the paper "A hybrid algorithm for a class of vehicle routing problems" published in Computers & Operations Research (C&OR). In addition, he was the supervisor of the works that won the prize for the best undergraduate paper at the Brazilian OR Conference in 2015 and 2021. Moreover, he has been a member of the Editorial Advisory Board of C&OR since 2019, and coordinates or has coordinated 11 research projects with public or private funding. Anand is the organizer and host of the "Subject to" podcast.