[Rule] LongestCommonSubsequence to ILP

[zazabap]

Source: LongestCommonSubsequence
Target: ILP
Motivation: Enables solving LCS instances via ILP solvers; the match-pair formulation naturally encodes subsequence ordering as linear constraints.
Reference: Blum et al., 2021 — discusses ILP formulation with match-pair binary variables and conflict/no-crossing constraints for LCS (Section 2, ILP model); the match-pair ILP formulation for sequence problems is also described in Althaus et al., 2006 in the context of sequence alignment.

Reduction Algorithm

Notation:

• Source: $k = 2$ strings $s_1$ (length $n_1$) and $s_2$ (length $n_2$) over alphabet $\Sigma$
• Target: ILP with binary variables, linear constraints, and a maximize objective

Scope: This reduction handles the 2-string LCS case only.

Variable mapping:

For each pair of positions $(j_1, j_2)$ where $s_1[j_1] = s_2[j_2]$, create a binary variable:

$$m_{j_1, j_2} \in {0, 1}$$

meaning "position $j_1$ of $s_1$ is matched to position $j_2$ of $s_2$ in the common subsequence."

Total variables: $|M|$ where $M = {(j_1, j_2) : s_1[j_1] = s_2[j_2]}$, bounded by $n_1 \cdot n_2$.

Constraints:

1. Each position in $s_1$ matched at most once: for each $j_1 \in {0, \ldots, n_1-1}$,
   $$\sum_{j_2 : (j_1,j_2) \in M} m_{j_1, j_2} \leq 1$$

2. Each position in $s_2$ matched at most once: for each $j_2 \in {0, \ldots, n_2-1}$,
   $$\sum_{j_1 : (j_1,j_2) \in M} m_{j_1, j_2} \leq 1$$

3. Order preservation (no crossings): for all $(j_1, j_2), (j_1', j_2') \in M$ with $j_1 < j_1'$ and $j_2 > j_2'$,
   $$m_{j_1, j_2} + m_{j_1', j_2'} \leq 1$$

Objective: maximize $\sum_{(j_1,j_2) \in M} m_{j_1, j_2}$

Solution extraction: The matched positions with $m_{j_1,j_2} = 1$, sorted by $j_1$, give the characters of the LCS.

Size Overhead

Worst-case bounds (all characters match, i.e., $|M| = n_1 \cdot n_2$):

Target metric (code name)	Worst-case bound
num_vars	$n_1 \cdot n_2$
num_constraints	$n_1 + n_2 + \binom{n_1 \cdot n_2}{2}$

In overhead expression syntax (using source problem getters):

• num_vars = num_chars_first * num_chars_second
• num_constraints = num_chars_first + num_chars_second + (num_chars_first * num_chars_second) ^ 2

Note: the actual number of variables and crossing constraints depends on the input content (character matches), so these are upper bounds. The crossing constraint count $\binom{|M|}{2}$ is $O(n_1^2 \cdot n_2^2)$ in the worst case.

Validation Method

Closed-loop testing: solve LCS by brute-force, solve the reduced ILP, and verify that both give the same optimal objective. Test with varying alphabet sizes and string lengths, including edge cases (identical strings, no common characters, single-character alphabet).

Example

Source instance: $s_1$ = ABAC, $s_2$ = BACA, alphabet $\Sigma = {A, B, C}$.

Variables (6 match pairs):

Variable	$s_1$ pos	$s_2$ pos	Character
$m_{0,1}$	0	1	A
$m_{0,3}$	0	3	A
$m_{1,0}$	1	0	B
$m_{2,1}$	2	1	A
$m_{2,3}$	2	3	A
$m_{3,2}$	3	2	C

Constraints (13 total):

Assignment for $s_1$: $m_{0,1} + m_{0,3} \leq 1$, $m_{2,1} + m_{2,3} \leq 1$ (plus 2 trivial single-variable constraints).

Assignment for $s_2$: $m_{0,1} + m_{2,1} \leq 1$, $m_{0,3} + m_{2,3} \leq 1$ (plus 2 trivial).

No-crossing: $m_{0,1} + m_{1,0} \leq 1$, $m_{0,3} + m_{1,0} \leq 1$, $m_{0,3} + m_{2,1} \leq 1$, $m_{0,3} + m_{3,2} \leq 1$, $m_{2,3} + m_{3,2} \leq 1$.

Objective: maximize $m_{0,1} + m_{0,3} + m_{1,0} + m_{2,1} + m_{2,3} + m_{3,2}$

Optimal ILP solution: objective = 3, with $m_{1,0} = m_{2,1} = m_{3,2} = 1$ (all others 0).

Extracted LCS: $s_1[1] = s_2[0]$ = B, $s_1[2] = s_2[1]$ = A, $s_1[3] = s_2[2]$ = C → BAC (length 3), matching the brute-force LCS.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Source problem LongestCommonSubsequence does not exist in the codebase yet
Non-trivial	✅ Pass	Match-pair ILP formulation with ordering constraints is genuine structural transformation
Correctness	❌ Fail	Both cited references have DOI/content mismatches — see details
Well-written	⚠️ Warn	Overhead expressions use `

Overall: 1 passed, 1 failed, 2 warnings

---

Usefulness

The source problem LongestCommonSubsequence does not exist in the codebase (pred show LongestCommonSubsequence fails). This means the reduction rule cannot be implemented without first adding the LCS model. No existing path to ILP can be evaluated since the source node doesn't exist in the reduction graph.

Verdict: Pass on novelty (no existing path), but Warn — a [Model] issue for LCS should be filed and implemented first.

Non-trivial

The reduction constructs binary match-pair variables $m_{j_1,j_2}$ for character-matching positions, introduces assignment constraints (each position matched at most once), and ordering/no-crossing constraints. This is a genuine ILP formulation involving new variables and structural constraints — not a trivial relabeling or type coercion. Pass.

Correctness

Reference 1: Lancia et al., 2001 (DOI 10.1007/3-540-44676-1_16)

This DOI resolves to Chapter 16 in the ESA 2001 proceedings (Springer LNCS). The paper by Lancia, Carr, Walenz, and Istrail is titled "1001 Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap" — it's about protein contact map overlap, not the basic Longest Common Subsequence problem. While the contact map overlap problem uses a related ILP formulation with match-pair variables, it is a different (more constrained) problem. The issue cites this as a reference for the plain LCS→ILP reduction, which is a mismatch.

Reference 2: Althaus et al., 2006 (DOI 10.1007/s10107-006-0016-x)

This DOI could not be resolved in any search. The actual paper by Althaus, Caprara, Lenhof, and Reinert ("A branch-and-cut algorithm for multiple sequence alignment") has DOI 10.1007/s10107-005-0659-3. Furthermore, this paper is about multiple sequence alignment with arbitrary gap costs, not about the standard LCS→ILP formulation. The issue describes it as "general ILP formulations for sequence alignment" which is loosely related but does not directly establish the match-pair formulation presented.

The ILP formulation itself (match-pair binary variables with assignment and no-crossing constraints) is a well-known, standard construction — see e.g. Santini, Blum & Djukanovic (2021) who discuss this formulation explicitly. The issue should cite a reference that directly establishes this specific formulation.

Verdict: Fail — both citations have DOI errors or content mismatches. Replace with references that directly describe the match-pair ILP formulation for LCS.

Well-written

Sections: All required sections (Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation, Example) are present and substantive. ✓

Algorithm completeness: The step-by-step procedure is detailed and implementable — variable mapping, constraints, objective, and solution extraction are all clearly specified. ✓

Symbol consistency: All symbols ($k$, $n_1$, $n_2$, $M$, $m_{j_1,j_2}$) are defined before use and consistent across sections. ✓

Size overhead issue: The num_constraints formula uses $|M|$ (the number of character-match pairs), which is a runtime quantity depending on input content, not a structural dimension of the source problem. The overhead should be expressed as a worst-case closed-form bound: in the worst case $|M| = n_1 \cdot n_2$, so the crossing constraints number $\binom{n_1 \cdot n_2}{2}$. The overhead table should read:

• num_vars = num_chars_first * num_chars_second (worst case)
• num_constraints = num_chars_first + num_chars_second + (num_chars_first * num_chars_second)^2 (worst case, from $\binom{|M|}{2}$)

Example quality: Excellent — fully worked with 4-character strings, all 6 match pairs, 13 constraints enumerated, and the optimal solution verified against brute-force. ✓

Note on general $k$: The issue mentions a general $k$-string extension in passing but the algorithm is specified for $k = 2$ only. This is fine for a first implementation, but should be explicitly scoped as "2-string LCS only" in the issue title or definition.

Recommendations

• File a [Model] issue for LongestCommonSubsequence first — this rule depends on it
• Replace citations with references that directly describe the match-pair ILP for LCS (e.g., the formulation in Blum & Blesa, 2005 or textbook ILP formulations)
• Express overhead bounds as worst-case closed-form expressions using source problem getter names

[zazabap]

Issue Quality Re-Check — Rule (post-correction)

Check	Result	Details
Usefulness	⚠️ Warn	Source problem LongestCommonSubsequence does not yet exist in the codebase
Non-trivial	✅ Pass	Match-pair ILP formulation with assignment + ordering constraints
Correctness	⚠️ Warn	Both DOIs now resolve correctly; minor mismatch on what Blum et al. Section 2 contains
Well-written	✅ Pass	All sections present, algorithm complete, example fully worked

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

pred show LongestCommonSubsequence still fails — the source model does not exist in the codebase. A [Model] issue for LCS must be filed and implemented before this rule can be added. No existing path to ILP exists (novel reduction). Pass on novelty, Warn on dependency.

Non-trivial

The reduction constructs binary match-pair variables, assignment constraints (each string position matched at most once), and order-preservation/no-crossing constraints. This is a genuine structural ILP formulation — not a trivial relabeling, subtype coercion, or identity. Pass.

Correctness

Reference 1: Blum et al., 2021 — DOI resolves correctly to "Solving longest common subsequence problems via a transformation to the maximum clique problem" in Computers & Operations Research 125, 105089. However, the issue claims this paper "discusses ILP formulation with match-pair binary variables and conflict/no-crossing constraints for LCS (Section 2, ILP model)." In reality, Section 2 describes the conflict graph transformation (LCS → MIS/MaxClique), not an ILP model directly. The ILP solver CPLEX is used as a comparison baseline (solving MIS on the conflict graph). The conflict graph encodes the same match-pair structure with conflict edges for crossings, so the connection is valid, but the characterization "Section 2, ILP model" overstates what the paper contains.

The actual ILP models for classical LCS are attributed in this paper to Lee et al. (2009) — this would be the more precise reference for the match-pair ILP formulation.

Reference 2: Althaus et al., 2006 — DOI now resolves correctly to "A branch-and-cut algorithm for multiple sequence alignment" in Mathematical Programming 105, 387–425. The paper is about MSA with gap costs (a generalization of pairwise sequence alignment), not specifically about 2-string LCS. The description "match-pair ILP formulation for sequence problems" is a reasonable but loose characterization. Exists and is related, but tangential.

The formulation itself (match-pair binary variables with assignment and no-crossing constraints) is mathematically correct and well-established in the literature. No factual errors in the reduction algorithm.

Verdict: Warn — both papers exist with correct DOIs and are related, but neither directly establishes the specific match-pair ILP for 2-string LCS. Consider adding Lee et al. (2009) as the primary reference.

Well-written

All required sections are present and substantive:

• Source/Target: ✓ Valid problem names
• Motivation: ✓ Concrete ("enables solving LCS via ILP solvers")
• Reference: ✓ Two citations with working DOIs
• Reduction Algorithm: ✓ Complete step-by-step with variable mapping, constraints, objective, solution extraction
• Size Overhead: ✓ Worst-case bounds with getter-style expressions (num_chars_first, num_chars_second); code metric names num_vars and num_constraints match ILP's size_fields
• Scope: ✓ Explicitly limited to 2-string case
• Validation Method: ✓ Closed-loop with edge cases specified
• Example: ✓ Fully worked — 4-char strings, 6 match pairs, 13 constraints enumerated, optimal solution BAC (length 3) verified

Minor note: The overhead expression (num_chars_first * num_chars_second) ^ 2 overapproximates the crossing constraint count by ~2× (actual worst case is $\binom{n_1 n_2}{2} \approx (n_1 n_2)^2 / 2$). This is acceptable as an upper bound for the overhead system.

Pass.

Recommendations

• Add Lee et al. (2009) as the primary reference for the ILP models for classical LCS (cited within Blum et al. 2021)
• Refine the Blum et al. citation to say "describes the equivalent conflict graph formulation for LCS" rather than "Section 2, ILP model"
• File a [Model] issue for LongestCommonSubsequence as a prerequisite

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Source (LCS) not yet in codebase; novel reduction
Non-trivial	✅ Pass	Match-pair variables with assignment + no-crossing constraints
Correctness	⚠️ Warn	References are tangential — neither directly describes this ILP formulation
Well-written	⚠️ Warn	2-string LCS is polynomial-time; overhead formula is loose

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

LongestCommonSubsequence does not exist in the codebase, so this is a novel reduction. Requires implementing the LCS model first.

Note: 2-string LCS is solvable in O(n₁·n₂) by dynamic programming — it's a polynomial-time problem. Reducing a poly-time problem to NP-hard ILP has limited practical value. Consider expanding scope to k-string LCS (NP-hard for k ≥ 3) where an ILP formulation would be more compelling.

Non-trivial

Creates binary match-pair variables from position alignments, constructs assignment constraints (each position matched at most once), no-crossing constraints (order preservation), and a maximization objective. Solution extraction requires sorting matched positions. Genuine structural transformation.

Correctness — WARN

Reference	Status	Notes
Blum et al. (2021), Comp. & Ops. Research	⚠️ Tangential	Paper is about LCS-to-Maximum Clique transformation. The ILP formulation is a secondary solver technique, not the paper's primary contribution.
Althaus et al. (2006), Math. Programming	⚠️ Tangential	Addresses multiple sequence alignment, a related but distinct problem.

The ILP formulation itself (match-pair variables, assignment constraints, no-crossing constraints) is mathematically correct and standard. The example was independently verified: s₁="ABAC", s₂="BACA" → LCS="BAC" (length 3) via 6 match-pair variables and 13 constraints.

Recommendation: Find a more direct reference for the match-pair ILP formulation of LCS. Consider citing a combinatorial optimization textbook (e.g., Schrijver's "Combinatorial Optimization") or an OR survey on sequence ILP formulations.

Well-written — WARN

All sections present with good example quality.

Issues:

• Overhead formula num_constraints = num_chars_first + num_chars_second + (num_chars_first * num_chars_second)^2 overstates worst-case crossing constraints by ~2× (actual: C(|M|,2) ≈ (n₁·n₂)²/2)
• Source getter names (num_chars_first, num_chars_second) reference a not-yet-existing model — acceptable but needs validation when LCS model is created

Recommendations

• Consider expanding to k-string LCS (NP-hard) to strengthen the motivation
• Find a more direct reference for the ILP formulation
• Tighten the overhead bound for crossing constraints

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Source problem LongestCommonSubsequence does not exist in the codebase yet — requires a new model first
Non-trivial	✅ Pass	Genuine structural transformation: constructs ILP variables from character match pairs with ordering constraints
Correctness	⚠️ Warn	Cited papers exist but do not directly describe the claimed ILP formulation (see details)
Well-written	⚠️ Warn	Generally complete; overhead formula is a loose upper bound (see details)

Overall: 1 passed, 3 warnings, 0 failed

---

Usefulness

The source problem LongestCommonSubsequence is not yet implemented in the reduction graph (pred show LongestCommonSubsequence fails). This means a [Model] issue and implementation for LCS must be completed before this rule can be implemented. Assuming the model is added, this is a novel reduction — no existing path from LCS to ILP exists. Pass (novel reduction), with the caveat that the source model is a prerequisite.

Non-trivial

The reduction performs genuine structural transformation: it constructs ILP binary variables from character match pairs, builds assignment constraints (one-match-per-position), and generates no-crossing constraints for order preservation. This is not a trivial relabeling or subtype coercion. Pass.

Correctness

Reference 1: Blum et al., 2021 (DOI: 10.1016/j.cor.2020.105089)

• The paper exists: "Solving longest common subsequence problems via a transformation to the maximum clique problem" by Santini, Blum, and Djukanovic, Computers & Operations Research, 125, 2021.
• Issue claim: "discusses ILP formulation with match-pair binary variables and conflict/no-crossing constraints for LCS (Section 2, ILP model)."
• Actual content: The paper transforms LCS instances into maximum clique problem instances via a conflict graph construction. While an ILP solver (CPLEX) is applied to solve the resulting independent set problem, the paper does not present a direct ILP formulation for LCS with the specific constraint structure described in the issue. The match-pair concept is present in the conflict graph construction, but framed as a graph problem, not as the standalone ILP formulation described here.
• Verdict: The citation is misleading. The paper supports the general idea of match-pair variables but does not contain the specific "ILP model" claimed.

Reference 2: Althaus et al., 2006 (DOI: 10.1007/s10107-005-0659-3)

• The paper exists: "A branch-and-cut algorithm for multiple sequence alignment" by Althaus, Caprara, Lenhof, and Reinert, Mathematical Programming, 105, 2006.
• Issue claim: "the match-pair ILP formulation for sequence problems is also described in [Althaus et al., 2006] in the context of sequence alignment."
• Actual content: This paper addresses the multiple sequence alignment (MSA) problem with arbitrary gap costs using branch-and-cut. While related to sequence comparison, MSA is a distinct problem from LCS, and the ILP formulation uses a different model (pairwise alignment variables with gap costs, not the match-pair no-crossing formulation for LCS).
• Verdict: The citation is tangentially related but does not directly support the specific ILP formulation described in the issue.

Note on the ILP formulation itself: The match-pair ILP formulation for 2-string LCS described in the issue is mathematically correct and well-known in the combinatorial optimization community. It follows naturally from modeling LCS as a maximum weight independent set in a conflict graph (which is the connection to Blum et al.). However, the issue should cite a reference that directly presents this ILP formulation, or acknowledge that it is derived from the conflict graph construction.

Well-written

Strengths:

• Algorithm is clearly specified with numbered steps, all symbols defined
• Example is well-worked with 4-character strings, showing all 6 match pairs, 13 constraints, and optimal solution
• The example was verified: 4 s1-assignment + 4 s2-assignment + 5 no-crossing = 13 constraints, optimal objective = 3 (BAC) — all correct
• Validation method is appropriate (closed-loop brute-force comparison)

Issues found:

1. Overhead formula is a loose upper bound: The issue states num_constraints = num_chars_first + num_chars_second + (num_chars_first * num_chars_second) ^ 2. The actual worst-case crossing constraint count is C(|M|, 2) = |M|(|M|-1)/2 where |M| = n1n2, which is approximately (n1n2)^2/2. The formula (n1n2)^2 overestimates by roughly 2x. While acceptable as an upper bound for overhead expressions, it could be tightened to (num_chars_first * num_chars_second)^2 / 2 or noted as an asymptotic bound.

2. Source problem getters unverified: The overhead expressions use num_chars_first and num_chars_second as getter names, but since the LongestCommonSubsequence model does not yet exist, these getter names cannot be validated against actual methods. They should be confirmed when the model is implemented.

3. Scope limitation could be more prominent: The "Scope: This reduction handles the 2-string LCS case only" note is good but could be reflected in the title or a more prominent location.

Recommendations

• Replace or supplement the Blum et al. citation with a reference that directly presents the match-pair ILP for LCS, or explicitly note that the ILP is derived from the conflict graph formulation in Blum et al.
• Consider tightening the overhead formula for num_constraints to use (num_chars_first * num_chars_second) * (num_chars_first * num_chars_second - 1) / 2 for the crossing term.
• Implement the LongestCommonSubsequence model first (file a [Model] issue if one does not exist).