Session: New Advances in Robust Optimization
Chair: Shimrit Shtern
Cluster: Optimization Under Uncertainty and Data-driven Optimization
Talk 1: Robust Extensible Bin Packing and Revisiting the Convex Knapsack Problem
Speaker: Noam Goldberg
Abstract: We study a robust extensible bin packing problem with budgeted uncertainty, an uncertainty model where item sizes are defined to lie in the intersection of a box with a one-norm ball. We propose a scenario generation algorithm for this problem, which alternates between solving a master robust bin-packing problem with finite uncertainty set and solving a separation problem. We first show that the separation is strongly NP-hard given solutions to the continuous relaxation of the master problem. Then, focusing on the separation problem for the integer master problem, we show that this problem becomes a special case of the continuous convex knapsack problem, which is known to be weakly NP-hard. Next, we prove that our special case when each of the functions is piecewise linear, having only two pieces, remains NP-hard. We develop a pseudo-polynomial dynamic program (DP) and a fully polynomial-time approximation scheme (FPTAS) for general convex knapsack with improved running times. For our special case, we develop an even faster variant of the DP and FPTAS whose running time matches that of a binary knapsack FPTAS. Finally, our computational study shows that the DP can be significantly more efficient in practice compared with solving the problem with specially ordered set (SOS) constraints using advanced mixed-integer (MIP) solvers. Our experiments also demonstrate the application of our pricing problem method to solving the robust extensible bin packing problem, including the evaluation of deferring the exact solution of the master problem, separating based on approximate master solutions in intermediate iterations.
Talk 2: Distributionally robust optimization through the lens of submodularity
Speaker: Karthik Natarajan
Abstract: Distributionally robust optimization is used to solve decision making problems under adversarial uncertainty where the distribution of the uncertainty is itself ambiguous. In this paper, we identify a class of these instances that is solvable in polynomial time by viewing it through the lens of submodularity. We discuss applications in multimarginal optimal transport and generalized moment problems using this approach.
Talk 3: Robust Fluid Models with Adjustable Controllers
Speaker: Shimrit Shtern
Abstract: Fluid models are widely used to approximately optimize the service policy in complicated service networks, where the stochasticity is replaced by arrival and service rates. These models can be cast as structured semicontinuous linear programs (SCLP) which can be solved using dedicated simplex based solvers. Uncertainty can appear in these models when the arrival and service rates are not known exactly. In the literature, such models are addressed via robust optimization. These robust optimization models restrict the controller, determining the service policy at each point in time, to be set in the start of the planning horizon, and do not allow to change it based on revealed information about the uncertainty. We suggest a novel partially adaptive model, in which we can change the controller based on the state of the system in predefined time points, and reformulate the resulting problem as a SCLP for various uncertainty sets.
