Search code examples
roptimizationlinear-programminglpsolve

cutting stock optimization/waste minimize in r using lpsolve/lpsolveapi

I am having a tough time understanding the how to formulate code to a cutting stock problem. I have searched the web extensively and I see a lot of theory but no actual examples.

The majority of query results point to the wikipedia page: http://en.wikipedia.org/wiki/Cutting_stock_problem

13 patterns to be produced, with required amounts indicated alongside. The machine produces by default a 5600 width piece to be cut into widths below. Goal is to minimize waste.

  Widths/Required amount
1380    22
1520    25
1560    12
1710    14
1820    18
1880    18
1930    20
2000    10
2050    12
2100    14
2140    16
2150    18
2200    20

Would someone show me how to formulate this solution in R with lpsolve/lpsolve API?

  stock=5600
  widths=c(1380,1520,1560,1710,1820,1880,1930,2000,2050,2100,2140,2150,2200)
  required=c(22,25,12,14,18,18,20,10,12,14,16,18,20)

 library(lpSolveAPI)




 ...
 solve(lprec)
 get.variables(lprec)
Solution

  • You could model it as a Mixed Integer Problem and solve it using various techniques. Of course to generate variables (i.e. a valid pattern of widths) you need to use a suitable column generation method.

    Have a look at this C++ project: https://code.google.com/p/cspsol

    cspsol is based on GLPK API library, uses column generation and branch & bound to solve the MIP. It may give you some hints about how to do it in R. Good luck !