Abstract Typically, probability distributions that generate uncertain parameters cannot be measured exactly in practice. As a remedy, distributional robustness determines optimized decisions that are protected in a robust fashion against all probability distributions in some appropriately chosen ambiguity set. In this work, we consider robust joint chance-constrained optimization problems and focus on discrete probability distributions. Many methods for this kind of problems study convex or even linear constraint functions. In contrast, we introduce a practically efficient scenario-based bundle method without convexity assumptions on the constraint functions. We start by deriving an approximation problem to the original robust chance-constrained version by using smoothing and penalization techniques that build on our former work on chance-constrained optimization. Our convergence results with respect to the smoothing approximation and well-known results for penalty approximations suggest replacing the original problem with the approximation problem for large smoothing and penalty parameters. Our scenario-based bundle method starts by solving the approximation problem with a bundle method, and then uses the bundle solution to decide which scenarios to include in a scenario-expanded formulation. This formulation is a standard nonlinear optimization problem. Our approach is guaranteed to find feasible solutions. Furthermore, in the numerical experiments on real-world gas transport problems with uncertain demands, we mostly find globally optimal solutions. Comparing these results to the classical robust reformulations for ambiguity sets consisting of confidence intervals and Wasserstein balls, we observe that the scenario-based bundle method typically outperforms solving the classical reformulation directly.

Quantum computation promises to advance a wide range of computational tasks. However, current quantum hardware suffers from noise and is too small for error correction. Thus, accurately utilizing noisy quantum computers strongly relies on noise characterization, mitigation, and suppression. Crucially, these methods must also be efficient in terms of their classical and quantum overhead. Here, we efficiently characterize and mitigate crosstalk noise, which is a severe error source in, for example, cross-resonance based superconducting quantum processors. For crosstalk characterization, we develop a simplified measurement experiment. Furthermore, we analyze the problem of optimal experiment scheduling and solve it for common hardware architectures. After characterization, we mitigate noise in quantum circuits by a noise-aware qubit routing algorithm. Our integer programming algorithm extends previous work on optimized qubit routing by swap insertion. We incorporate the measured crosstalk errors in addition to other, more easily accessible noise data in the objective function. Furthermore, we strengthen the underlying integer linear model by proving a convex hull result about an associated class of polytopes, which has applications beyond this work. We evaluate the proposed method by characterizing crosstalk noise for two chips with up to 127 qubits and leverage the resulting data to improve the approximation ratio of the Quantum Approximate Optimization Algorithm by up to 10% compared with other established noise-aware routing methods. Our work clearly demonstrates the gains of including noise data when mapping abstract quantum circuits to hardware native ones. History: Accepted by Giacomo Nannicini, Area Editor for Quantum Computing and Operations Research. Accepted for Special Issue on Quantum Computing. Funding: This work was supported by Bavarian state government; Bayerische Staatsministerium für Wirtschaft, Landesentwicklung und Energie. 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.2024.0551 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0551 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.

Advancements in mathematical programming have made it possible to efficiently tackle large-scale real-world problems that were deemed intractable just a few decades ago. However, provably optimal solutions may not be accepted due to the perception of optimization software as a black box. Although well understood by scientists, this lacks easy accessibility for practitioners. Hence, we advocate for introducing the explainability of a solution as another evaluation criterion, next to its objective value, which enables us to find trade-off solutions between these two criteria. Explainability is attained by comparing against (not necessarily optimal) solutions that were implemented in similar situations in the past. Thus, solutions are preferred that exhibit similar features. Although we prove that already in simple cases the explainable model is NP-hard, we characterize relevant polynomially solvable cases such as the explainable shortest path problem. Our numerical experiments on both artificial as well as real-world road networks show the resulting Pareto front. It turns out that the cost of enforcing explainability can be very small.

We present a solution framework for general alternating current optimal power flow (AC OPF) problems that include discrete decisions. The latter occur, for instance, in the context of the curtailment of renewables or the switching of power-generation units and transmission lines. Our approach delivers globally optimal solutions and is provably convergent. We model AC OPF problems with discrete decisions as mixed-integer nonlinear programs (MINLPs). The solution method starts from a known framework that uses piecewise linear relaxations. These relaxations are modeled as mixed-integer linear programs and adaptively refined until some termination criterion is fulfilled. In this work, we extend and complement this approach by problem-specific as well as very general algorithmic enhancements. In particular, these are mixed-integer second order cone programs as well as primal and dual cutting planes. For example, objective and no-good cuts help to compute good feasible solutions in which outer approximation constraints tighten the relaxations. We present extensive numerical results for various AC OPF problems in which discrete decisions play a major role. Even for hard instances with a large proportion of discrete decisions, the method is able to generate high-quality solutions efficiently. Furthermore, we compare our approach with state-of-the-art MINLP solvers. Our method outperforms all other algorithms. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This research has been funded by the Federal Ministry of Education and Research of Germany [Grant 05M18WEB]. This research has been performed as part of the Energie Campus Nürnberg and is supported by funding of the Bavarian State Government. The authors thank the Deutsche Forschungsgemeinschaft for support within projects A05, B06, B07, and B10 of the Sonderforschungsbereich/Transregio 154 “Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks.” This work has been supported by the Federal Ministry for Economic Affairs and Energy, Germany [Grant 03El1036A]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.1270 .

Currently, there are few theoretical or practical approaches available for general nonlinear robust optimization. Moreover, the approaches that do exist impose restrictive assumptions on the problem structure. We present an adaptive bundle method for nonlinear and nonconvex robust optimization problems with a suitable notion of inexactness in function values and subgradients. As the worst-case evaluation requires a global solution to the adversarial problem, it is a main challenge in a general nonconvex nonlinear setting. Moreover, computing elements of an ε-perturbation of the Clarke subdifferential in the [Formula: see text]-norm sense is in general prohibitive for this class of problems. In this article, instead of developing an entirely new bundle concept, we demonstrate how existing approaches, such as Noll’s bundle method for nonconvex minimization with inexact information [Noll D (2013) Bundle method for non-convex minimization with inexact subgradients and function values. Computational and Analytical Mathematics, Springer Proceedings Mathematics, vol. 50 (Springer, New York), 555–592.] can be modified to be able to cope with this situation. Extending the nonconvex bundle concept to the case of robust optimization in this way, we prove convergence under two assumptions: first, that the objective function is lower C 1 and, second, that approximately optimal solutions to the adversarial maximization problem are available. The proposed method is, hence, applicable to a rather general setting of nonlinear robust optimization problems. In particular, we do not rely on a specific structure of the adversary’s constraints. The considered class of robust optimization problems covers the case that the worst-case adversary only needs to be evaluated up to a certain precision. One possibility to evaluate the worst case with the desired degree of precision is the use of techniques from mixed-integer linear programming. We investigate the procedure on some analytic examples. As applications, we study the gas transport problem under uncertainties in demand and in physical parameters that affect pressure losses in the pipes. Computational results for examples in large realistic gas network instances demonstrate the applicability as well as the efficiency of the method. Summary of Contribution: Nonlinear robust optimization is a relevant field of research as real-world optimization problems usually suffer from not precisely known parameters, for example, physical parameters that cannot be measured exactly. Currently, there are few theoretical or practical approaches available for general nonlinear robust optimization. Moreover, the methods that do exist impose restrictive assumptions on the problem structure. Writing nonlinear robust optimization tasks in minimax form, in principle, bundle methods can be used to solve the resulting nonsmooth problem. However, there are a number of difficulties to overcome. First, the inner adversarial problem needs to be solved to global optimality, which is a major challenge in a general nonconvex nonlinear setting. In order to cope with this, an adaptive solution approach, which allows for inexactness, is required. A second challenge is then that the computation of elements from an ε-neighborhood of the Clarke subdifferential is, in general, prohibitive. We show how an existing bundle concept by D. Noll for nonconvex problems with inexactness in function values and subgradients can be adapted to this situation. The resulting method only requires availability of approximate worst-case evaluations, and in particular, it does not rely on a specific structure of the adversarial constraints. To evaluate the worst case with the desired degree of precision, one possibility is the use of techniques from mixed-integer linear programming. In the course of the paper, we discuss convergence properties of the resulting method and demonstrate its efficiency by means of robust gas transport problems.

For a mixed-integer linear problem (MIP) with uncertain constraints, the radius of robust feasibility (RRF) determines a value for the maximal size of the uncertainty set such that robust feasibility of the MIP can be guaranteed. The approaches for the RRF in the literature are restricted to continuous optimization problems. We first analyze relations between the RRF of a MIP and its continuous linear (LP) relaxation. In particular, we derive conditions under which a MIP and its LP relaxation have the same RRF. Afterward, we extend the notion of the RRF such that it can be applied to a large variety of optimization problems and uncertainty sets. In contrast to the setting commonly used in the literature, we consider for every constraint a potentially different uncertainty set that is not necessarily full-dimensional. Thus, we generalize the RRF to MIPs and to include safe variables and constraints; that is, where uncertainties do not affect certain variables or constraints. In the extended setting, we again analyze relations between the RRF for a MIP and its LP relaxation. Afterward, we present methods for computing the RRF of LPs and of MIPs with safe variables and constraints. Finally, we show that the new methodologies can be successfully applied to the instances in the MIPLIB 2017 for computing the RRF. Summary of Contribution: Robust optimization is an important field of operations research due to its capability of protecting optimization problems from data uncertainties that are usually defined via so-called uncertainty sets. Intensive research has been conducted in developing algorithmically tractable reformulations of the usually semi-infinite robust optimization problems. However, in applications it also important to construct appropriate uncertainty sets (i.e., prohibiting too conservative, intractable, or even infeasible robust optimization problems due to the choice of the uncertainty set). In doing so, it is useful to know the maximal “size” of a given uncertainty set such that a robust feasible solution still exists. In this paper, we study one notion of “size”: the radius of robust feasibility (RRF). We contribute on the theoretical side by generalizing the RRF to MIPs as well as to include “safe” variables and constraints (i.e., where uncertainties do not affect certain variables or constraints). This allows to apply the RRF to many applications since safe variables and constraints exist in most applications. We also provide first methods for computing the RRF of LPs as well as of MIPs with safe variables and constraints. Finally, we show that the new methodologies can be successfully applied to the instances in the MIPLIB 2017 for computing the RRF.

Abstract Solving mixed-integer nonlinear optimization problems (MINLPs) to global optimality is extremely challenging. An important step for enabling their solution consists in the design of convex relaxations of the feasible set. Known solution approaches based on spatial branch-and-bound become more effective the tighter the used relaxations are. Relaxations are commonly established by convex underestimators, where each constraint function is considered separately. Instead, a considerably tighter relaxation can be found via so-called simultaneous convexification, where convex underestimators are derived for more than one constraint function at a time. In this work, we present a global solution approach for solving mixed-integer nonlinear problems that uses simultaneous convexification. We introduce a separation method that relies on determining the convex envelope of linear combinations of the constraint functions and on solving a nonsmooth convex problem. In particular, we apply the method to quadratic absolute value functions and derive their convex envelopes. The practicality of the proposed solution approach is demonstrated on several test instances from gas network optimization, where the method outperforms standard approaches that use separate convex relaxations.

Abstract We study gas network problems with compressors and control valves under uncertainty that can be formulated as two‐stage robust optimization problems. Uncertain data are present in the physical parameters of the pipes as well as in the overall demand. We show how to exploit the special decomposable structure of the problem to reformulate the two‐stage problem as a single‐stage robust optimization problem. The right‐hand side of the single‐stage problem can be precomputed by solving a series of optimization problems and multiple elements of the right‐hand side can be combined into one optimization task. The practical feasibility and effectiveness of our approach is demonstrated with benchmarks on several gas network instances, among them a realistic model of the Greek natural gas network. Overall, aggregation and preprocessing allow us to quickly solve large gas network instances under uncertainty for the price of slightly more conservative solutions.