Heuristics for the minimum-weight $k$-clique problem
Your problem appears to be the minimization variant (flip the edge weight signs?) of the edge-weighted maximal clique problem. Check out this reference:


  @article{park1996extended,
  title={{An extended formulation
  approach to the edge-weighted maximal
  clique problem}},
  author={Park, K.
  and Lee, K. and Park, S.},
  journal={European Journal of
  Operational Research},
  volume={95}, 
  number={3},
  pages={671--682},
  year={1996},
  publisher={Elsevier} }


where they discuss various LP-based heuristics.