Discrete Optimization Talks (DOTs)

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: Branch-and-bound has been for decades the workhorse of solution methods for the broad class of Mixed Integer Programming (MIP) problems. For MIP problems whose continuous relaxation is linear or convex, branching on integer and binary variables guarantees termination. On the other hand, in order to find a global optimum of MIPs with a nonlinear, nonconvex continuous relaxation, spatial branching, i.e., branching on continuous variables, is needed.

We argue that, for MIPs with convex relaxations, branching on continuous variables can be more effective than on discrete variables. We prove this by studying two well-known Mixed Integer Quadratic Programming problems arising from Machine Learning and from Geometric Clustering applications. For both classes of problems, we amend a common MIP solver, the FICO Xpress Optimizer, with a branching scheme for continuous variables. Computational tests show that, for these two problem classes, spatial branching outperforms, sometimes by orders of magnitude, the standard integer branching.

Bio: Pietro Belotti is Associate Professor at the Department of Electronics, Information and Bioengineering of the Politecnico di Milano. He received a doctoral degree in Computer Engineering at Politecnico di Milano in 2003. He has been postdoc at Carnegie Mellon University; Visiting Assistant Professor at Lehigh University; and Assistant Professor at the Mathematical Science department of Clemson University. From 2013 to 2021 he was Software Engineer at FICO, within the Xpress Optimizer team.

His research interests are mainly in mixed integer nonlinear optimization, discrete multiobjective optimization, and optimization of power grids. Pietro is the author and maintainer of Couenne, an open-source software package for solving global optimization problems. 

Abstract: We present some old and new results on arbitrary families of parametric polyhedra. First, if the constraint matrix is fixed, in the literature there are structural results for the integer hull and the finiteness of cutting plane closures for varying r.h.s. For instance, recently, Becu et al. proved in "Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data" that the GMI closure of this family is finitely generated, in the sense that there exists a finite list of aggregation weights defining the GMI cuts that give the GMI closure for any polyhedra in the family. We extend this result for other cutting plane closures. Second, if the family of parametric  polyhedra is arbitrary but all polyhedra in the family have the same integer hull, they define the same MIP, and we can leverage this information to understand and solve MIPs better. These families have been used to understand theoretical properties of the rank of cutting planes and to obtain better formulations. We present an application of these same-integer-hull families to formulations for the Asymmetric Traveling Salesman Problem.

The talk includes joint work with Gustavo Angulo and future joint work with Silvia Di Gregorio.

Bio: Diego Moran Ramirez is an assistant professor in the Department of Industrial and Systems Engineering at Rensselaer Polytechnic Institute. He holds a Ph.D. in Operations Research from the Georgia Institute of Technology, a Mathematical Engineer professional degree (BS and MS equivalent) and a Master in Operations Management from Universidad de Chile. Prior to joining RPI, Dr. Moran Ramirez was an assistant professor in the School of Business at Universidad Adolfo Ibañez and an assistant professor in the Industrial and Systems Engineering department at Virginia Tech. His main research interest is Optimization with a focus on the theory and applications of mixed-integer linear and nonlinear programming. His research in mathematical optimization is motivated by algorithmic aspects of mixed-integer programs and he has also worked on projects involving the application of optimization to solve real-world problems arising in production planning, logistics and other business and engineering relevant areas. He received the INFORMS Optimization Society Student Paper Prize in 2012 and the IBM Faculty Award in 2018.

Abstract: In this paper, we study the Regularized A-Optimal Design (ROAD) problem, which aims to select a subset of k experiments to minimize the inverse of the resulting Fisher information matrix, regularized with a scaled identity matrix.  ROAD has broad applications in Bayesian experimental design, sensor placement, and cold-start recommendation. We first prove the NP-hardness of ROAD by reducing the independent set decision problem to it. To solve ROAD efficiently, we introduce a novel convex integer programming reformulation and derive the optimality gap for its continuous relaxation, which enables us to develop a cutting-plane algorithm. We demonstrate that this reformulation provides the tightest relaxation compared to existing convex integer programs of ROAD. We also derive the optimality gaps of existing continuous relaxations and demonstrate that, in certain ranges of k, these gaps can be arbitrarily large, highlighting their limitations. In addition, we consider forward and backward greedy algorithms for approximately solving ROAD,  each with provable performance guarantees for different ranges of k. When combined, these algorithms achieve the best-known approximation ratio. Finally, our numerical results show that the exact algorithm performs efficiently for small and medium cases, while the approximation algorithms scale well to large instances with high solution quality. We also highlight the practical effectiveness of RAOD by applying it to a real-world user cold-start recommendation problem.

Bio: Dr. Yongchun Li is an assistant professor in the Department of Industrial and Systems Engineering at the University of Tennessee Knoxville. She received a PhD in Operations Research from Georgia Tech. Her research interests lie at the intersection of optimization, machine learning (ML), and statistics, with the goal of advancing ML towards greater interpretability, efficiency, fairness, and robustness.

Abstract: Multiobjective integer (linear) programs (MOIPs), as the name suggests, simultaneously optimize multiple objective functions 183over a set of linear constraints and integer variables. Relaxations of MOIPs provide bounds on their solutions and play an important role in solution algorithms. In this talk, we present a Lagrangian relaxation of an MOIP and discuss its properties. Specifically, we show that there exist sparse Lagrangian multipliers that satisfy a complementary slackness property and generate tight relaxations at supported solutions. At unsupported solutions, where the convex hull relaxation is not tight either, we show that a Lagrangian relaxation improves upon the convex hull bounds. We use the Lagrangian relaxation to define a Lagrangian dual of an MOIP and establish weak duality. The dual is strong at supported solutions under certain conditions on the primal feasible region which are identical to the single-objective case.

Bio: Saumya Sinha is an Assistant Professor of Industrial & Systems Engineering at the University of Minnestota - Twin Cities. She joined UMN in Fall 2022, before which she was a postdoctoral scholar at Rice University and a visiting postdoctoral fellow at Houston Methodist Hospital, working in the areas of optimization and organ transplantation. She received her PhD in applied mathematics at the University of Washington, Seattle, where her dissertation focused on robust dynamic programming. Sinha’s research focuses on decision-making in uncertain and dynamic environments, especially using robust and multiobjective optimization, motivated primarily by applications in clinical decision-making, healthcare operations, and health policy. 

Abstract: The increasing complexity of modern mobility systems is challenging traditional engineering practices. A fundamental challenge is that different engineering requirements lead to distinct optimization and control problems, each necessitating specialized techniques that can take years to develop. As a result, researchers are increasingly turning to machine learning (ML) to automate the development of solvers. However, recent findings—including our own—indicate that pure ML methods can be brittle and often underperform compared to classical solvers. To address this, we propose a learning-guided optimization approach that combines the strengths of ML with established optimization techniques. The focus is on creating algorithms that automatically customize optimization methods based on the specific characteristics of different problem instances. We have developed learning-guided optimization algorithms for branch-and-cut methods, rolling horizon optimization, and large neighborhood search. Experimentally, these algorithms accelerate state-of-the-art optimization solvers by up to 50-85%. We will discuss applications in areas such as mixed-integer linear programming, flexible job shop scheduling, vehicle routing, and multi-agent pathfinding. We will also discuss recent work that starts to address the brittleness of pure ML methods.

Bio: Cathy Wu is an Associate Professor at MIT in LIDS, CEE, and IDSS. She holds a Ph.D. from UC Berkeley, and B.S. and M.Eng. from MIT, all in EECS, and completed a Postdoc at Microsoft Research. Her research advances machine learning for control and optimization in mobility. She is broadly interested in AI for Engineering. Cathy has received a number of awards, including the NSF CAREER, PhD dissertation awards, and publications with distinction. She serves on the Board of Governors for the IEEE ITSS, is a Program Co-chair for RLC 2025, and is an Associate Editor (or equivalent) for ICML, NeurIPS, and ICRA. She is also spearheading efforts towards reproducible research in transportation, including co-founding the RERITE Working Group.

Abstract. In this talk, I will introduce distributionally risk-receptive and distributionally robust multistage stochastic integer programs (denoted by DRR- and DRO-MSIPs). I will present cutting plane-based and reformulation-based approaches for solving DRR- and DRA-MSIPs without and with decision-dependent uncertainty. These frameworks are applicable for mitigating the impact of data corruption, and for modeling and solving Stackelberg games that are played between an interdictor and a defender. These games are helpful for making long-term planning decisions and analyzing vulnerabilities in a system. More specifically, the interdictor makes interdiction decisions using limited resources to degrade the defender’s performance, and the defender makes decisions after observing the interdiction decision. The DRR- and DRO stochastic programs allow uncertainty in the success and impact of the attacks by an interdictor, adjustments based on risk-appetite (risk-receptive or risk-averse) of the decision makers (both interdictor and defender), and incomplete information of probability distribution associated with uncertain data parameters. I will present computational results for DRR and DRO multistage maximum flow and facility location interdiction problems. Furthermore, if time permits, I will briefly discuss the applications of DRR models in machine learning by introducing feature selection interdiction problem. 

Bio. Dr. Manish Bansal is an Associate Professor, Grado Early Career Faculty Fellow, and Operations Research Program Area Lead with Grado Department of Industrial and Systems Engineering at Virginia Tech. He did bachelor’s in electrical engineering from National Institute of Technology in India, and M.S. with thesis and Ph.D. from Department of Industrial and Systems Engineering at Texas A&M University. Prior to joining Virginia Tech, he was a postdoctoral fellow in Department of Industrial Engineering and Management Sciences at Northwestern University. His research is focused on the theory of mixed integer programming, stochastic and distributionally ambiguous optimization, game theory, and location science along with their applications in logistics and supply chain management. He has received multiple grants from National Science Foundation, Department of Defense, Automotive Research Center at University of Michigan Ann Arbor, and Commonwealth Cyber Initiatives. Dr. Bansal has served as president of INFORMS Junior Faculty Interest Group and Engineering Faculty Organization at Virginia Tech. He is also an affiliate faculty with the National Security Institute, and Center for AI and Data Analytics at Virginia Tech.

Abstract: Cutting-plane generators are among the most important components of modern MILP solvers. Together with other components, like presolve and branch-and-bound, they enable us to solve a wide range of practical optimization problems. While cutting planes unquestionably work in practice, a closer look at how and why they work leaves many open questions. In this talk I will touch on three topics related to cutting planes in which I failed to understand what’s going on and, in some cases, probably continue to fail to this day. These topics are: the path mixing cuts first published as part of my thesis and now implemented in some commercial MILP solvers, the relationship among various families of cuts such as lifted flow cover cuts and mingling cuts, and the never-ending mystery of cutting-plane selection.

Abstract: Stochastic facility location problems with outsourcing costs (SFLPOC) optimize facility placement and customer assignment under demand uncertainty. Excess demand beyond a facility’s capacity incurs outsourcing costs. This work addresses SFLPOC, aiming to minimize overall expected costs (installation, servicing, and outsourcing). We model SFLPOC as a two-stage stochastic program. While prior work focused on specific assumptions or small scenario sets, we present methods suitable for general probability distributions. For discrete scenario sets, we improve upon classic Benders decomposition by exploiting the second-stage subproblem’s structure. To handle general distributions, we partition the probability space based on incumbent integer solutions. Coupled with Benders cuts, this provides an exact solution method for common distributions (e.g., Bernoulli, Gaussian). Additionally, we introduce a compact formulation specifically for i.i.d. demand distributions, allowing us to solve even continuous distribution problems to optimality. Computational experiments on established benchmarks demonstrate that our compact formulation consistently finds optimal solutions, while the Benders approach provides strong solutions with proven optimality gaps for general distributions, outperforming sample average approximations. Joint work with Javiera Barrera (Universidad Adolfo Ibanez) and Ivana Ljubic (ESSEC Business School).