Search

Sample average approximation (SAA), the standard approach to stochastic mixed-integer programming, does not provide guidance for cases with limited computational budgets. In such settings, variance reduction is critical in identifying good decisions. This paper explores two closely related ensemble methods to determine effective decisions with a probabilistic guarantee. (a) The first approach recommends a decision by coordinating aggregation in the space of decisions as well as aggregation of objective values. This combination of aggregation methods generalizes the bagging method and the "compromise decision" of stochastic linear programming. Combining these concepts, we propose a stopping rule that provides an upper bound on the probability of early termination. (b) The second approach applies efficient computational budget allocation for objective function evaluation and contributes to identifying the best solution with a predicted lower bound on the probability of correct selection. It also reduces the variance of the upper bound estimate at optimality. Furthermore, it adaptively selects the evaluation sample size. Both approaches provide approximately optimal solutions even in cases with a huge number of scenarios, especially when scenarios are generated by using oracles/simulators. Finally, we demonstrate the effectiveness of these methods via extensive computational results for "megascale" (extremely large scale) stochastic facility location problems. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by The Office of Naval Research [Grant N00014-20-1-2077] and the Air Force Office of Scientific Research [Grant FA9550-20-1-0006]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0324) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0324). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Program coverage customization selectively adds instrumentation to a compiled computer program so that a limited amount of directly observed data can be used to infer other program coverage information after a run. A good instrumentation plan can reduce run-time overheads while still giving software developers the information they need. Unfortunately, optimal coverage planning is NP-hard, limiting either the quality of heuristic plans or the sizes of programs that can be instrumented optimally. We exploit the monotonicity property of feasible instrumentations to formulate this problem as an intraprocedural set covering problem. Our formulation has an exponential number of constraints, and we design a polynomial-time separation algorithm to incrementally add the necessary subset of these inequalities. Our approach reduces expected run-time probing costs compared with existing methods, offers a guarantee of the optimality of the instrumentation, and has compilation-time overhead suitable for wide practical use. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the National Science Foundation [Grants CCF-1318489, CCF-1420866, and CCF-1423237] and the Air Force Research Laboratory [Grant FA8750-14-2-0270]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0349) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0349). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In this paper, we study adjustable robust optimization (ARO) problems with discrete uncertainty. Under a very general modeling framework, we show that such two-stage robust problems can be exactly reformulated as ARO problems with objective uncertainty only. This reformulation is valid with and without the fixed recourse assumption and is not limited to continuous wait-and-see decision variables unlike most of the existing literature. Additionally, we extend an enumerative algorithm akin to a branch-and-cut scheme for which we study the asymptotic convergence. We discuss how to apply the reformulation on two variants of well-known optimization problems, a facility location problem in which uncertainty may affect the capacity values and a multiple knapsack problem with uncertain weights, and we report extensive computational results demonstrating the effectiveness of the approach. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by the Air Force Office of Scientific Research [Grants FA8655-20-1-7012, FA8655-20-1-7019]. [ABSTRACT FROM AUTHOR]