Oh, actually, I think you want the smallest ones last, if anything? (Or is my guess for getting mildly better performance out of greedy knapsack selection off the mark?)
Is this about optimising for the last few transactions in a block, or choosing a canonical ordering so there’s less uncertainty/ambiguity, or something else?
You can’t get a strictly unique “perfect” linearisation, since if you have txs A, B, C, C spending A and B, and A,B having equal fee and size, but lower feerate than C, then [ABC] and [BAC] are equally good linearisations. You could break the tie by resorting to your arbitrary order R_2, of course, but that’s still picking a winner arbitrarily…
Your definition of opt seems weird? Shouldn’t that just be \operatorname{opt}(G) = L_G + \operatorname{opt}(G \setminus S_G) where S_G is the highest-feerate subset of G and L_G is the first valid linearisation of S_G?
I would have proven the uniqueness claim non-constructively: set f(L) = |\{L_2 | L \ge L2\}|. Pick a linearisation L_x where f(L_x) \ge f(L) for all L. If this value equals the count of all linearisations, then L_x \ge L for all L, so L_x is an optimal linearisation. If it’s not the case, then there is some L_y where L_x \not\ge L_y, so calculate L_z = \operatorname{merge}(L_x, L_y) which gives us L_z \ge L_x but also L_z \ge L_y. But for any L where L_x \ge L, L_z \ge L by transitivity, so f(L_z) \gt f(L_x) which contradicts our choice of L_x.