We propose an optimization framework to solve problems that involve parameters that are forecast to vary over a given time horizon. We model uncertainty in the forecast through the use of lower and upper bounds that can be seen as time-dependent uncertainty levels. Our framework is applicable in long-term budget planning or resource allocation settings. We propose a model to minimize the maximum deviation from a so-called “ideal function” that we then show can be reformulated as a narrowest path problem on an acyclic directed graph with weights determined by solving minimax regret problems. Given that constructing the graph might be computationally demanding, we devise an optimal path discovery iterative scheme that computes edge weights on an as-needed basis and that results in ε-optimal solutions in a finite number of steps. We conduct an extensive numerical analysis of the proposed procedure to determine average-case performance. We then apply our proposed framework in two real-life settings: (1) large-scale screening of populations for West Nile Virus and (2) the allocation of resources in blood donation centers. The results from both case studies indicate significant reductions in yearly societal costs. History: Accepted by J. Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. 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.2023.0048 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0048 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We study the design of large-scale group testing schemes under a heterogeneous population (i.e., subjects with potentially different risk) and with the availability of multiple tests. The objective is to classify the population as positive or negative for a given binary characteristic (e.g., the presence of an infectious disease) as efficiently and accurately as possible. Our approach examines components often neglected in the literature, such as the dependence of testing cost on the group size and the possibility of no testing, which are especially relevant within a heterogeneous setting. By developing key structural properties of the resulting optimization problem, we are able to reduce it to a network flow problem under a specific, yet not too restrictive, objective function. We then provide results that facilitate the construction of the resulting graph and finally provide a polynomial time algorithm. Our case study, on the screening of HIV in the United States, demonstrates the substantial benefits of the proposed approach over conventional screening methods. Summary of Contribution: This paper studies the problem of testing heterogeneous populations in groups in order to reduce costs and hence allow for the use of more efficient tests for high-risk groups. The resulting problem is a difficult combinatorial optimization problem that is NP-complete under a general objective. Using structural properties specific to our objective function, we show that the problem can be cast as a network flow problem and provide a polynomial time algorithm.

We study a large-scale resource allocation problem with a convex, separable, not necessarily differentiable objective function that includes uncertain parameters falling under an interval uncertainty set, considering a set of deterministic constraints. We devise an exact algorithm to solve the minimax regret formulation of this problem, which is NP-hard, and we show that the proposed Benders-type decomposition algorithm converges to an [Formula: see text]-optimal solution in finite time. We evaluate the performance of the proposed algorithm via an extensive computational study, and our results show that the proposed algorithm provides efficient solutions to large-scale problems, especially when the objective function is differentiable. Although the computation time takes longer for problems with nondifferentiable objective functions as expected, we show that good quality, near-optimal solutions can be achieved in shorter runtimes by using our exact approach. We also develop two heuristic approaches, which are partially based on our exact algorithm, and show that the merit of the proposed exact approach lies in both providing an [Formula: see text]-optimal solution and providing good quality near-optimal solutions by laying the foundation for efficient heuristic approaches.