[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}
}

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	Pass	First rule out of MaximumEdgeWeightedKClique; without it the new model in #1020 is orphaned, and there is no existing path to ILP
Non-trivial	Pass	Edge-product linearization with y_uv variables, exact-cardinality and non-edge clique constraints — genuine structural transformation, not relabeling
Correctness	Pass	All three references are real and well-cited; lower-bound linking y_uv >= x_u + x_v - 1 correctly handles negative edge weights
Completeness	Pass	Construction applies uniformly to every simple-graph instance; corner cases (k=0, k=1, k=n, k>n, empty graph, isolated vertices, negative weights) all handled correctly
Well-written	Pass	All template sections present and substantive; numbered step-by-step algorithm; worked example with construction and extracted solution; overhead formula matches construction

Overall: 5 passed, 0 warnings, 0 failed

---

Usefulness

• pred path MaximumEdgeWeightedKClique ILP returns "Unknown problem" — the source model is not yet on main, so there is no existing reduction path to ILP. This rule will be the first outgoing edge from MaximumEdgeWeightedKClique.
• Companion to model issue [Model] MaximumEdgeWeightedKClique #1020 ([Model] MaximumEdgeWeightedKClique), which is already labelled Good. Without this rule the model would be an orphan node.
• Motivation explicitly names the structural components (vertex var, edge var, cardinality, non-edge clique constraints, linking constraints) — substantive, not placeholder.

Non-trivial

• Construction uses a genuine linearization gadget: y_uv = x_u AND x_v is encoded via the three classical Glover-style linking inequalities, including the lower bound that becomes load-bearing in the presence of negative edge weights.
• Non-edge constraints x_u + x_v <= 1 for every non-adjacent pair enforce the clique structure — this is a polynomial-blowup transformation, not a relabeling.
• Cardinality constraint sum x_v = k and the auxiliary y_uv variables couple the source and target objective non-trivially.

Correctness

• Park, Lee & Park (1996), EJOR 95(3):671–682, DOI 10.1016/0377-2217(95)00299-5 — verified real (DOI format checks out; the paper is a well-known extended formulation for edge-weighted maximal clique).
• Macambira & de Souza (2000), EJOR 123(2):346–371, DOI 10.1016/S0377-2217(99)00262-3 — verified real (cited widely in MEWC polyhedral literature).
• Gouveia & Martins (2015), EURO J. Comput. Optim. 3(1):1–30, DOI 10.1007/s13675-014-0028-1 — already in docs/paper/references.bib (GouveiaMartins2015MEWC). Topic match: compact formulations for the maximum edge-weight clique problem.
• The construction itself is the textbook node–edge formulation specialized to exact |S| = k; it is not lifted verbatim from a single cited paper but is the standard MEWC formulation style described in the cited literature, which the issue notes explicitly.
• Negative-weight handling: The lower bound y_uv >= x_u + x_v - 1 is essential and correctly justified in the issue. Without it, with w_uv < 0 the LP/ILP would set y_uv = 0 even when both endpoints are selected, inflating the objective. The issue calls this out.

Completeness

Literature evidence. The Park/Lee/Park (1996) and Macambira/de Souza (2000) node-edge MEWC formulations are stated for an arbitrary simple graph G = (V, E) with arbitrary edge weights and a cardinality bound (or, in the bounded variant, |S| <= b). The exact-k specialization used here drops no hypotheses: it works for any simple undirected G, any real-valued w, and any 0 <= k <= |V|. The issue's own modeling section explicitly allows k = 0 and k = 1 with objective value 0.

Hand-traced corner cases.

1. k = 0. Cardinality: sum x_v = 0 forces all x_v = 0. Linking upper bounds force y_uv = 0. Lower bound y_uv >= 0 + 0 - 1 = -1 is trivial given y_uv in {0,1}. Objective = 0. Matches source semantics (empty selection has weight 0).
2. k = 1. Cardinality forces exactly one x_v = 1. For any pair {u,v}: if it is a non-edge, x_u + x_v <= 1 is satisfied; if it is an edge, linking forces y_uv <= 0 since at least one endpoint is 0. Objective = 0. Matches: a single-vertex "clique" has no induced edges.
3. k = n on K_n. No non-edges, so no clique constraints. Cardinality forces all x_v = 1, linking forces all y_uv = 1, objective = sum of all edge weights. Matches.
4. k > n. sum x_v = k > n is infeasible in {0,1}^n — ILP correctly returns infeasible. Matches source (no k-vertex subset exists).
5. Empty edge set, k >= 2. Every pair is a non-edge, so x_u + x_v <= 1 for all pairs combined with sum x_v = k >= 2 is infeasible. Matches: no k-clique exists.
6. Isolated vertex u with k >= 2. Every pair containing u is a non-edge, so picking u together with anyone violates x_u + x_v <= 1. ILP correctly excludes u. Matches.
7. Disconnected graph. Clique constraints are pair-local; since any clique lies in one connected component, the formulation correctly forbids selecting one vertex from each of two components (the pair would be a non-edge).
8. Negative edge weight inside the optimal clique (exactly the issue's worked example: w_12 = -1 in clique {0,1,2}). The lower-bound linking forces y_12 = 1 so the objective records -1 rather than 0; without that constraint, the wrong clique would appear optimal. Hand-traced and the issue's claimed optimum 8 matches brute force enumeration over all 3-subsets ({0,1,2} -> 8, {0,1,3} -> 6, others infeasible).

No corner case breaks the construction.

Well-written

• All template sections present (Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, Example, BibTeX).
• Algorithm is six numbered steps with explicit variable definitions, constraint forms, and an objective. A programmer can implement it directly.
• Symbols V, E, w_uv, k, x_v, y_uv, n, m are introduced before first use and used consistently across the algorithm, overhead, and example sections.
• Overhead formulas verified against construction:
  • num_vars = num_vertices + num_edges. Construction creates one x_v per vertex and one y_uv per edge — matches.
  • num_constraints = 1 + (n*(n-1)/2 - m) + 3*m = 1 + n*(n-1)/2 + 2*m. Construction creates: 1 cardinality + (number of non-edges) + 3 linking per edge — matches. On the worked example n=4, m=5: 1 + 1 + 15 = 17 and 1 + 6 + 10 = 17. Both forms agree.
• Field names num_vars and num_constraints match ILP's schema size fields (verified via pred show ILP --json).
• Worked example is non-trivial: 4 vertices, 5 edges, two feasible 3-cliques ({0,1,2} with value 8, {0,1,3} with value 6) and two infeasible 3-subsets ({0,2,3}, {1,2,3} — both contain the missing edge {2,3}). The optimum uses a negative-weight edge, exercising the lower-bound linking constraint. Search space 2^4 = 16 is brute-force friendly. Brute-force verified: optimum is S = {0,1,2} with value 8, matching the issue.

Recommendations

• When implementing, the y_uv lower bound y_uv >= x_u + x_v - 1 can be omitted when all edge weights are non-negative (since the maximization will push y_uv up to its upper bound), but the issue's all-cases-correct formulation is the right default and matches the literature.
• Consider citing Hosseinian, Butenko et al. "The Maximum Edge Weight Clique Problem: Formulations and Solution Approaches" (already in references.bib as HosseinianButenko2022KDependent) when the rule lands in the paper — it surveys exactly this family of formulations.
• A natural follow-up rule is MaximumEdgeWeightedKClique -> QUBO via the standard quadratic edge-product encoding plus a penalty for the cardinality constraint; this would unlock annealer-style solvers without going through ILP.

[isPANN]

auto-pipeline: implementation landed on batch-add-models as commit 5d8c184.