Abstract When computing bounds, spatial branch-and-bound algorithms often linearly outer approximate convex relaxations for non-convex expressions in order to capitalize on the efficiency and robustness of linear programming solvers. Considering that linear outer approximations sacrifice accuracy when approximating highly nonlinear functions and recognizing the recent advancements in the efficiency and robustness of available methods to solve optimization problems with quadratic objectives and constraints, we contemplate here the construction of quadratic outer approximations of twice-differentiable convex functions for use in deterministic global optimization. To this end, we present a novel cutting-plane algorithm that determines the tightest scaling parameter, $$\alpha $$ α , in the second-order Taylor series approximation quadratic underestimator proposed by Su et al. [25]. We use a representative set of convex functions extracted from optimization benchmark libraries to showcase–qualitatively and quantitatively–the tightness of the constructed quadratic underestimators and to demonstrate the overall computational efficiency of our algorithm. Furthermore, we extend our construction procedure to generate even tighter quadratic underestimators by allowing overestimation in infeasible polyhedral regions of optimization problems, as informed by the latter’s linear constraints.

Abstract Recent advances in the efficiency and robustness of algorithms solving convex quadratically constrained quadratic programming (QCQP) problems motivate developing techniques for creating convex quadratic relaxations that, although more expensive to compute, provide tighter bounds than their classical linear counterparts. In the first part of this two-paper series (Strahl et al. Constructing tight quadratic relaxations for global optimization: I. Outer-approximating twice-differentiable convex functions. Forthcoming, (2024)), we developed a cutting-plane algorithm to construct convex quadratic underestimators for twice-differentiable convex functions, which we extend here to address the case of non-convex difference-of-convex (d.c.) functions as well. Furthermore, we generalize our approach to consider a hierarchy of quadratic forms, thereby allowing the construction of even tighter underestimators. Utilizing a benchmark library of d.c. functions, we demonstrate noteworthy reduction in the hypervolume between our quadratic underestimators and linear ones constructed at the same points. Additionally, we construct convex QCQP relaxations at the root node of a spatial branch-and-bound tree for a set of systematically created d.c. optimization problems in up to four dimensions, and we show that our relaxations reduce the gap between the lower bound computed by the state-of-the-art global optimization solver BARON and the optimal solution by an excess of 90%, on average.

This paper studies robust variants of an extended model of the classical heterogeneous vehicle routing problem (HVRP), where a mixed fleet of vehicles with different capacities, availabilities, fixed costs, and routing costs is used to serve customers with uncertain demand. This model includes, as special cases, all variants of the HVRP studied in the literature with fixed and unlimited fleet sizes, accessibility restrictions at customer locations, and multiple depots. Contrary to its deterministic counterpart, the goal of the robust HVRP is to determine a minimum cost set of routes and fleet composition that remains feasible for all demand realizations from a prespecified uncertainty set. To solve this problem, we develop robust versions of classical node and edge exchange neighborhoods that are commonly used in local search and establish that efficient evaluation of the local moves can be achieved for five popular classes of uncertainty sets. The proposed local search is then incorporated in a modular fashion within two metaheuristic algorithms to determine robust HVRP solutions. The quality of the metaheuristic solutions is quantified using an integer programming model that provides lower bounds on the optimal solution. An extensive computational study on literature benchmarks shows that the proposed methods allow us to obtain high-quality robust solutions for different uncertainty sets and with minor additional effort compared with deterministic solutions.

Designing networks with specified collective properties is useful in a variety of application areas, enabling the study of how given properties affect the behavior of network models, the downscaling of empirical networks to workable sizes, and the analysis of network temporal evolution. Despite the importance of the task, there currently exists a gap in our ability to systematically generate networks that adhere to theoretical guarantees for the given property specifications. In thisarticle, we propose the use of Mixed‐Integer Linear Optimization modeling and solution methodologies to address thisNetwork Generation Problem. We present useful modeling techniques and apply them to mathematically express and constrain a broad class of network properties in the context of an optimization formulation. We derive complete formulations for the generation of networks that attain specified levels of connectivity, spread, assortativity and robustness, and we illustrate these via a number of computational case studies. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(4), 283–301 2016