The paper's method assigns non-negative prices to token occurrences, obtains a lower bound via shortest-path and vocabulary budget selection, recovers the LP relaxation by taking the maximum over prices, and certifies the values with an independent integer checker.