Geodesic
The grouping method for the linear relaxation of 1d cutting stock problem
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 3, pp. 47-62.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the problem of large-dimension linear cutting. This problem could be interpreted as a problem of linear integer programming. Using the proposed grouping method we can get the initial solution for the problem of continuous relaxation. This solution is close to the optimum, which often reducing the time to find optimal solutions. Bibl. 15.
Keywords: linear relaxation, simplex-method, 1d cutting stock problem. 
@article{DA_2009_16_3_a2,
     author = {V. M. Kartak},
     title = {The grouping method for the linear relaxation of 1d cutting stock problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {47--62},
     publisher = {mathdoc},
     volume = {16},
     number = {3},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_3_a2/}
}
TY  - JOUR
AU  - V. M. Kartak
TI  - The grouping method for the linear relaxation of 1d cutting stock problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 47
EP  - 62
VL  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_3_a2/
LA  - ru
ID  - DA_2009_16_3_a2
ER  - 
%0 Journal Article
%A V. M. Kartak
%T The grouping method for the linear relaxation of 1d cutting stock problem
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 47-62
%V 16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_3_a2/
%G ru
%F DA_2009_16_3_a2
V. M. Kartak. The grouping method for the linear relaxation of 1d cutting stock problem. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 3, pp. 47-62. http://geodesic.mathdoc.fr/item/DA_2009_16_3_a2/

[1] Geri M. P., Dzhonson D. S., Vychislitelnye mashiny i trudnorazreshimye zadachi, Mir, M., 1982, 419 pp. | MR

[2] Kantorovich L. V., Zallgaller V. A., Raschet ratsionalnogo raskroya materialov, Lenizdat, L., 1951, 199 pp.

[3] Kartak V. M., “Dostatochnye usloviya nevypolneniya svoistva tselochislennogo okrugleniya dlya zadachi lineinogo raskroya”, Avtomatika i telemekhanika, 2004, no. 4, 55–62 | MR

[4] Mukhacheva E. A., Rubinshtein G. Sh., Matematicheskoe programmirovanie, Nauka, Novosibirsk, 1987, 272 pp. | MR | Zbl

[5] Applegate D. L., Buriol L. S., Dillard B. L., Johnson D. S., Shor P. W., “The cutting-stock approach to bin packing: theory and experiments”, Proc. the fifth workshop on algorithm engineering and experimentation, SIAM, 2003, 1–15

[6] Belov G., Scheithauer G., “A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting”, Europ. J. Oper. Research, 171:1 (2006), 85–106 | DOI | MR | Zbl

[7] Claudio A., Valerio de Carvalho J. M., “A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem”, Comput. Oper. Research, 35:4 (2008), 1315–1328 | DOI | Zbl

[8] Dyckhoff H., “A typology of cutting and packing problems”, Europ. J. Oper. Research, 44:2 (1990), 145–159 | DOI | MR | Zbl

[9] Fernandez de la Vega W., Lueker G. S., “Bin packing can be solved within $1+e$ in linear time”, Combinatorica, 1981, no. 1, 349–355 | DOI | MR | Zbl

[10] Gilmore P., Gomory R., “A linear programming approach to the cutting-stock problem”, Oper. Research, 1961, no. 9, 849–859 | DOI | MR | Zbl

[11] Marcotte O., “An instance of the cutting stock problem for which the rounding property does not hold”, Oper. Research Letters, 4:5 (1986), 239–243 | DOI | MR | Zbl

[12] Mukhacheva E., Belov G., Kartak V., Mukhacheva A., “Linear one-dimensional cutting-packing problems: numerical experiments with the sequential value correction method (SVC) and a modified branch-and-bound method (MBB)”, Pesquisa Operacional, 20:2 (2000), 153–168 | DOI

[13] Peeters M., Degraeve Z., “Optimal integer solutions to industrial cutting-stock problems: part 2. Benchmark Results”, Inform. J. Computing, 15:1 (2003), 58–81 | DOI | MR

[14] Schwerin P., Wascher G., “The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP”, Intern. Transactions Oper. Research, 4:5/6 (1997), 377–389 | DOI | Zbl

[15] Vanderbeck F., “Computational study of a column generation algorithm for bin packing and cutting stock problems”, Math. Programming, 86:3 (1999), 565–594 | DOI | MR | Zbl