A few references where these instances are used
Given a valued graph G=(V,E) of n nodes and a number k, the problem is to find a subset S of V having a cardinality k and such that the induced subgraph is as dense as possible.
Each .dat file contains one instance, in the following format : Number of nodes, k, Number of edges, and then, for any edge [i,j] with i < j wij = 0.5 if and only if an edge links vertices i and j
n k nb_non_zero matrix W
W entriesThe optimal solution values are reported here
[1] A. Billionnet, S. Elloumi, A. Lambert and A. Wiegele. Using a conic bundle method to accelerate both phases of a quadratic convex reformulation Informs Journal on computing. 29 (2), 318-331 (2017) DOI: 10.1287/ijoc.2016.0731
[2] A. Billionnet , S. Elloumi , M. Plateau - Quadratic Convex Reformulation : a Computational Study of the Graph Bisection Problem, TR CEDRIC No 1003, 2006. (pdf)
[3] A. Billionnet - Different formulations for solving the heaviest k-subgraph problem, Information Systems and Operational Research, vol. 43(3), pp. 171-186, 2005
Back to Main page
Back to SMIQP
Back to Equipe OC
Back to CEDRIC