Formal Computer Science / Optimization

Kenton Labs / Optimization

Combinatorial optimization

Separate a feasible chosen subset from a certified best objective over all allowed choices.

The vocabulary.

These definitions state the objects and properties used by the dataset. The complete instance specification remains the authority for each result.

0/1 knapsack
Each item may be chosen at most once under a total weight limit.
Primal witness
A concrete feasible subset attaining a particular value.
Optimality
No other feasible subset has a larger objective.

How the dataset works.

Three deterministic instances define this family. Each includes its input model, a checked result, evidence, and an acceptance procedure. Download the complete dataset JSON ↘ or the area’s readable source ↘.

Acceptance procedure

  1. Enumerate every binary item-selection vector.
  2. Discard selections exceeding capacity.
  3. Compute each remaining total value.
  4. Check that the submitted subset is feasible and attains the maximum.

Cost and scope

n items produce 2ⁿ subsets. Pseudopolynomial dynamic programming offers a different tradeoff for integral capacity.

A common failure

The highest value-to-weight ratio can fail for indivisible 0/1 items.

Explore the mechanics.

Change a local input or follow the steps. The stored result and its scope remain attached to the downloadable record.

Worked records.

Three instances expose concrete claims and the artifacts that establish or refute them. Expand a record for the problem, checker reasoning, formal payload, and verification metadata.

KL-FCS-043
Combinatorial optimizationA four-item capacity decisionComplete subset enumeration · 16 candidates

The problem

Maximize total item value without exceeding the weight capacity.

The checked result

Maximum value: 11.

Each subset is a distinct candidate. The checker independently computes feasibility and objective, accepts any optimal witness, and rejects attractive but overweight selections.

Why the checker accepts it

  1. Enumerate every binary item-selection vector.
  2. Discard selections exceeding capacity.
  3. Compute each remaining total value.
  4. Check that the submitted subset is feasible and attains the maximum.

Formal specification

{
  "items": [
    [
      2,
      3
    ],
    [
      3,
      4
    ],
    [
      4,
      7
    ],
    [
      5,
      8
    ]
  ],
  "capacity": 7,
  "item_encoding": "[weight, value]; index identifies an indivisible item"
}

Claim and evidence

{
  "claim": {
    "maximum_value": 11
  },
  "witness": {
    "selected": [
      1,
      2
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 16 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

n items produce 2ⁿ subsets. Pseudopolynomial dynamic programming offers a different tradeoff for integral capacity.

Only this finite 0/1 instance is certified; no approximation ratio or measured solver speed is claimed.

A boundary to investigate

The highest value-to-weight ratio can fail for indivisible 0/1 items. Add assignment dual certificates, set cover, and branch-and-bound proof logs.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-044 ↘Related KL-FCS-045 ↘
KL-FCS-044
Combinatorial optimizationValue ties in a five-item knapsackComplete subset enumeration · 32 candidates

The problem

Maximize total item value without exceeding the weight capacity.

The checked result

Maximum value: 15.

Each subset is a distinct candidate. The checker independently computes feasibility and objective, accepts any optimal witness, and rejects attractive but overweight selections.

Why the checker accepts it

  1. Enumerate every binary item-selection vector.
  2. Discard selections exceeding capacity.
  3. Compute each remaining total value.
  4. Check that the submitted subset is feasible and attains the maximum.

Formal specification

{
  "items": [
    [
      1,
      2
    ],
    [
      2,
      4
    ],
    [
      3,
      4
    ],
    [
      4,
      6
    ],
    [
      5,
      9
    ]
  ],
  "capacity": 8,
  "item_encoding": "[weight, value]; index identifies an indivisible item"
}

Claim and evidence

{
  "claim": {
    "maximum_value": 15
  },
  "witness": {
    "selected": [
      0,
      1,
      4
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 32 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

n items produce 2ⁿ subsets. Pseudopolynomial dynamic programming offers a different tradeoff for integral capacity.

Only this finite 0/1 instance is certified; no approximation ratio or measured solver speed is claimed.

A boundary to investigate

The highest value-to-weight ratio can fail for indivisible 0/1 items. Add assignment dual certificates, set cover, and branch-and-bound proof logs.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-043 ↘Related KL-FCS-045 ↘
KL-FCS-045
Combinatorial optimizationSix items and a larger capacityComplete subset enumeration · 64 candidates

The problem

Maximize total item value without exceeding the weight capacity.

The checked result

Maximum value: 22.

Each subset is a distinct candidate. The checker independently computes feasibility and objective, accepts any optimal witness, and rejects attractive but overweight selections.

Why the checker accepts it

  1. Enumerate every binary item-selection vector.
  2. Discard selections exceeding capacity.
  3. Compute each remaining total value.
  4. Check that the submitted subset is feasible and attains the maximum.

Formal specification

{
  "items": [
    [
      2,
      5
    ],
    [
      2,
      4
    ],
    [
      3,
      6
    ],
    [
      4,
      7
    ],
    [
      5,
      11
    ],
    [
      1,
      1
    ]
  ],
  "capacity": 10,
  "item_encoding": "[weight, value]; index identifies an indivisible item"
}

Claim and evidence

{
  "claim": {
    "maximum_value": 22
  },
  "witness": {
    "selected": [
      0,
      2,
      4
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 64 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

n items produce 2ⁿ subsets. Pseudopolynomial dynamic programming offers a different tradeoff for integral capacity.

Only this finite 0/1 instance is certified; no approximation ratio or measured solver speed is claimed.

A boundary to investigate

The highest value-to-weight ratio can fail for indivisible 0/1 items. Add assignment dual certificates, set cover, and branch-and-bound proof logs.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-043 ↘Related KL-FCS-044 ↘

Go further.

Add assignment dual certificates, set cover, and branch-and-bound proof logs.

Questions to investigate

  1. The highest value-to-weight ratio can fail for indivisible 0/1 items.
  2. Which assumption in the specification can be changed to make the current evidence insufficient?
  3. Add assignment dual certificates, set cover, and branch-and-bound proof logs.

Conceptual references

These sources explain the surrounding theory. The linked material was not imported as a dataset, and these records do not claim checking by the source’s software.

Primary conceptual reference ↗

Related areas

Circuit minimizationSchedulingConstraint satisfaction