While useful probability bounds for \(n\) pairwise independent Bernoulli random variables adding up to at least an integer \(k\) have been proposed in the literature, none of these bounds are tight in general. In this paper, we provide several results in this direction. Firstly, when \(k = 1\), the tightest upper bound on the probability … Read more
Given a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called CliSAT, to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a … Read more
We consider the capacitated facility location problem with (partial) single-sourcing (CFLP-SS). A natural mixed integer formulation for the problem involves 0-1 variables x_j indicating whether faclility j is used or not and y_{ij} variables indicating the fraction of the demand of client i that is satisfied from facility j. When the x variables are fixed, … Read more
We investigate the complexity of finding small branch-and-bound trees using variable disjunctions. We first show that it is not possible to approximate the size of a smallest branch-and-bound tree within a factor of 2^(1/5) in time 2^(\delta n) with \delta < 1/5, unless the strong exponential time hypothesis fails. Similarly, for any \varepsilon > 0, … Read more
We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as … Read more
Neural networks tend to achieve better accuracy with training if they are larger — even if the resulting models are overparameterized. Nevertheless, carefully removing such excess parameters before, during, or after training may also produce models with similar or even improved accuracy. In many cases, that can be curiously achieved by heuristics as simple as … Read more
We present the Branch-and-Bound Performance Estimation Programming (BnB-PEP), a unified methodology for constructing optimal first-order methods for convex and nonconvex optimization. BnB-PEP poses the problem of finding the optimal optimization method as a nonconvex but practically tractable quadratically constrained quadratic optimization problem and solves it to certifiable global optimality using a customized branch-and-bound algorithm. By … Read more
We investigate the problem of optimizing a linear objective function over the set of all binary vectors of length n with bounded variation, where the latter is defined as the number of pairs of consecutive entries with different value. This problem arises naturally in many applications, e.g., in unit commitment problems or when discretizing binary … Read more
We propose a matheuristic approach to solve split delivery variants of the vehicle routing problem (VRP). The proposed method is based on the use of several mathematical programming components within an Iterated Local Search metaheuristic framework. In addition to well-known VRP local search heuristics, we include new types of improvement and perturbation strategies that are … Read more
In the last decade, decision diagrams (DDs) have been the basis for a large array of novel approaches for modeling and solving optimization problems. Many techniques now use DDs as a key tool to achieve state-of-the-art performance within other optimization paradigms, such as integer programming and constraint programming. This paper provides a survey of the … Read more