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.
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
On the Simplex method for 0/1 polytopes
Abstract: The Simplex method is one of the most popular algorithms for solving linear programs, but despite decades of study, it is still not known whether there exists a pivot rule that guarantees it will always reach an optimal solution with a polynomial number of steps. In fact, a polynomial pivot rule is not even known for linear programs over 0/1 polytopes (0/1-LPs), despite the fact that the diameter of a 0/1 polytope is bounded by its dimension.
This talk will focus on the behavior of the Simplex method for 0/1-LPs, and discuss pivot rules that are guaranteed to require only a polynomial number of non-degenerate pivots.
Joint work with: Alexander Black, Jesus De Loera, Sean Kafer.
Integer programming column generation: Accelerating branch-and-price for set covering, packing, and partitioning problems
Abstract: Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch-and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with the sole aim to solve linear programming relaxations. Hence, the ability to form integer feasible solutions is not considered during the generation of columns. Without any changes to the standard pricing schemes, the potential of deploying generic LNS heuristics within a branch-and-price procedure is severely limited.
We propose a matheuristic, based on an LNS heuristic framework, where the novelty is a customised pricing scheme for generating columns to solve an auxiliary problem. The theoretical foundation for this pricing scheme is a set of optimality conditions for integer programs. From this foundation, a column generation strategy is developed for finding columns that are likely to be of use in high-quality primal feasible solutions for the original problem. The proposed matheuristic is implemented in the generic branch-price-and-cut solver GCG. On a broad test set comprising classical block diagonal structured instances and general instances from the MIPLIB 2017 Collection, the computational results show a significant improvement to the solving performance of GCG.
TBD
TBD
TBD
TBD
TBD
TBD
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.
