eigenvalue constraint

Computational study of a branching algorithm for the maximum k-cut problem

  • Miguel F. Anjos
  • Sébastien Le Digabel
  • Vilmar Jefté Rodrigues de Sousa
    • Categories Branch and Cut Algorithms, Graphs and Matroids, Semi-definite Programming Tags , , , ,

    This work considers the graph partitioning problem known as maximum k-cut. It focuses on investigating features of a branch-and-bound method to efficiently obtain global solutions. An exhaustive experimental study is carried out for two main components of a branch-and-bound algorithm: computing bounds and branching strategies. In particular, we propose the use of a variable neighborhood … Read more

    Improving the linear relaxation of maximum hBccut with semidefinite-based constraints

  • Miguel F. Anjos
  • Sébastien Le Digabel
  • Vilmar Jefté Rodrigues de Sousa
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We consider the maximum $k$-cut problem that involves partitioning the vertex set of a graph into $k$ subsets such that the sum of the weights of the edges joining vertices in different subsets is maximized. The associated semidefinite programming (SDP) relaxation is known to provide strong bounds, but it has a high computational cost. We … Read more