[Rule] MaximumEdgeWeightedKClique to ILP

[zhangjieqingithub]

Source

MaximumEdgeWeightedKClique

Target

ILP

Motivation

This is the natural first companion rule for MaximumEdgeWeightedKClique. Without it, the new model would be an orphan. The problem has a clean binary ILP formulation using:

• one variable per vertex,
• one variable per graph edge,
• one exact-cardinality constraint,
• clique validity constraints on non-edges, and
• linking constraints that make each edge variable equal to the product of its endpoint-selection variables.

Reference

• K. Park, K. Lee, S. Park, "An extended formulation approach to the edge-weighted maximal clique problem," European Journal of Operational Research 95(3):671-682, 1996. https://doi.org/10.1016/0377-2217(95)00299-5
• E. M. Macambira, C. C. de Souza, "The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations," European Journal of Operational Research 123(2):346-371, 2000. https://doi.org/10.1016/S0377-2217(99)00262-3
• L. Gouveia, P. Martins, "Solving the maximum edge-weight clique problem in sparse graphs with compact formulations," EURO Journal on Computational Optimization 3(1):1-30, 2015. https://doi.org/10.1007/s13675-014-0028-1

The construction below is the direct exact-k specialization of the standard edge/node formulation style used in the edge-weighted clique literature.

Reduction Algorithm

Let the source instance be:

• a simple undirected graph G = (V, E)
• edge weights w_uv for each edge {u,v} in E
• an integer k

Construct a binary ILP as follows.

1. For each vertex v in V, create a binary variable x_v.

   • x_v = 1 iff vertex v is selected.

2. Enforce exact cardinality:

   • sum_{v in V} x_v = k

3. For each unordered non-edge {u,v} with u != v and {u,v} notin E, add:

   • x_u + x_v <= 1

   This guarantees that no selected pair can be a non-edge, so every feasible selected set is a clique.

4. For each edge {u,v} in E, create a binary variable y_uv.

   • y_uv = 1 iff both endpoints are selected.

5. For each edge {u,v} in E, add the linking constraints:

   • y_uv <= x_u
   • y_uv <= x_v
   • y_uv >= x_u + x_v - 1

   Together these force y_uv = 1 exactly when x_u = x_v = 1.

6. Set the ILP objective to:

   • max sum_{ {u,v} in E } w_uv * y_uv

Correctness intuition:

• Step 2 enforces exactly k selected vertices.
• Step 3 ensures the selected vertices form a clique.
• Steps 4-5 ensure each y_uv records exactly whether edge {u,v} is induced by the selected clique.
• Therefore the objective equals the total edge weight of the selected k-clique.

The lower bound y_uv >= x_u + x_v - 1 is essential because edge weights may be negative. Without it, a negative-weight selected edge could be incorrectly set to 0.

Size Overhead

Let n = |V| and m = |E|.

Target metric	Formula
num_vars	num_vertices + num_edges
num_constraints	1 + (num_vertices * (num_vertices - 1) / 2 - num_edges) + 3 * num_edges

Equivalently,
num_constraints = 1 + num_vertices * (num_vertices - 1) / 2 + 2 * num_edges.

Validation Method

• Compare ILP optimum against brute-force enumeration on small graphs and all admissible values of k.
• Include cases with negative edge weights to verify that the y_uv >= x_u + x_v - 1 constraints are necessary.
• Check extracted solutions: selected vertices must form a clique of size exactly k.
• Verify that the ILP objective equals the sum of the weights of the induced clique edges.

Example

Take the source instance:

• V = {0,1,2,3}
• E = {{0,1}, {0,2}, {1,2}, {0,3}, {1,3}}
• weights:
  • w_01 = 5
  • w_02 = 4
  • w_12 = -1
  • w_03 = 1
  • w_13 = 0
• k = 3

Construction

Vertex variables:

• x_0, x_1, x_2, x_3

Edge variables:

• y_01, y_02, y_12, y_03, y_13

Cardinality constraint:

• x_0 + x_1 + x_2 + x_3 = 3

The only non-edge is {2,3}, so the clique constraint is:

• x_2 + x_3 <= 1

Linking constraints:

• for {0,1}:
  • y_01 <= x_0
  • y_01 <= x_1
  • y_01 >= x_0 + x_1 - 1
• for {0,2}:
  • y_02 <= x_0
  • y_02 <= x_2
  • y_02 >= x_0 + x_2 - 1
• for {1,2}:
  • y_12 <= x_1
  • y_12 <= x_2
  • y_12 >= x_1 + x_2 - 1
• for {0,3}:
  • y_03 <= x_0
  • y_03 <= x_3
  • y_03 >= x_0 + x_3 - 1
• for {1,3}:
  • y_13 <= x_1
  • y_13 <= x_3
  • y_13 >= x_1 + x_3 - 1

Objective:

• max 5 y_01 + 4 y_02 - y_12 + y_03 + 0 y_13

Optimal target solution

An optimal ILP solution is:

• x = (1,1,1,0)
• y_01 = 1
• y_02 = 1
• y_12 = 1
• y_03 = 0
• y_13 = 0

The objective value is:

• 5 + 4 - 1 = 8

This maps back to clique {0,1,2}, which is exactly the optimal source solution.

BibTeX

@article{ParkLeePark1996,
  author  = {Kyungchul Park and Kyungsik Lee and Sungsoo Park},
  title   = {An extended formulation approach to the edge-weighted maximal clique problem},
  journal = {European Journal of Operational Research},
  volume  = {95},
  number  = {3},
  pages   = {671--682},
  year    = {1996},
  doi     = {10.1016/0377-2217(95)00299-5},
  url     = {https://doi.org/10.1016/0377-2217(95)00299-5}
}

@article{MacambiraDeSouza2000,
  author  = {Elder Magalhaes Macambira and Cid Carvalho de Souza},
  title   = {The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations},
  journal = {European Journal of Operational Research},
  volume  = {123},
  number  = {2},
  pages   = {346--371},
  year    = {2000},
  doi     = {10.1016/S0377-2217(99)00262-3},
  url     = {https://doi.org/10.1016/S0377-2217(99)00262-3}
}

@article{GouveiaMartins2015MEWC,
  author  = {Luis Gouveia and Paulo Martins},
  title   = {Solving the maximum edge-weight clique problem in sparse graphs with compact formulations},
  journal = {EURO Journal on Computational Optimization},
  volume  = {3},
  number  = {1},
  pages   = {1--30},
  year    = {2015},
  doi     = {10.1007/s13675-014-0028-1},
  url     = {https://doi.org/10.1007/s13675-014-0028-1}
}