pith. sign in

arxiv: 2604.10850 · v1 · submitted 2026-04-12 · 🧮 math.OC

A study of column generation embedded in scalarization methods for the bi-objective cutting stock problem

Jennifer C. Borges , Helenice de O. Florentino , Socorro Rangel This is my paper

Pith reviewed 2026-05-10 15:09 UTC · model grok-4.3

classification 🧮 math.OC
keywords bi-objective cutting stock problemcolumn generationscalarization methodsPareto front approximationmulti-objective optimizationone-dimensional CSPtwo-dimensional CSPtrade-off analysis
0
0 comments X

The pith

Dynamic column generation embedded in scalarization methods improves Pareto front approximations for the bi-objective cutting stock problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the bi-objective cutting stock problem in one and two dimensions, where the goals are to minimize the total number of objects and the total number of saw cycles. It proposes embedding dynamic column generation inside scalarization methods that turn the multi-objective problem into a series of single-objective problems. Experiments show this dynamic approach produces better approximations to the Pareto front than standard column generation. The three scalarization methods act as complements: the combined set of points they generate always has more non-dominated solutions and greater hypervolume than the set from any one method alone.

Core claim

The central claim is that embedding dynamic column generation into scalarization methods for the bi-objective one-dimensional and two-dimensional cutting stock problem produces Pareto front approximations with higher quality than standard approaches, and that the union of the solution points obtained from the three different scalarization methods always yields fronts with strictly greater cardinality and hypervolume than those obtained from any single method.

What carries the argument

Dynamic column generation embedded in scalarization methods, which generates new cutting patterns on the fly while solving each weighted or epsilon-constrained single-objective integer program to explore trade-offs between object count and saw-cycle count.

If this is right

  • Decision makers gain access to a larger set of non-dominated trade-off solutions between material usage and production cycles.
  • Combining multiple scalarization methods produces a demonstrably stronger approximation than relying on any one method.
  • The same embedding strategy works for both the one-dimensional and two-dimensional variants of the cutting stock problem.
  • Industry obtains concrete computational tools that generate pragmatic solutions balancing the two objectives.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The complementarity result suggests that running several scalarization methods in parallel and merging their outputs may be a general tactic for improving Pareto approximations in other combinatorial problems.
  • The observed benefit of dynamic column generation could be tested on larger or more heterogeneous instance sets to check whether the advantage scales.
  • The generated fronts could be fed into downstream scheduling or inventory models to quantify real-world savings in material and machine time.

Load-bearing premise

That the dynamic column generation embedded in scalarization methods will consistently outperform standard column generation approaches on the full range of bi-objective cutting stock instances.

What would settle it

A new collection of bi-objective cutting stock instances on which the Pareto front approximations obtained without dynamic column generation show equal or greater cardinality and hypervolume than those obtained with dynamic column generation.

Figures

Figures reproduced from arXiv: 2604.10850 by Helenice de O. Florentino, Jennifer C. Borges, Socorro Rangel.

Figure 1
Figure 1. Figure 1: A two-stage orthogonal guillotine non-exact cutting pattern. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Dynamic versus Static Column Generation For all the instances displayed in [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Computational effort to obtain an FrA for the 1D-BOCSP relative to [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Approximation of the Pareto Front for the instance S/95 of the 1D-BOCSP with [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Computational effort to obtain an FrA for the 2D-BOCSP associated with [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Approximation of the Pareto front given by the methods [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗
read the original abstract

Research on multi-objective combinatorial optimization and on the Cutting Stock Problem (CSP) has been widely developed over the years. In contrast, the multi-objective Cutting Stock Problem has received limited attention and has been explored in only a small number of studies. In this paper a bi-objective study of the one-dimensional and the two-dimensional CSP is presented. It distinguishes itself from other research in the literature in two key aspects, among others. The first regards the model used to represent the problem and the second is the solution strategy based on dynamic column generation embedded into scalarization methods. Three methods adapted from the literature to analyse the trade-off between the minimization of the total number of objects and the total number of saw cycles are implemented. The computational results show that the use of dynamic column generation provides a better approximation of the Pareto front. As for the scalarization methods, none stood out. In fact, they can be viewed as complementary. The cardinality and hypervolume of an approximation of the Pareto front built from the union of the points generated by the three methods is always greater than the ones generated by each one. Dealing with the multi-objective nature of CSP, this study provides insights and computational tools to help industry obtain pragmatic solutions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 3 minor

Summary. The paper studies the bi-objective one- and two-dimensional cutting stock problem (CSP), minimizing the number of objects and the number of saw cycles. It embeds dynamic column generation inside three scalarization methods adapted from the literature and reports computational experiments claiming that dynamic column generation yields a superior Pareto-front approximation compared with standard approaches, while the three scalarizations are complementary: the union of their solution sets always produces strictly higher cardinality and hypervolume than any individual method.

Significance. If the experimental claims hold under properly documented instances and baselines, the work supplies concrete algorithmic tools and insights for obtaining pragmatic trade-off solutions in industrial CSP settings, an area that has received limited multi-objective attention. The explicit demonstration of complementarity via union metrics is a useful practical observation.

major comments (3)
  1. [§5] §5 (Computational Experiments): the central claim that dynamic column generation 'provides a better approximation of the Pareto front' is not yet load-bearing because the manuscript does not specify the exact non-dynamic baseline (standard CG with or without acceleration techniques?), the column-generation stopping criteria, time limits per scalarization, or the precise definition of 'better' (hypervolume, cardinality, or both). Without these details the observed improvement cannot be reproduced or generalized.
  2. [§5] §5, Table 2 and Table 3: the statement that the union 'is always greater' in cardinality and hypervolume requires explicit confirmation that dominated points are filtered and that the hypervolume reference point is fixed across all compared sets; otherwise the metric comparison is sensitive to implementation choices and may not support the complementarity conclusion.
  3. [§4.2–4.4] §4.2–4.4 (Scalarization Methods): the adaptation of the three scalarization methods to the bi-objective CSP is described at a high level; the precise weighting schemes, normalization constants, and how the dynamic column-generation subproblem is formulated for each scalarization (especially the objective coefficients passed to the pricing problem) are not given in sufficient detail to allow independent verification of the reported Pareto sets.
minor comments (3)
  1. [Abstract / §1] The abstract and introduction should cite the specific prior multi-objective CSP papers that the authors claim have received 'limited attention' so readers can assess novelty.
  2. [§2] Notation for the two-dimensional CSP (cutting patterns, saw cycles) is introduced without a consolidated table; a single notation table would improve readability.
  3. [§5] Figure captions for the Pareto-front plots should state the instance size, number of item types, and whether the plotted points are filtered for dominance.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive and detailed feedback on our manuscript. We address each major comment point by point below, providing clarifications where possible and committing to revisions that enhance reproducibility and clarity without altering the core claims.

read point-by-point responses

  1. Referee: [§5] §5 (Computational Experiments): the central claim that dynamic column generation 'provides a better approximation of the Pareto front' is not yet load-bearing because the manuscript does not specify the exact non-dynamic baseline (standard CG with or without acceleration techniques?), the column-generation stopping criteria, time limits per scalarization, or the precise definition of 'better' (hypervolume, cardinality, or both). Without these details the observed improvement cannot be reproduced or generalized.

    Authors: We agree that these implementation details are essential for reproducibility and to make the central claim load-bearing. In the revised manuscript, we will explicitly define the non-dynamic baseline as standard column generation without acceleration techniques. We will also specify the column-generation stopping criteria (no new columns generated for a fixed number of iterations or duality gap below 1e-4), the per-scalarization time limits used in the experiments, and clarify that 'better approximation' is measured by simultaneous improvements in both hypervolume and cardinality. These details will be added to Section 5. revision: yes

  2. Referee: [§5] §5, Table 2 and Table 3: the statement that the union 'is always greater' in cardinality and hypervolume requires explicit confirmation that dominated points are filtered and that the hypervolume reference point is fixed across all compared sets; otherwise the metric comparison is sensitive to implementation choices and may not support the complementarity conclusion.

    Authors: We acknowledge that explicit confirmation is required to support the complementarity conclusion. In the revised manuscript, we will add statements in Section 5 confirming that dominated points are filtered prior to metric computation and that a fixed reference point (the nadir point using the maximum objective values across all generated sets) is used consistently for all hypervolume calculations in Tables 2 and 3. This will eliminate sensitivity to implementation choices. revision: yes

  3. Referee: [§4.2–4.4] §4.2–4.4 (Scalarization Methods): the adaptation of the three scalarization methods to the bi-objective CSP is described at a high level; the precise weighting schemes, normalization constants, and how the dynamic column-generation subproblem is formulated for each scalarization (especially the objective coefficients passed to the pricing problem) are not given in sufficient detail to allow independent verification of the reported Pareto sets.

    Authors: We agree that greater precision is needed for independent verification. In the revised manuscript, we will expand Sections 4.2–4.4 to include the exact weighting schemes (including specific weight vectors or ranges for each scalarization), the normalization constants applied to each objective, and the full formulation of the pricing subproblem for dynamic column generation, with the precise objective coefficients passed to the pricing problem under each scalarization. These additions will enable full replication of the Pareto sets. revision: yes

Circularity Check

0 steps flagged

No circularity; empirical claims rest on computational experiments without self-referential reductions

full rationale

The paper describes an algorithmic approach (dynamic column generation embedded in three scalarization methods for bi-objective CSP) and reports computational outcomes on Pareto-front quality (cardinality, hypervolume). No derivation chain, equation, or uniqueness claim reduces by construction to its own inputs or to a self-citation whose content is unverified. The central statements are explicitly tied to experimental results rather than mathematical identities or fitted parameters renamed as predictions. Self-citations, if present, are not load-bearing for the reported superiority or complementarity findings.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available, so specific free parameters, axioms, or invented entities cannot be identified from the full paper content.

pith-pipeline@v0.9.0 · 5524 in / 1065 out tokens · 58121 ms · 2026-05-10T15:09:14.122778+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages

  1. [1]

    Aliano-Filho, A

    A. Aliano-Filho, A. C. Moretti, and M. V. Pato. A comparative study of exact methods for the bi- objective integer one-dimensional cutting stock problem.Journal of the Operational Research Society, 69(1):91–107, 2018

    work page 2018

  2. [2]

    Aliano-Filho, A

    A. Aliano-Filho, A. C. Moretti, M. V. Pato, and W. A. Oliveira. An exact scalarization method with multiple reference points for bi-objective integer linear optimization problems.Annals of Operations Research, 296(1):35–69, 2021

    work page 2021

  3. [3]

    Arana-Jiménez and L

    M. Arana-Jiménez and L. Salles-Neto. Sufficient condition for partial efficiency in a bicriteria nonlinear cutting stock problem.RAIRO-Operations Research, 51(3):709–717, 2017

    work page 2017

  4. [4]

    S. A. d. Araujo, K. C. Poldi, and J. Smith. A genetic algorithm for the one-dimensional cutting stock problem with setups.Pesquisa Operacional, 34:165–187, 2014

    work page 2014

  5. [5]

    Artigues, N

    C. Artigues, N. Jozefowiez, and B. M. Sarpong. Column generation algorithms for bi-objective combina- torial optimization problems with a min–max objective.EURO Journal on Computational Optimization, 6(2):117–142, 2018

    work page 2018

  6. [6]

    Boland, H

    N. Boland, H. Charkhgard, and M. Savelsbergh. A criterion space search algorithm for biobjective integer programming: The balanced box method.INFORMS Journal on Computing, 27(4):735–754, 2015

    work page 2015

  7. [7]

    H. V. da Silva, F. K. Lemos, A. C. Cherri, and S. A. de Araujo. Arc-flow formulations for the one- dimensional cutting stock problem with multiple manufacturing modes.RAIRO-perations Research, 57(1):183–200, 2023

    work page 2023

  8. [8]

    De Santis, G

    M. De Santis, G. Grani, and L. Palagi. Branching with hyperplanes in the criterion space: The frontier partitioner algorithm for biobjective integer programming.European Journal of Operational Research, 283(1):57–69, 2020

    work page 2020

  9. [9]

    Desaulniers, J

    G. Desaulniers, J. Desrosiers, and M. M. Solomon, editors.Column Generation. Springer, 2005

    work page 2005

  10. [10]

    E. D. Dolan and J. J. Moré. Benchmarking optimization software with performance profiles.Mathematical Programming, 91(2):201–213, 2002

    work page 2002

  11. [11]

    Ehrgott and X

    M. Ehrgott and X. Gandibleux. Multiple objective combinatorial optimization - a tutorial. InMulti- Objective Programming and Goal Programming, pages 3 – 18. Springer Berlin Heidelberg, 2003

    work page 2003

  12. [12]

    Gau and G

    T. Gau and G. Wäscher. Cutgen1: A problem generator for the standard one-dimensional cutting stock problem.European Journal of Operational Research, 84(3):572–579, 1995

    work page 1995

  13. [13]

    P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting-stock problem. Operations Research, 9(6):849 – 859, 1961

    work page 1961

  14. [14]

    J. C. Gomez and H. Terashima-Maríns. Approximating multi-objective hyper-heuristics for solving 2d irregular cutting stock problems. In G. e. a. Sidorov, editor,Advances in Soft Computing, pages 349 –

    work page

  15. [15]

    Springer Berlin Heidelberg, 2010

    work page 2010

  16. [16]

    G. G. Guimarães and K. C. Poldi. Mathematical models for the cutting stock with limited open stacks problem.RAIRO-perations Research, 57(4):2067–2085, 2023

    work page 2067

  17. [17]

    M. L. IAIN DUNNING, JOEY HUCHETTE.JuMP: Modeling language for mathematical Optimization,

    work page

  18. [18]

    Las visited April 2025

    work page 2025

  19. [19]

    IBM.CPLEX, 2014

    C. IBM.CPLEX, 2014. Visitada pela última vez em: 13/03/2019

    work page 2014

  20. [20]

    Julia.Julia Computing Language, 2018

    C. Julia.Julia Computing Language, 2018. Visitada pela última vez em: 09/10/2020

    work page 2018

  21. [21]

    A. W. J. Kolen and F. C. R. Spieksma. Solving a bi-criterion cutting stock problem with open-ended demand: a case study.Journal of the Operational Research Society, 51(11):1238 – 1247, 2000

    work page 2000

  22. [22]

    Lodi and M

    A. Lodi and M. Monaci. Integer linear programming models for 2-staged two-dimensional knapsack problems.Mathematical Programming, 94(2-3):257–278, 2003

    work page 2003

  23. [23]

    Malaguti, R

    E. Malaguti, R. M. Durán, and P. Toth. Approaches to real world two-dimensional cutting problems. Omega, 47:99 – 115, 2014

    work page 2014

  24. [24]

    Martello and P

    S. Martello and P. Toth.Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., USA, 1990

    work page 1990

  25. [25]

    Martin, E

    M. Martin, E. G. Birgin, R. D. Lobato, R. Morabito, and P. Munari. Models for the two-dimensional rectangular single large placement problem with guillotine cuts and constrained pattern.International Transactions in Operational Research, 27(2):767–793, 2020. 22 J. C. Borges, H. de Florentino and S. Rangel (arXiv 2026)

    work page 2020

  26. [26]

    Mellouli, R

    A. Mellouli, R. Mellouli, and F. Masmoudi. An innovative genetic algorithm for a multi-objective optimization of two-dimensional cutting-stock problem.Applied Artificial Intelligence, 33(6):531–547, 2019

    work page 2019

  27. [27]

    Morabito, M

    R. Morabito, M. N. Arenales, and H. H. Yanasse. Special issue on cutting, packing and related problems. International Transactions in Operational Research, 16(6):659–659, 2009

    work page 2009

  28. [28]

    Muñoz, M

    C. Muñoz, M. Sierra, J. Puente, C. R. Vela, and R. Varela. Improving cutting-stock plans with multi- objective genetic algorithms. In J. R. Mira, J.and Álvarez, editor,Bio-inspired Modeling of Cognitive Tasks, pages 528 – 537, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg

    work page 2007

  29. [29]

    Oliveira, D

    O. Oliveira, D. Gamboa, and E. Silva. An introduction to the two-dimensional rectangular cutting and packing problem.International Transactions in Operational Research, 30:3238–3266, 2023

    work page 2023

  30. [30]

    L. M. Pierini and K. C. Poldi. A bi-objective multiperiod one-dimensional cutting stock problem. Pesquisa Operacional, 42(e258432):1– 19, 2022

    work page 2022

  31. [31]

    Rangel and A

    S. Rangel and A. G. d. Figueiredo. O problema de corte de estoque em indústrias de móveis de pequeno e médio portes.Pesquisa Operacional, 28:451 – 472, 2008

    work page 2008

  32. [32]

    Rangel and J

    S. Rangel and J. Sáez-Aguado. Biobjective approaches for the cutting stock problem minimizing total number of objects and saw cycles.INFORMS 2017 Technical Program, 1:165–165, 2017a

    work page 2017

  33. [33]

    Rangel and J

    S. Rangel and J. Sáez-Aguado. Unidimensional cutting stock problem: Mathematical models to minimize the number of saw cycles and objects.Proceeding Series of the Brazilian Society of Computational and Applied Mathematics, 5(1), 2017b

    work page

  34. [34]

    Respicio and E

    A. Respicio and E. Captivo. Bi-objective sequencing of cutting patterns. InMETAHEURISTICS: progress as real problem solvers, pages 227 – 241. Springer, 2005

    work page 2005

  35. [35]

    Sáez-Aguado and P

    J. Sáez-Aguado and P. C. Trandafir. Variants of theϵ−constraint method for biobjective integer programming problems: aplication toρ-median-cover problems.Mathematical Methods of Operations Research, 87(2):251 – 283, 2018

    work page 2018

  36. [36]

    L. L. Salles-Neto, S. Araujo, and R. Golfeto. Um problema de corte de estoque multiobjetivo.Pesquisa Operacional para o Desenvolvimento, 6(2):183 – 201, 2014

    work page 2014

  37. [37]

    Scheithauer.Introduction to Cutting and Packing Optimization: Problems, Modeling Approaches, Solution Methods, volume 263

    G. Scheithauer.Introduction to Cutting and Packing Optimization: Problems, Modeling Approaches, Solution Methods, volume 263. Springer, 2018

    work page 2018

  38. [38]

    Silva, J

    E. Silva, J. F. Oliveira, and G. Wäscher. 2dcpackgen: A problem generator for two-dimensional rectangular cutting and packing problems.European Journal of Operational Research, 237(3):846–856, 2014

    work page 2014

  39. [39]

    Sinuany-Stern and I

    Z. Sinuany-Stern and I. Weiner. The one dimensional cutting stock problem using two objectives.Journal of the Operational Research Society, 45(2):231–236, 1994

    work page 1994

  40. [40]

    B. Soylu. Heuristic approaches for biobjective mixed 0–1 integer linear programming problems.European Journal of Operational Research, 245(3):690–703, 2015

    work page 2015

  41. [41]

    Toscano, S

    A. Toscano, S. Rangel, and H. H. Yanasse. A heuristic approach to minimize the number of saw cycles in small-scale furniture factories.Annals of Operations Research, 258(2):719–746, 2017

    work page 2017

  42. [42]

    G. Wäscher. An lp-based approach to cutting stock problems with multiple objectives.European Journal of Operational Research, 44(2):175–184, 1990

    work page 1990

  43. [43]

    Wäscher, H

    G. Wäscher, H. Haußner, and H. Schumann. An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3):1109 – 1130, 2007

    work page 2007

  44. [44]

    H. H. Yanasse. A note on the minimization of the number of cutting cycles problem.Livro de resumos do XI Simpósio de Pesquisa Operacional e Logística da Marinha - SPOLM, 2008. 23

    work page 2008