Fabio Furini

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

  • Stefano Coniglio
  • Fabio Furini
  • Ivana Ljubić
    • Categories Cutting Plane Approaches, Integer Programming, Nonlinear Optimization Tags , ,

    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

  • Stefano Coniglio
  • Fabio Furini
  • Pablo San Segundo
    • Categories Combinatorial Optimization, Integer Programming

    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

    A Branch-and-Price Algorithm for the Minimum Sum Coloring Problem

  • Diego Delle Donne
  • Fabio Furini
  • Enrico Malaguti
  • Roberto Wolfler Calvo
    • Categories Combinatorial Optimization, Integer Programming

    A proper coloring of a given graph is an assignment of colors (integer numbers) to its vertices such that two adjacent vertices receives di different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for fi nding a proper coloring while minimizing the sum of the colors assigned to the vertices. This paper presents … Read more

    Casting light on the hidden bilevel combinatorial structure of the k-Vertex Separator problem

  • Fabio Furini
  • Ivana Ljubić
  • Enrico Malaguti
  • Paolo Paronuzzi
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Network Optimization

    Given an undirected graph, we study the capacitated vertex separator problem which asks to find a subset of vertices of minimum cardinality, the removal of which induces a graph having a bounded number of pairwise disconnected shores (subsets of vertices) of limited cardinality. The problem is of great importance in the analysis and protection of … Read more

    On Integer and Bilevel Formulations for the k-Vertex Cut Problem

  • Fabio Furini
  • Ivana Ljubić
  • Enrico Malaguti
  • Paolo Paronuzzi
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Network Optimization

    The family of Critical Node Detection Problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problems asks for determining the minimum weight subset of nodes whose removal disconnects a … Read more

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

  • Stefano Coniglio
  • Fabio D'Andreagiovanni
  • Fabio Furini
    • Categories Combinatorial Optimization, Integer Programming

    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

    Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Problems

  • Jean-François Cordeau
  • Fabio Furini
  • Ivana Ljubić
    • Categories Branch and Cut Algorithms, Combinatorial Optimization Tags , , , ,

    Covering problems constitute an important family of facility location problems. This paper intro- duces a new exact algorithm for two important members of this family: i) the maximal covering location problem, which requires finding a subset of facilities that maximizes the amount of demand covered while respecting a budget constraint on the cost of the … Read more

    The Maximum Clique Interdiction Problem

  • Fabio Furini
  • Ivana Ljubić
  • Sébastien Martin
  • Pablo San Segundo
    • Categories Graphs and Matroids, Integer Programming Tags , , ,

    Given a graph G and an interdiction budget k, the Maximum Clique Interdiction Problem asks to find a subset of at most k vertices to remove from G so that the size of the maximum clique in the remaining graph is minimized. This problem has applications in many areas, such as crime detection, prevention of … Read more

    The Vertex k-cut Problem

  • Denis Cornaz
  • Fabio Furini
  • Enrico Malaguti
  • Mathieu Lacroix
  • A. Ridha Mahjoub
  • Sébastien Martin
    • Categories Combinatorial Optimization, Graphs and Matroids, Integer Programming Tags , , ,

    Given an undirected graph G = (V, E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k connected components. Given a graph G and an integer k greater than or equal to two, the vertex k-cut problem consists in finding a vertex … Read more

    QPLIB: A Library of Quadratic Programming Instances

  • Pietro Belotti
  • Antonio Frangioni
  • Fabio Furini
  • Ambros Gleixner
  • Nicholas I. M. Gould
  • Leo Liberti
  • Andrea Lodi
  • Hans D Mittelmann
  • Ruth Misener
  • Nikolaos Sahinidis
  • Emiliano Traversi
  • Stefan Vigerske
  • Angelika Wiegele
    • Categories Quadratic Programming

    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