Operations Research and Statistics Seminar
Fall 2020
-
Dec02
-
The value of conic optimization for analytics practitionersDr. Erling AndersenMOSEK ApSTime: 12:00 PM
View Abstract
Linear optimization, also known as linear programming, is a modeling framework widely used by analytics practitioners. The reason is that many optimization problems can easily be described in this framework. Moreover, huge linear optimization problems can be solved using readily available software and computers. However, a linear model is not always a good way to describe an optimization problem since the problem may contain nonlinearities. Nevertheless, such nonlinearities are often ignored or linearized because a nonlinear model is considered cumbersome. Also, there are issues with local versus global optima and in general, it is just much harder to work with nonlinear functions than linear functions. Over the last 15 years, a new paradigm for formulating certain nonlinear optimization problems called conic optimization has appeared. The advantage of conic optimization is that it allows the formulation of a wide variety of nonlinearities while almost keeping the simplicity and efficiency of linear optimization. Therefore, in this presentation, we will discuss what conic optimization is and why it is relevant to analytics practitioners. In particular, we will discuss what can be formulated using conic optimization, illustrated by examples. We will also provide some computational results documenting that large conic optimization problems can be solved efficiently in practice. To summarize, this presentation should be interesting for everyone interested in an important recent development in nonlinear optimization.
-
Nov16
-
Decomposition Methods for Solving Large-scale Network Flow Optimization ProblemsDr. Rob CurryUSNATime: 03:45 PM
View Abstract
In this talk, I present multiple projects detailing current and future work in mathematical programming methods for solving large-scale network flow optimization problems. In the first project, I consider time-dependent network applications that may require dynamic flows to be transmitted according to a non-simultaneous schedule of path-flows. I thus study a dynamic network flow problem that considers the presence of set up costs required to begin transmitting flow on an arc. I employ a relaxation-based algorithm for obtaining upper and lower bounds for this problem that solves a series of smaller MIPs. I present computational results to demonstrate the efficacy of my approach. In the second project, I detail application-focused work in combating illegal territorial expansion in maritime settings. Criminal actors prioritize unlawful territorial expansion in contested waters in order to expand financial and territorial dominance over such waters. Thus, I plan to explore mixed-integer programming techniques to optimize resource management and strategic coordination for ally actors in order to mitigate this illegal territorial expansion. This latter project is joint work with Assoc. Prof. Dan Bates and MIDN 1/C Micah Oh and is a part of MIDN Oh's honors project. In this presentation, I only informally introduce and discuss this problem.
-
Nov02
-
Dense spanning trees and applicationsDr. Hua WangGeorgia Southern UniversityTime: 03:45 PM
View Abstract
We introduce the notion of dense (and consequently sparse) spanning trees. We show that finding dense and sparse spanning trees reduces to solving the discrete optimization problems. Solving these optimization problems exactly may be prohibitively time consuming for large graphs. Hence, we examine fast heuristics for finding such structures. We also discuss some related applications.
-
Oct19
-
Exact algorithms for discrete bilevel programmingDr. Leonardo LozanoUniversity of CincinnatiTime: 03:45 PM
View Abstract
Bilevel optimization considers two-player, two-level Stackelberg games in which a leader and a follower sequentially solve interdependent problems that optimize different objective functions. Bilevel optimization problems subsume a wide array of problems in robust optimization, network interdiction, and two-stage stochastic programming, which are known to be NP-hard in general. Discrete bilevel problems are particularly challenging as standard approaches for bilevel problems require the follower's problem to be convex. We proposed exact solution methodologies for discrete bilevel problems based on a value-function-reformulation of the problem and convexification techniques via decision diagrams. Our proposed algorithms outperform standard approaches from the literature on a collection of test problems from different application areas.
-
Oct05
-
Real-time Discrete Optimization of Coronavirus RecallCDR Matt HawksUSNATime: 03:45 PM
View Abstract
The coronavirus lockdowns occurred while the US Naval Academy was on Spring Break. The campus soon shifted academic courses to virtual delivery, keeping some 4,600 students off campus. Normally, all students reside in the single large dormitory, Bancroft Hall. Now, Bancroft Hall needed to be made ready for the arrival of the next entering class. We optimized the staggered return of graduating midshipmen to pick up their belongings from Bancroft Hall and participate in a small, closed, socially-distanced graduation and commissioning event. Constraints included a maximum number of midshipmen from each living zone, assigning roommates to different groups, and a preference for bringing back geographically distant seniors first and local seniors last. We comment on the solution, further constraints, and robustness.
-
Sep21
-
Iteration Complexity of Algorithms for Linear Programming ProblemGoran LesajaUSNATime: 03:45 PM