This paper focuses on non-asymptotic confidence bounds (CB) for the optimal values of stochastic optimization (SO) problems. Existing approaches often rely on two conditions that may be restrictive: The need for a global Lipschitz constant and the assumption of light-tailed distributions. Beyond either of the conditions, it remains largely unknown whether computable CBs can be constructed. In view of this literature gap, we provide three key findings below: (i) Based on the conventional formulation of sample average approximation (SAA), we derive non-Lipschitzian CBs for convex SP problems under heavy tails. (ii) We explore diametrical risk minimization (DRM)—a recently introduced modification to SAA—and attain non-Lipschitzian CBs for nonconvex SP problems in light-tailed settings. (iii) We extend our analysis of DRM to handle heavy-tailed randomness by utilizing properties in formulations for training over-parameterized classification models.

This paper presents an algorithmic framework for conducting search and identification missions using multiple heterogeneous agents. Dynamic objects of type ldquoneutralrdquo or ldquotargetrdquo move through a discretized environment. Probabilistic representation of the current level of situational awareness - knowledge or belief of object locations and identities - is updated with imperfect observations. Optimization of search is formulated as a mixed-integer program to maximize the expected number of targets found and solved efficiently in a receding horizon approach. The search effort is conducted in tandem with object identification and target interception tasks, and a method for assignment of these missions among agents is developed. The proposed framework is demonstrated in simulation studies, and an implementation of its decision support capabilities in a recent field experiment is reported.

Abstract The constrained shortest‐path problem (CSPP) generalizes the standard shortest‐path problem by adding one or more path‐weight side constraints. We present a new algorithm for CSPP that Lagrangianizes those constraints, optimizes the resulting Lagrangian function, identifies a feasible solution, and then closes any optimality gap by enumerating near‐shortest paths, measured with respect to the Lagrangianized length. “Near‐shortest” implies ε‐optimal, with a varying ε that equals the current optimality gap. The algorithm exploits a variety of techniques: a new path‐enumeration method; aggregated constraints; preprocessing to eliminate edges that cannot form part of an optimal solution; “reprocessing” that reapplies preprocessing steps as improved solutions are found; and, when needed, a “phase‐I procedure” to identify a feasible solution before searching for an optimal one. The new algorithm is often an order of magnitude faster than a state‐of‐the‐art label‐setting algorithm on singly constrained randomly generated grid networks. On multiconstrained grid networks, road networks, and networks for aircraft routing the advantage varies but, overall, the new algorithm is competitive with the label‐setting algorithm. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

We describe a new algorithm for computing the efficient frontier of the “bi-objective maximum-flow network-interdiction problem.” In this problem, an “interdictor” seeks to interdict (destroy) a set of arcs in a capacitated network that are Pareto-optimal with respect to two objectives, minimizing total interdiction cost and minimizing maximum flow. The algorithm identifies these solutions through a sequence of single-objective problems solved using Lagrangian relaxation and a specialized branch-and-bound algorithm. The Lagrangian problems are simply max-flow min-cut problems, while the branch-and-bound procedure partially enumerates s-t cuts. Computational tests reveal the new algorithm to be one to two orders of magnitude faster than an algorithm that replaces the specialized branch-and-bound algorithm with a standard integer-programming solver.