INFORMS 2021 Program Book

INFORMS Anaheim 2021

WC27

3 - Forecasting Life Cycles Using Bayesian Model Averaging and Exponential Smoothing Xiaojia Guo, Robert H. Smith School of Business, University of Maryland, International Hall, College Park, MD, WC1N 1AS, United States, Kenneth Lichtendahl, Yael Grushka-Cockayne We study the problem of forecasting the demand of a product or service that evolves according to a dynamically changing life cycle. These demand forecasts are often made prior to launch, and need to be updated frequently thereafter once realizations are available. We develop a new life cycle model that is based on Bayesian model averaging and exponential smoothing to forecast demand using past similar life cycles. In two empirical studies, we show that the rolling point forecasts and quantile forecasts generated by our new model are more accurate than those generated by the benchmarks. When quantile forecasts are used in a newsvendor setting, our new model also has the potential to provide meaningful economic benefit when compared to various existing models. 4 - Choice Modeling and Assortment Optimization in the Presence of Context Effects Reza Yousefi Maragheh, University of Illinois at Urbana- Champaign, Urbana, IL, 61801-2925, United States, Xin Chen, James M Davis, Jason Cho, Sushant Kumar In the presence of context effects, the perceived attractiveness of individual items depends on other items that are offered beside them. In this paper, we introduce a new Utility-Based choice model, the “Contextual MNL” model, that incorporates these effects. We show the high prediction power of the model on a real data set. We also prove the NP-hardness of the assortment optimization problem under this model. Several polynomially solvable special cases of the model are identified that also perform well in our empirical validation for our data set. Also, to derive approximation results, we obtain some conditions for monotonicity and submodularity of the objective of the assortment optimization problem. We also develop fast heuristics for solving the assortment optimization problem which provide near-optimal solutions according to our test results. WC26 CC Room 206A In Person: Decision Diagram Methods General Session Chair: Isaac Rudich, Polytechnique Montréal, Montréal, QC, H3G 1A3, Canada 1 - “ddo” a Fast and Efficient Framework for Solving Combinatorial Optimization Problems with Branch-and-bound MDD Xavier Gillard, Grad. Student, UC Louvain, Louvain-la-Neuve, Belgium In this talk I will present you “ddo” a free fast and efficient framework for solving combinatorial optimization problems with branch-and-bound MDDs. To that end, we will start modelling well known problems (Knapsack, Travelling Salesman with Time Window a.k.a TSPTW). Once the basic are in place, we will discuss some performance strategies. In particular, we will see how to easily exploit the available hardware on your platform. We will also see how to boost the performance of the solvers though the introduction of problem specific knowledge in the form of a rough upper bound. Finally, I will present some numerical results comparing the performance of “ddo” and Gurobi on the resolution of MISP (Maximum Independent Set Proble), MCP (Maximum Cut Problem) and MAX2SAT (Maximum 2 Satisfiability). These results show the Leonardo Lozano, University of Cincinnati, Carl H. Lindner Hall 2906 Woodside Ct Ofc 3347, Cincinnati, OH, 45246-2310, United States, David Bergman, Andre Augusto Cire We study a class of challenging discrete bilevel problems and propose a reformulation based on decision diagrams that results in a single-level mixed integer program (MIP). The decision diagrams are to provide a convex representation of the discrete follower problem which is then appended to the leader problem via KKT conditions. In contrast to previous approaches from the literature that reformulate bilevel problems as nonlinear single-level MIPs and often transform the resulting problem into a linear MIP usually via big-M formulations, our approach exploits the structure given by the decision diagrams to provide a linear reformulation, thus avoiding any linearization or big-M constraints. Computational experiments on a bilevel project selection problem shows that our approach greatly outperform two state-of-the-art bilevel relevance of using ddo as it may significantly outperform MIP. 2 - DD-based Reformulation for a Class of Combinatorial Bilevel Problems

algorithms from the literature. 3 - Improving Decision Diagram Relaxations for Sequencing Problems Isaac Rudich, Polytechnique Montréal, Montréal, QC, H3G 1A3, Canada

Relaxations of multivalued decision diagrams (MDDs) are effective for improving methods of solving sequencing problems. To strengthen the bounds generated by MDD relaxations, we used multiple metrics to improve merge rules and encoded a restricted MDD into the relaxed MDD. We evaluated our approach by comparing its performance to previous work done by Cire and van Hoeve on variations of the traveling salesman problem (TSP), such as the asymmetric TSP, TSP with time windows, TSP with precedence constraints, and the sequence ordering problem. WC27 CC Room 206B In Person: Optimization on Manifolds General Session Chair: David Gutman, Texas Tech University, Lubbock, TX, 79407, United States 1 - Trade-offs in Nonconvexity and Noise Models in the Global Stability of Stochastic Gradient Descent Vivak Patel, Assistant Professor, University of Wisconsin-Madison, Madison, WI, United States Recently, it was demonstrated that stochastic gradient descent (SGD) either diverges or converges to stationary points with probability one for a very broad class of nonconvex stochastic optimization problems. However, this result does not address the question of stability: will SGD diverge to regions where the objective function is diverging? Unfortunately, the answer is not simple. We begin by showing that there is a sufficiently slow growth function on which SGD is unstable. Accoridngly, we will suggest that there is a trade-off between the nonconvexity and the noise models that ensures the stability of SGD. For stochastic objectives that satisfy this trade-off, we will be able to show that SGD is stable using a single analysis. Moreover, we will be able to show that SGD converges (in probability and L1) to regions of the objective function where the gradient is zero. 2 - An Inexact Sequential Quadratic Method for Nonlinear Equality Constrained Stochastic Optimization Baoyu Zhou, Lehigh University, Bethlehem, PA, 18015, United States, Frank E. Curtis, Daniel Robinson We propose an inexact sequential quadratic optimization algorithm for minimizing a stochastic objective function subject to deterministic equality constraints. Algorithms that allow inexact subproblem solutions to be used are important in large-scale applications when the matrices used by the subproblem solver are too expensive to form or factorize. The inexact conditions that we propose for characterizing appropriate subproblem solutions address challenges resulting from the stochasticity in the objective function. Convergence results (in expectation) are established for our proposed method (under common assumptions), and numerical experiments demonstrate that our method outperforms exact variants in terms of key efficiency measures. 3 - Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds David Gutman, Texas Tech University, Lubbock, TX, 79407, United States, Nam Ho-Nguyen We consider an extension of the coordinate descent algorithm to manifold domains, and provide convergence analyses for geodesically convex and non- convex smooth objective functions. Our key insight is to draw an analogy between coordinate blocks in Euclidean space and tangent subspaces of a manifold. Hence, our method is called tangent subspace descent (TSD). The core principle behind ensuring convergence of TSD is the appropriate choice of subspace at each iteration. To this end, we propose two novel conditions: the gap ensuring and C-randomized norm conditions on deterministic and randomized modes of subspace selection respectively. These ensure convergence for smooth functions, and are satisfied in practical contexts. We propose randomized and deterministic subspace selection rules of particular practical interest for the Stiefel manifold.

163