# Combinatorial optimization

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

## Definitions

- **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.

## 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.

## Complexity

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

## Common failure

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

## Extensions

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

## Instances

- KL-FCS-043: A four-item capacity decision — Maximum value: 11
- KL-FCS-044: Value ties in a five-item knapsack — Maximum value: 15
- KL-FCS-045: Six items and a larger capacity — Maximum value: 22

## References

- https://developers.google.com/optimization/assignment/linear_assignment