Numerically safe lower bounds for the Capacitated Vehicle Routing Problem

The resolution of integer programming problems is typically performed via branch-and-bound. Nodes of the branch-and-bound tree are pruned whenever the corresponding subproblem is proven not to contain a solution better than the best solution found so far. This is a key ingredient for achieving reasonable solution times. However, since subproblems are solved in floating-point arithmetic, … Read more

Global optimal control with the direct multiple shooting method

We propose to solve global optimal control problems with a new algorithm that is based on Bock’s direct multiple shooting method. We provide conditions and numerical evidence for a significant overall runtime reduction compared to the standard single shooting approach. Citation Optimal Control Applications and Methods, Vol. 39 (2), pp. 449–470, 2017 DOI 10.1002/oca.2324 Article … Read more

Stochastic Dual Dynamic Integer Programming

Multistage stochastic integer programming (MSIP) combines the difficulty of uncertainty, dynamics, and non-convexity, and constitutes a class of extremely challenging problems. A common formulation for these problems is a dynamic programming formulation involving nested cost-to-go functions. In the linear setting, the cost-to-go functions are convex polyhedral, and decomposition algorithms, such as nested Benders’ decomposition and … Read more

A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem

The bounded degree sum-of-squares (BSOS) hierarchy of Lasserre, Toh, and Yang [EURO J. Comput. Optim., 2015] constructs lower bounds for a general polynomial optimization problem with compact feasible set, by solving a sequence of semi-definite programming (SDP) problems. Lasserre, Toh, and Yang prove that these lower bounds converge to the optimal value of the original … Read more

Towards an accurate solution of wireless network design problems

The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. … Read more

SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework

This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An … Read more

Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis

Nonconvex optimization problems are frequently encountered in much of statistics, business, science and engineering, but they are not yet widely recognized as a technology. A reason for this relatively low degree of popularity is the lack of a well developed system of theory and algorithms to support the applications, as is the case for its … Read more

MIDAS: A Mixed Integer Dynamic Approximation Scheme

Mixed Integer Dynamic Approximation Scheme (MIDAS) is a new sampling-based algorithm for solving finite-horizon stochastic dynamic programs with monotonic Bellman functions. MIDAS approximates these value functions using step functions, leading to stage problems that are mixed integer programs. We provide a general description of MIDAS, and prove its almost-sure convergence to an epsilon-optimal policy when … Read more

An Exact Algorithm for a Resource Allocation Problem in Mobile Wireless Communications

We consider a challenging resource allocation problem arising in mobile wireless communications. The goal is to allocate the available channels and power in a so-called OFDMA system, in order to maximise the transmission rate, subject to quality of service (QoS) constraints. Standard MINLP software struggled to solve even small instances of this problem. Using outer … Read more

Scenario Tree Reduction Methods Through Changing Node Values

To develop practical and efficient scenario tree reduction methods, we introduce a new methodology which allows for changing node values, and an easy-to-calculate distance function to measure the difference between two scenario trees. Based on minimizing the new distance, we first construct a primitive scenario tree reduction model which also minimizes the Wasserstein distance between … Read more