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 February to April 2023, the seminars are scheduled the last 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).
Theoretical and Computational Analysis of Strong Branching
Abstract: Strong branching is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On the positive side, we identify vertex cover as a class of instances where this rule provably works well. In particular, for vertex cover we present: 1) an upper bound on the size of the branch-and-bound tree using strong-branching as a function of the additive integrality gap; 2) show how the Nemhauser-Trotter property of persistency, which can be used as a pre-solve technique for vertex cover, is being recursively and consistently used throughout the strong-branching tree; 3) and finally provide an example of a vertex cover instance where not using strong-branching leads to a tree that has at least exponentially more nodes than the branch-and-bound tree based on strong-branching. On the negative side for strong-branching, we identify another class of instances where the strong-branching tree is exponentially larger than another branch-and-bound tree for solving these instances. On the computational side, we conduct experiments on various types of instances, like the lot-sizing problem and its variants, packing integer programs (IP), covering IPs, chance constrained IPs, vertex cover, etc., to understand how much larger is the size of the strong-branching based branch-and-bound tree in comparison to the optimal branch-and-bound tree. The main take-away from these experiments (on small instances) is that for all these instances the size of the strong-branching tree is within a factor of two of the size of the optimal branch-and-bound tree.
Traceability Technology Adoption in Supply Chain Networks
Abstract: Modern traceability technologies promise to improve supply chain management by simplifying recalls, increasing visibility, or verifying sustainable supplier practices. Initiatives leading the implementation of traceability technologies must choose the least-costly set of firms — or seed set — to target for early adoption. Choosing this seed set is challenging because firms are part of supply chains interlinked in complex networks, yielding an inherent supply chain effect: benefits obtained from traceability are conditional on technology adoption by a subset of firms in a product’s supply chain. We prove that the problem of selecting the least- costly seed set in a supply chain network is hard to solve and even approximate within a polylogarithmic factor. Nevertheless, we provide a novel linear programming-based algorithm to identify the least-costly seed set. The algorithm is fixed-parameter tractable in the supply chain network’s treewidth, which we show to be low in real-world supply chain networks. The algorithm also enables us to derive easily-computable bounds on the cost of selecting an optimal seed set. Finally, we leverage our algorithms to conduct large-scale numerical experiments that provide insights into how the supply chain network structure influences diffusion. These insights can help managers optimize their technology diffusion strategy.
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.