This study introduces column generation via optimization-based sorting (CGOS) for a proportional capital budgeting model with project-specific investment bounds and cardinality-based global limits. The underlying formulation contains an exponential number of investment-pattern constraints, which makes explicit enumeration impractical beyond moderate problem sizes. CGOS embeds an exact sorting-based pricing oracle within the column generation loop: a single sort of the dual-price vector, followed by prefix-sum evaluations, identifies improving upper- and lower-bound patterns for all k in one pass. Computational experiments on randomly generated feasible instances (N = 5–80) and a real-world participatory budgeting benchmark indicate that, in our test setting, CGOS is competitive on small instances and becomes faster than solving the explicit primal LP as N grows; for example, at N = 20 the explicit LP required 14.566 s, whereas CGOS required 0.338 s under the same settings. These results illustrate how exploiting pricing structure can improve the scalability of exact LP solution methods for this problem class. Because CGOS relies on a structured pricing oracle, extending it to formulations with nonlinearities, richer interdependencies, or dynamic constraints remains a topic for future research.
Witthayapraphakorn et al. (Tue,) studied this question.