A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization

We introduce a unified framework for the study of multilevel mixed integer linear optimization problems and multistage stochastic mixed integer linear optimization problems with recourse. The framework highlights the common mathematical structure of the two problems and allows for the development of a common algorithmic framework. Focusing on the two-stage case, we investigate, in particular, … Read more

On the exact separation of cover inequalities of maximum depth

We investigate the problem of exactly separating cover inequalities of maximum depth and we develop a pseudo-polynomial-time algorithm for this purpose. Compared to the standard method based on the maximum violation, computational experiments carried out on knapsack and multi-dimensional knapsack instances show that, with a cutting-plane method based on the maximum-depth criterion, we can optimize … Read more

Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function … Read more

A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflict Graph

We study the Knapsack Problem with Conflict Graph (KPCG), a generalization of the Knapsack Problem in which a conflict graph specifies pairs of items (vertices of the graph) which cannot be simultaneously selected in a solution. The KPCG asks for determining a maximum-profit subset of items of total weight no larger than the knapsack capacity … Read more

The sharpest column: stabilizing column generation for the bin packing problem via a lexicographic pricer

In spite of being an extremely successful method to tackle mathematical programs involving a very large number of variables, Column Generation (CG) is known to suffer from stabilization issues which can slow down its convergence significantly. In this article, we propose a new parameter-free stabilization technique for CG based on solving a lexicographic pricing problem. … Read more

Discrete optimization methods to fit piecewise-affine models to data points

Fitting piecewise affine models to data points is a pervasive task in many scientific disciplines. In this work, we address the k- Piecewise Affine Model Fitting with Pairwise Linear Separability problem (k-PAMF-PLS) where, given a set of real points and the corresponding observations, we have to partition the real domain into k pairwise linearly separable … Read more

On the exact separation of rank inequalities for the maximum stable set problem

When addressing the maximum stable set problem on a graph G = (V,E), rank inequalities prescribe that, for any subgraph G[U] induced by U ⊆ V , at most as many vertices as the stability number of G[U] can be part of a stable set of G. These inequalities are very general, as many of … Read more

On the generation of cutting planes which maximize the bound improvement

We propose the bound-optimal cutting plane method. It is a new paradigm for cutting plane generation in Mixed Integer Programming allowing for the simultaneous generation of k cuts which, when added to the current Linear Programming elaxation, yield the largest bound improvement. By Linear Programming duality arguments and standard linearization techniques we show that, for … Read more

Coordinated cutting plane generation via multi-objective separation

In cutting plane methods, the question of how to generate the “best possible” set of cuts is both central and crucial. We propose a lexicographic multi-objective cutting plane generation scheme that generates, among all the maximally violated valid inequalities of a given family, an inequality that is undominated and maximally diverse w.r.t. the cuts that … Read more