Mining for diamonds – matrix generation algorithms for binary quadratically constrained quadratic problems

In this paper, we consider binary quadratically constrained quadratic problems and propose a new approach to generate stronger bounds than the ones obtained using the Semidefinite Programming relaxation. The new relaxation is based on the Boolean Quadric Polytope and is solved via a Dantzig-Wolfe Reformulation in matrix space. For block-decomposable problems, we extend the relaxation … Read more

An exact algorithm for robust influence maximization

We propose a Branch-and-Cut algorithm for the robust influence maximization problem. The influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum number of other actors. We assume that the social network is given in the form of a graph with … Read more

Convex optimization under combinatorial sparsity constraints

We present a heuristic approach for convex optimization problems containing sparsity constraints. The latter can be cardinality constraints, but our approach also covers more complex constraints on the support of the solution. For the special case that the support is required to belong to a matroid, we propose an exchange heuristic adapting the support in … Read more

A Benders squared (B2) framework for infinite-horizon stochastic linear programs

We propose a nested decomposition scheme for infinite-horizon stochastic linear programs. Our approach can be seen as a provably convergent extension of stochastic dual dynamic programming to the infinite-horizon setting: we explore a sequence of finite-horizon problems of increasing length until we can prove convergence with a given confidence level. The methodology alternates between a … Read more

A simplicial decomposition framework for large scale convex quadratic programming

In this paper, we analyze in depth a simplicial decomposition like algorithmic framework for large scale convex quadratic programming. In particular, we first propose two tailored strategies for handling the master problem. Then, we describe a few techniques for speeding up the solution of the pricing problem. We report extensive numerical experiments on both real … Read more

Dantzig Wolfe decomposition and objective function convexification for binary quadratic problems: the cardinality constrained quadratic knapsack case

The purpose of this paper is to provide strong reformulations for binary quadratic problems. We propose a first methodological analysis on a family of reformulations combining Dantzig-Wolfe decomposition and Quadratic Convex Reformulation principles. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem, providing extensive experimental insights. We show that … Read more

QPLIB: A Library of Quadratic Programming Instances

This paper describes a new instance library for Quadratic Programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function, the constrains, or both are quadratic. QP is a very “varied” class of problems, comprising sub-classes of problems ranging from trivial to undecidable. Solution methods for QP are very diverse, ranging … Read more

Exact Approaches for the Knapsack Problem with Setups

We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We … Read more

On the Separation of Split Inequalities for Non-Convex Quadratic Integer Programming

We investigate the computational potential of split inequalities for non-convex quadratic integer programming, first introduced by Letchford and further examined by Burer and Letchford. These inequalities can be separated by solving convex quadratic integer minimization problems. For small instances with box-constraints, we show that the resulting dual bounds are very tight; they can close a … Read more

Extended Linear Formulation for Binary Quadratic Problems

In this work we propose and test a new linearisation technique for Binary Quadratic Problems (BQP). We computationally prove that the new formulation, called Extended Linear Formulation, performs much better than the standard one in practice, despite not being stronger in terms of Linear Programming relaxation (LP). We empirically prove that this behaviour is due … Read more