Discrete Optimization Talks (DOTs)

Abstract:
The frequency and impact of wildfires have considerably increased in the past decade due to extreme weather conditions and rising population density. These fires now pose significant threats to forests, homes, and human lives. Climate change has further exacerbated their environmental and economic consequences, necessitating comprehensive preparedness and response strategies—even in regions where wildfires were not historically a major concern. This study was inspired by discussions with wildfire management officials from a province in Turkey, Natural Resources Wales, the UK Forestry Commission, and Forestry England.

We introduce, model, and solve a wildfire suppression problem involving the coordination of heterogeneous firefighting resources, including fire brigades, helicopters, and razing teams. Unlike most existing models that treat all resources generically, we explicitly incorporate their distinct operational constraints and effects on fire control. Two integer programming formulations are proposed: a polynomial-sized model and a Benders’ decomposition reformulation. Both mathematical formulations are tested on randomly generated instances that simulate realistic wildfire scenarios and resource constraints.

Our computational experiments show that both formulations can produce high-quality upper and lower bounds. Extensive numerical testing was conducted to assess the impact of different operational constraints on model performance and to evaluate the effectiveness of various resource combinations. The findings emphasize the importance of selecting the appropriate mix of firefighting assets for effective wildfire suppression. A case study from the Yatagan district of Muğla province in Turkey illustrates the model’s practical application, with visual maps depicting the fire's progression over time.

This study contributes a novel approach to modelling wildfire suppression by accounting for the heterogeneous nature of firefighting resources. The proposed methods offer valuable insights for decision-makers in developing efficient wildfire response strategies.

Bio:
Maria Battarra is a Professor in Operations Research at the University of Bath, School of Management. In 2010, she obtained a PhD from the University of Bologna in Operational Research and she specialized in the study of combinatorial optimisation problems.  Her research mainly focuses on developing innovative exact and metaheuristic algorithms for real world applications, including but not limited to vehicle routing problems, scheduling problems, and disaster relief management. Her research has been published in prestigious international journals, as Operations Research, Transportation Science, Informs Journal of Computing, European Journal of Operational Research, Computers & OR and Decision Sciences.

Abstract:  
Motivated by our collaboration with a residency program at an academic health system, we propose new integer programming (IP) approaches for the resident-to- rotation assignment problem (RRAP). Given sets of residents, resident classes, and departments, as well as a block structure for each class, staffing needs, rotation requirements for each class, program rules, and resident vacation requests, the RRAP involves finding a feasible year-long rotation schedule that specifies resident assignments to rotations and vacation times. We first present an IP formulation for the RRAP, which mimics the manual method for generating rotation schedules in practice and can be easily implemented and efficiently solved using off-the-shelf optimization software. However, it can lead to disparities in satisfying vacation requests among residents. To mitigate such disparities, we derive an equity-promoting counterpart that finds an optimal rotation schedule, maximizing the number of satisfied vacation requests while minimizing a measure of disparity in satisfying these requests. Then, we propose a computationally efficient Pareto Search Algorithm capable of finding the complete set of Pareto optimal solutions to the equity-promoting IP within a time that is suitable for practical implementation. Additionally, we present a user-friendly tool that implements the proposed models to automate the generation of the rotation schedule. Finally, we construct diverse RRAP instances based on data from our collaborator and conduct extensive experiments to illustrate the potential practical benefits of our proposed approaches. Our results demonstrate the computational efficiency and implementability of our approaches and underscore their potential to enhance fairness in resident rotation scheduling. 

Bio:  
Dr. Karmel S. Shehadeh is WiSE Gabilan Assistant Professor of Industrial and Systems Engineering at the University of Southern California (USC). Before joining USC in 2025, she was an assistant professor of ISE at Lehigh University. She holds a Ph.D. in Industrial and Operations Engineering from the University of Michigan. Her research program aims to push the boundaries of the theory and applications of stochastic and (distributionally) robust optimization (SRO). Her research group has a track record of designing, analyzing, and implementing innovative and computationally efficient SRO and integer programming models and algorithms to solve challenging real-world optimization problems across diverse application domains, including healthcare, facility location, humanitarian logistics, and transportation. Another stream of her research focuses on designing decomposition algorithms and fairness-promoting optimization frameworks. Her work has been published in top-tier journals, including Operations Research, Transportation Science (TS), European Journal of Operational Research, Naval Research Logistics, and Transportation Research Part C (TR-C). Professional recognition of her work includes an INFORMS Minority Issues Forum  (MIF) Early Career Award, an MIF Paper Award, a Junior Faculty Interest Group (JFIG) Paper Prize, a Service Science Best Cluster Paper Prize, and Lehigh's Alfred Noble Robinson Faculty Award. She serves as an associate editor for four  journals (TS, IJOC, HCMS, and TR-C). Vice President of Communications of the INFORMS Section on Public and Societal Operations Research, Vice President (President-elect) of the INFORMS Section on Location Analysis (SOLA), and President of JFIG. 

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract:
For mixed-integer linear programs (MILPs), strong branching is a highly effective variable selection method in branch-and-bound. Extending it to nonlinear problems (NLPs) is conceptually simple but practically limited. In MILPs, branching fixes a variable to 0 or 1, whereas branching on a continuous variable requires an additional decision to choose a branching point. Previous extensions of strong branching for NLP typically pre-defines this point (for example, via a convex combination of the relaxed solution and the midpoint of the variable’s bound) and then solves 2n relaxations where n is the number of candidate variables to evaluate the improvement. We propose extreme strong branching, which evaluates multiple branching points per variable and jointly selects both the branching variable and point based on the objective value improvement. This approach resembles the success of strong branching in the MILP while additionally exploiting bound tightening as a by-product. Despite the substantial computational burden, extreme strong branching outperforms other branching rules and state-of-the-art commercial solver for certain types of QCQPs.

Bio:
Dahye Han is a Ph.D. student in Operations Research at Georgia Tech, advised by Dr. Santanu Dey. Her research focuses on design and analysis of algorithms for mixed-integer nonlinear programming and applying advanced optimization techniques to domains such as power systems and structural engineering. She is also interested in leveraging machine learning as an auxiliary tool to support and enhance optimization methods. 

Abstract:
We study a class of vehicle routing problems (VRPs) with generic intra-route constraints that can be tested in polynomial time. These problems are naturally modeled using column generation (CG), where variables correspond to a route relaxation and the pricing problem is a resource-constrained shortest path problem (RCSPP). However, depending on the intra-route constraints, the RCSPP state space can become prohibitively large. To address this, we propose a hybrid approach that integrates CG with the recently introduced column elimination (CE) method. Starting from a relaxation of the RCSPP, we iteratively refine the state space using CE and enforce feasibility through cutting planes. Computational experiments on the Chance-Constrained VRP with Stochastic Demands (CC-VRPSD) show that CG+CE outperforms both CG and CE alone, solving more instances and achieving smaller root gaps. On the 1-Commodity Pickup and Delivery VRP (1-PDVRP), our method also improves over the previous state-of-the-art exact algorithm, yielding tighter root gaps and solving more instances to optimality.

Bio:
Matheus J. Ota is a PhD student in the Department of Combinatorics and Optimization at the University of Waterloo. His research interests include vehicle routing, combinatorial optimization, integer programming, and stochastic optimization. He holds both a Master’s degree in Computer Science and a Bachelor’s degree in Computer Engineering from the University of Campinas, Brazil.

Abstract:
Symmetries are functions that preserve an object's structure while mapping it onto itself. They arise throughout mathematics, and integer programming is no exception: at least 36% of the instances in MIPLIB 2010 contain nontrivial symmetries (Margot, 2010; Pfetsch & Rehn, 2019). It is folklore knowledge that symmetry "harms'' IP solvers. Our main goal is to understand how symmetry affects the improvement of dual bounds of IPs under Lift-and-Project (L&P) operators. In particular, our work raises a fundamental question: Can we characterize the conditions that lead to the elimination of a symmetric optimal face of a relaxation at a fractional node in the branch-and-cut tree?

Let $P \subseteq [0,1]^{n}$ be a linear relaxation of some integer set ${X \subseteq \{0,1\}^{n}}$, and let $G \leq S_{n}$ be a subgroup of the group of formulation symmetries of $P$. We will show that if $G$ is $k$-transitive, i.e., for every pair of $k$-tuples there exists $g \in G$ mapping one tuple into the other one, then we can characterize when $(k-1)$ iterations of some classical L&P hierarchies will cut-off any $G$-invariant integer-empty face of $P$. Strikingly, the necessary and sufficient conditions are identical across the operators: L&P closure, Lovász-Schrijver, and Lovász-Schrijver with p.s.d. constraint, and Sherali-Adams. Two key implications are that, for highly symmetric IPs, these hierarchies achieve the same progress in the objective regardless of the operator, yielding a hierarchy collapse, and that the greater the symmetry of the optimal LP face, the harder it is to eliminate.

Bio: 

Matias Villagra is a Ph.D. student in Operations Research at Columbia University, co-advised by Dan Bienstock and Yuri Faenza. He works on large-scale and computationally challenging mixed-integer nonlinear programs. In particular, he studies the fundamental AC Optimal Power Flow problem and its applications in operations, planning, and pricing. He is also interested in the role of symmetry in optimization, particularly in integer programming, both in understanding its principles and in designing symmetry-aware algorithms.

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.