Scholarlink

<p>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 <i>k</i> in one pass. Computational experiments on randomly generated feasible instances (<i>N</i> = 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 <i>N</i> grows; for example, at <i>N</i> = 20 the explicit LP required 14.566&#xa0;s, whereas CGOS required 0.338&#xa0;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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月26日

查看全文
  • Aphisak Witthayapraphakorn,
  • Sasarose Jaijit,
  • Peerayuth Charnsethikul

摘要

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.