Alberto Costa

Complete mixed integer linear programming formulations for modularity density based clustering

  • Alberto Costa
  • Lin Xuan Foo
  • Tsan Sheng Ng
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Nonlinear Optimization

    Modularity density maximization is a clustering method that improves some issues of the commonly-used modularity maximization approach. Recently, some Mixed-Integer Linear Programming (MILP) reformulations have been proposed in the literature for the modularity density maximization problem, but they require as input the solution of a set of auxiliary binary Non-Linear Programs (NLPs). These can become … Read more

    Divisive heuristic for modularity density maximization

  • Alberto Costa
  • Leo Liberti
  • Sergey Kushnarev
  • Zeyu Sun
    • Categories (Mixed) Integer Linear Programming, Network Optimization Tags , , , ,

    In this paper we consider a particular method of clustering for graphs, namely the modularity density maximization. We propose a hierarchical divisive heuristic which works by splitting recursively a cluster into two new clusters by maximizing the modularity density, and we derive four reformulations for the mathematical programming model used to obtain the optimal splitting. … Read more

    MILP formulations for the modularity density maximization problem

  • Alberto Costa
    • Categories (Mixed) Integer Linear Programming, Network Optimization

    Cluster analysis refers to finding subsets of vertices of a graph (called clusters) which are more likely to be joined pairwise than vertices in different clusters. In the last years this topic has been studied by many researchers, and several methods have been proposed. One of the most popular is to maximize the modularity, which … Read more

    RBFOpt: an open-source library for black-box optimization with costly function evaluations

  • Alberto Costa
  • Giacomo Nannicini
    • Categories Bound-constrained Optimization, Global Optimization, Optimization Software and Modeling Systems

    We consider the problem of optimizing an unknown function given as an oracle over a mixed-integer box-constrained set. We assume that the oracle is expensive to evaluate, so that estimating partial derivatives by finite differences is impractical. In the literature, this is typically called a black-box optimization problem with costly evaluation. This paper describes the … Read more

    Reformulation of a model for hierarchical divisive graph modularity maximization

  • Sonia Cafieri
  • Alberto Costa
  • Pierre Hansen
    • Categories Convex Optimization, Network Optimization, Quadratic Programming Tags , , ,

    Finding clusters, or communities, in a graph, or network is a very important problem which arises in many domains. Several models were proposed for its solution. One of the most studied and exploited is the maximization of the so called modularity, which represents the sum over all communities of the fraction of edges within these … Read more

    On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square

  • Alberto Costa
  • Pierre Hansen
  • Leo Liberti
    • Categories Combinatorial Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    We study the problem of packing equal circles in a square from the mathematical programming point of view. We discuss different formulations, we analyse formulation symmetries, we propose some symmetry breaking constraints and show that not only do they tighten the convex relaxation bound, but they also ease the task of local NLP solution algorithms … Read more