Solving large-scale capital budgeting problems with column generation and optimization-based sorting

doi:10.1007/s10287-026-00569-2

Solving large-scale capital budgeting problems with column generation and optimization-based sorting

2026-05-01

0

PRE

AI

A

Aphisak Witthayapraphakorn

S

Sasarose Jaijit *

P

Peerayuth Charnsethikul

DOI：10.1007/s10287-026-00569-2

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Capital budgeting

Column generation

Optimization-based sorting

Large-scale optimization

Solving large-scale capital budgeting problems with column generation and optimization-based sorting

Abstract

Journal

Organization

Cited Papers