KthLargestMTuple ignores k and returns a count instead of the threshold decision

[isPANN]

Background

KthLargestMTuple is documented as the decision problem:

Are there at least k distinct m-tuples whose element sum is at least bound?

The original model issue #405 proposed representing each qualifying tuple as Sum(1) and comparing the final count with k externally. The implemented model performs the counting step, but no external threshold comparison is present in the model or deterministic solve output.

Problem

KthLargestMTuple::evaluate never reads self.k. It returns Sum(1) or Sum(0) for each tuple, so aggregate solving returns the exact number of qualifying tuples as Sum(count).

Consequently, instances that differ only in k are observationally identical:

• Example sets and bound = 12 have 14 qualifying tuples.
• With k = 14, the documented decision answer is YES.
• With k = 15, the documented decision answer is NO.
• The current solver returns Sum(14) for both instances.

The serialized input accepts and preserves k, but the field has no effect on evaluation or solve results. This makes the implementation inconsistent with the schema description, model documentation, and Garey & Johnson decision problem.

Evidence

The mismatch is in src/models/misc/kth_largest_m_tuple.rs:

impl Problem for KthLargestMTuple {
    type Value = Sum<u64>;

    fn evaluate(&self, config: &[usize]) -> Sum<u64> {
        // validates and scores the tuple against bound
        // self.k is never used
    }
}

The canonical example also records only the per-configuration value 1, while the model documentation describes the final YES/NO answer.

Expected behavior

The public model contract must represent one coherent problem:

1. If KthLargestMTuple remains the threshold decision problem, solving must use k and return the source-side YES/NO result for count >= k.
2. If exact counting is the intended model, remove k and rename/re-document the model as a counting problem.

Given the established Garey & Johnson name and schema, the first option matches the current declared interface.

Verification

Add a regression test using the documented 18-tuple example with 14 qualifying tuples:

• k = 14 returns YES.
• k = 15 returns NO.
• The two solve results must differ.

Also verify that changing only k can affect the dynamic CLI solve output.

Related

• [Model] KthLargestMTuple #405 introduced the model and explicitly mentioned an external comparison that is currently absent.
• [Rule] PARTITION to K-th LARGEST m-TUPLE #395 depends on the threshold semantics for the proposed PARTITION reduction.

[isPANN]

Fixed in 1122