Discrete Optimization Talks (DOTs)
Discrete Optimization Talks (DOTs) is a virtual seminar series from the Mixed Integer Programming Society (MIPS), a technical section of the Mathematical Optimization Society.
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 October to December 2023, the seminars are scheduled the first Friday of every month at 12: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.
Videos of past DOTs are posted under Past Talks and can also be found on our YouTube 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).
Upcoming Talks
Self-Adapting Network Relaxations for Weakly Coupled Markov Decision Processes
Abstract: High-dimensional weakly coupled Markov decision processes (WDPs) arise in dynamic decision making and reinforcement learning, decomposing into smaller MDPs when linking constraints are relaxed. The Lagrangian relaxation of WDPs (LAG) exploits this property to compute policies and (optimistic) bounds efficiently; however, dualizing linking constraints averages away combinatorial information. We introduce feasibility network relaxations (FNRs), a new class of linear programming relaxations that exactly represents the linking constraints. We develop a procedure to obtain the unique minimally sized relaxation, which we refer to as self-adapting FNR, as its size automatically adjusts to the structure of the linking constraints. Our analysis informs model selection: (i) the self-adapting FNR provides (weakly) stronger bounds than LAG, is polynomially sized when linking constraints admit a tractable network representation, and can even be smaller than LAG, and (ii) self-adapting FNR provides bounds and policies that match the approximate linear programming (ALP) approach but is substantially smaller in size than the ALP formulation and a recent alternative Lagrangian that is equivalent to ALP. We perform numerical experiments on constrained dynamic assortment and preemptive maintenance applications. Our results show that self-adapting FNR significantly improves upon LAG in terms of policy performance and/or bounds, while being an order of magnitude faster than an alternative Lagrangian and ALP, which are unsolvable in several instances. (Joint work with Andre Cire, University of Toronto).
Link to paper: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4081430
Bio: Selva Nadarajah is an Associate Professor of Information and Decision Sciences at the University of Illinois Chicago (UIC) College of Business. His research addresses challenges at the interface of operations and finance arising in the energy industry using reinforcement learning and optimization. His recent work develops self-adapting approaches, which are optimization methods and formulations that are capable of automatically adapting themselves to instance-specific information in a problem class or information arriving over time. Selva has received the 2021 Commodity and Energy Markets Association (CEMA) Best Paper Award, the 2020 INFORMS ENRE Young Researcher Prize, the Best Overall Paper at the 2020 NeurIPS Workshop on Tackling Climate Change with Machine Learning, the 2014 William L. Cooper Dissertation Award, and the 2013 Egon Balas Best Student Paper Award. Selva completed his PhD in Operations Research at the Tepper School of Business in Carnegie Mellon University.
A hybrid logic-based Benders decomposition approach for the network migration problem
Abstract: Telecommunication networks frequently face technological advancements and need to upgrade their infrastructure. Adapting legacy networks to the latest technology requires synchronized technicians responsible for migrating the equipment. The goal of the network migration problem is to find an optimal plan for this process. This is a defining step in the customer acquisition of telecommunications service suppliers, and its outcome directly impacts the network owners’ purchasing behavior. We propose the first exact method for the network migration problem, a logic-based Benders decomposition approach that benefits from a hybrid constraint programming–based column generation in its master problem and a constraint programming model in its subproblem. This integrated solution technique is applicable to any integer programming problem with similar structure, most notably the vehicle routing problem with node synchronization constraints. Comprehensive evaluation of our method over instances based on six real networks demonstrates the computational efficiency of the algorithm in obtaining quality solutions. We also show the merit of each incorporated optimization paradigm in achieving this performance.
Link to the paper: https://pubsonline.informs.org/doi/abs/10.1287/ijoc.2023.1280
Bio: Maryam Daryalal is an assistant professor of Operations Research in the Department of Decision Sciences at HEC Montréal. Her research centers on developing innovative methodologies to address sequential decision-making problems under uncertainty, with applications in telecommunications, healthcare, scheduling, and supply chain planning. Additionally, Maryam develops solutions for large-scale operational challenges in telecommunication networks. Her accolades include the Judith Liebman Award, Connaught International Scholarship, and Concordia Merit Award. She holds a PhD in Operations Research from the University of Toronto's Mechanical and Industrial Engineering Department.
TBA
Abstract: TBA
TBA
Abstract: TBA
TBA
Abstract: TBA
TBA
Abstract: TBA
For questions or suggestions, please contact Aleksandr M. Kazachkov or Elias B. Khalil.
DOTs are supported by the Canada Excellence Research Chair in Data Science for Real-Time Decision-Making and the University of Florida Department of Industrial and Systems Engineering.
