Search

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., 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. On a set of d.c. functions extracted from benchmark libraries, 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.

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. 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.

Inventory management, vehicle routing, and delivery scheduling decisions are simultaneously considered in the context of the inventory routing problem. This paper focuses on the continuous-time version of this problem where, unlike its more traditional discrete-time counterpart, the distributor is required to guarantee that inventory levels are maintained within the desired intervals at any moment of the planning horizon. In this work, we develop a compact mixed-integer linear programming formulation to model the continuous-time inventory routing problem. We further discuss means to expedite its solution process, including the adaptation of well-known rounded capacity inequalities to tighten the formulation in the context of a branch-and-cut algorithm. Through extensive computational studies on a suite of 90 benchmark instances from the literature, we show that our branch-and-cut algorithm outperforms the state-of-the-art approach. We also consider a new set of 63 instances adapted from a real-life dataset and show our algorithm's practical value in solving instances with up to 20 customers to guaranteed optimality., Comment: Accepted by Computers and Operations Research

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, as well as 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 pre-specified 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 to deterministic solutions., Comment: 54 pages, 10 figures, 12 tables

We study the strategic decision-making problem of assigning time windows to customers in the context of vehicle routing applications that are affected by operational uncertainty. This problem, known as the Time Window Assignment Vehicle Routing Problem, can be viewed as a two-stage stochastic optimization problem, where time window assignments constitute first-stage decisions, vehicle routes adhering to the assigned time windows constitute second-stage decisions, and the objective is to minimize the expected routing costs. We prove that a sampled deterministic equivalent of this stochastic model can be reduced to a variant of the Consistent Vehicle Routing Problem, and we leverage this result to develop a new scenario decomposition algorithm to solve it. From a modeling viewpoint, our approach can accommodate both continuous and discrete sets of feasible time window assignments as well as general scenario-based models of uncertainty for several routing-specific parameters, including customer demands and travel times, among others. From an algorithmic viewpoint, our approach can be easily parallelized, can utilize any available vehicle routing solver as a black box, and can be readily modified as a heuristic for large-scale instances. We perform a comprehensive computational study to demonstrate that our algorithm strongly outperforms all existing solution methods, as well as to quantify the trade-off between computational tractability and expected cost savings when considering a larger number of future scenarios during strategic time window assignment., Comment: 45 pages, 10 figures, 8 tables

We study two-stage robust optimization problems with mixed discrete-continuous decisions in both stages. Despite their broad range of applications, these problems pose two fundamental challenges: (i) they constitute infinite-dimensional problems that require a finite-dimensional approximation, and (ii) the presence of discrete recourse decisions typically prohibits duality-based solution schemes. We address the first challenge by studying a $K$-adaptability formulation that selects $K$ candidate recourse policies before observing the realization of the uncertain parameters and that implements the best of these policies after the realization is known. We address the second challenge through a branch-and-bound scheme that enjoys asymptotic convergence in general and finite convergence under specific conditions. We illustrate the performance of our algorithm in numerical experiments involving benchmark data from several application domains.

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 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 this paper, we propose the use of Mixed-Integer Linear Optimization modeling and solution methodologies to address this Network Generation Problem. We present a number of useful modeling techniques and apply them to mathematically express and constrain network properties in the context of an optimization formulation. We then develop 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.