For most optimisation methods an essential assumption is the vector space structure of the feasible set. This condition is not fulfilled if we consider optimisation problems over the sphere. We present an algorithm for solving a special global problem over the sphere, namely the determination of Frechet means, which are points minimising the mean distance … Read more
Mixed-integer second-order cone optimization (MISOCO) has become very popular in the last decade. Various aspects of solving these problems in Branch and Conic Cut (BCC) algorithms have been studied in the literature. This study aims to fill a gap and provide a novel way to find feasible solutions early in the BCC algorithm. Such solutions … Read more
The quadratic shortest path problem is the problem of finding a path in a directed graph such that the sum of interaction costs over all pairs of arcs on the path is minimized. We derive several semidefinite programming relaxations for the quadratic shortest path problem with a matrix variable of order $m+1$, where $m$ is … Read more
The minimum $k$-enclosing ball problem seeks the ball with smallest radius that contains at least $k$ of $m$ given points in a general $n$-dimensional Euclidean space. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of $k$ points to solve this problem. The nodes on the tree are ordered … Read more
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 … Read more
Interior point methods (IPM) are the most popular approaches to solve Second Order Cone Optimization (SOCO) problems, due to their theoretical polynomial complexity and practical performance. In this paper, we present a warm-start method for primal-dual IPMs to reduce the number of IPM steps needed to solve SOCO problems that appear in a Branch and … Read more
In this article, we provide an overview of the current state of the art with respect to solution of mixed integer linear optimization problems (MILPS) in parallel. Sequential algorithms for solving MILPs have improved substantially in the last two decades and commercial MILP solvers are now considered effective off-the-shelf tools for optimization. Although concerted development … Read more
We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the … Read more
We consider the problem of minimization of the energy consumed by an electrical vehicle performing quite long travels with slopes. The model we address here, takes into account the electrical and mechanical differential equations of the vehicle. This yields a mixed-integer optimal control problem that can be approximated, using a methodology based on some decomposition … Read more
In this work we present a branch-and-bound (B&B) framework for the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS) and the node-weighted Steiner tree problem (NWSTP). The main component of … Read more