Daniele Catanzaro

On the exact separation of cover inequalities of maximum depth

  • Daniele Catanzaro
  • Stefano Coniglio
  • Fabio Furini
    • Categories 0-1 Programming, Cutting Plane Approaches, Dynamic Programming

    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

    A Class Representative Model for Pure Parsimony Haplotyping

  • Daniele Catanzaro
  • Martine LabbĂ©
  • Alessandra Godi
    • Categories (Mixed) Integer Linear Programming, Basic Sciences Applications Tags , ,

    Parsimonious haplotype estimation from aligned Single Nucleotide Polymorphism (SNP) fragments consists of finding the minimum number of haplotypes necessary to explain a given set of genotypes. This problem is known to be NP-Hard. Here we describe a new integer linear-programming model to tackle this problem based on the concept of class representatives, already used for … Read more