2
$\begingroup$

It is well known that applying the Dantzig-Wolfe Decomposition in the one period cutting stock problem with trim loss minimization leads to an optimal real solution that shares the round up property, so directly from the decomposition it is possible to obtain an optimal integer solution for the problem, in other words, the columns (cutting patterns) generated are useful to obtain the optimal integer solution.

I'm currently working with a multi-period cutting stock problem (in each period a cutting process may occur and therefore a cutting stock problem must be solved) where the periods are connected via item inventory (I have other objectives beside trim loss, like cutting pattern minimization). I've been trying to solve it via column generation. After starting the master problem, I solve knapsack subproblems for each period until no patterns with reduced costs are available, thus obtaining an optimal real solution, however the generated columns do not lead to an optimal integer solution (I modeled the problem as a MIP and use an optimization package to solve it). In fact, I've developed heuristics that generate columns and get better results than the one from the column generation via solver. Does that imply that my column generation implementation is wrong or the round up property of the one dimensional single period can't be extended to multi period scenarios?

$\endgroup$
2
  • 4
    $\begingroup$ The property does not hold even for the classical one-period problem. See arxiv.org/ftp/arxiv/papers/2004/2004.01937.pdf $\endgroup$
    – RobPratt
    Sep 29, 2022 at 23:29
  • $\begingroup$ Although concise, @RobPratt's comment looks like an answer to me. $\endgroup$
    – Kuifje
    Sep 30, 2022 at 8:30

1 Answer 1

5
$\begingroup$

The property does not hold even for the classical one-period problem. See Counterexamples in the Cutting Stock Problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.