Motivated by recent progress on online linear programming and online resource allocation, we study the online decision making problem (ODMP) as a natural generalization. In ODMP, a single decision maker undertakes a sequence of decisions over multiple (likely many) time steps. At each time step, the decision maker makes a locally feasible decision based on information available up to that point, without knowledge of the future. The objective is to maximize the total reward accumulated over time while satisfying some global constraints called goal constraints. Decision made at each step results in a vector that represents the contribution of this local decision to the (global) goal constraints. In the online setting, these global goal constraints are soft constraints that can possibly be violated moderately at the end of the time horizon. ODMP has a strong modeling power, allowing discrete and nonlinear local constraints and general convex global constraints (beyond packing and covering). To handle discreteness and nonlinearity in solving ODMP, we propose a simple Fenchel dual-based online algorithm. Under some stochastic input models, we show that our algorithm achieves sublinear constraint violation deterministically in meeting the long-term goals, and sublinear regret in expected reward with respect to the optimal offline decisions. Numerical experiments on an online knapsack problem with fairness-over-time constraints and an assortment optimization problem are conducted to demonstrate the potential of our proposed online algorithm.

We revisit the value of stochastic solution (VSS) in the context of distributional ambiguity. When uncertainty arises from the right-hand side of a two-stage stochastic program, we investigate VSS's upper and lower bounds using distributionally robust and optimistic optimization. Because these bounds are NP-hard to compute exactly, we derive tractable yet tight relaxations for them and demonstrate their effectiveness through numerical experiments.

Incorporating energy storage systems (ESS) into power systems has been studied in many recent works, where binary variables are often introduced to model the complementary nature of battery charging and discharging. A conventional approach for these ESS optimization problems is to relax binary variables and convert the problem into a linear program. However, such linear programming relaxation models can yield unrealistic fractional solutions, such as simultaneous charging and discharging. In this paper, we develop a regularized Mixed-Integer Programming (MIP) model for the ESS optimal power flow (OPF) problem. We prove that under mild conditions, the proposed regularized model admits a zero integrality gap with its linear programming relaxation; hence, it can be solved efficiently. By studying the properties of the regularized MIP model, we show that its optimal solution is also near-optimal to the original ESS OPF problem, thereby providing a valid and tight upper bound for the ESS OPF problem. The use of the regularized MIP model allows us to solve two intractable problems: a two-stage stochastic ESS OPF problem and a trilevel min-max-min network contingency problem.

Choice-based matching platforms have recently proliferated thanks to their application in labor markets, dating, accommodation and ride-sharing. Due to correlated preferences, these platforms face the challenge of reducing choice congestion among popular options who receive more requests than they can handle, which may lead to sub-optimal market outcomes. To address this challenge, we introduce a general framework for two-sided assortment optimization under general choice preferences. The goal is to maximize the expected number of matches by deciding which assortments are displayed to the agents and the order in which they are shown. In this setting, we identify a wide range of policy classes that matching platforms can use in their design. Our goals are: (1) to measure the value that one class of policies has over another one, and (2) to approximately solve the optimization problem itself for a given class. For (1), we define the adaptivity gap as the worst-case ratio between the optimal values of two different policy classes. We show tight constant gaps between several classes of policies and that the worst policies (relative to the rest) are those who simultaneously show assortments to everyone. For (2), we separately show constant-approximation guarantees for two policy classes which sit in opposite ends of the policy spectrum.