A note on "Reducing the number of binary variables in cutting stock problems"

Hao Chun Lu; Yu Chien Ko; Yao Huei Huang

doi:10.1007/s11590-012-0598-x

A note on "Reducing the number of binary variables in cutting stock problems"

Hao Chun Lu, Yu Chien Ko, Yao Huei Huang^*

^*Corresponding author for this work

Department of Management Science

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

This study proposes a deterministic model to solve the two-dimensional, cutting stock problem (2DCSP) using a much smaller number of binary variables and thereby reducing the complexity of 2DCSP. Expressing a 2DCSP with m stocks and n cutting rectangles requires 2n² + n(m + 1) binary variables in the traditional model. In contrast, the proposed model uses n² + n⌈log² m⌉ binary variables to express the 2DCSP. Experimental results showed that the proposed model is more efficient than the existing model.

Original language	English
Pages (from-to)	569-579
Number of pages	11
Journal	Optimization Letters
Volume	8
Issue number	2
DOIs	https://doi.org/10.1007/s11590-012-0598-x
State	Published - Feb 2014

Keywords

Binary variables
Cutting stock problem
Deterministic model

Access to Document

10.1007/s11590-012-0598-x

Cite this

@article{fbd03cc646634adcb379e966c77be5df,

title = "A note on {"}Reducing the number of binary variables in cutting stock problems{"}",

abstract = "This study proposes a deterministic model to solve the two-dimensional, cutting stock problem (2DCSP) using a much smaller number of binary variables and thereby reducing the complexity of 2DCSP. Expressing a 2DCSP with m stocks and n cutting rectangles requires 2n2 + n(m + 1) binary variables in the traditional model. In contrast, the proposed model uses n2 + n⌈log2 m⌉ binary variables to express the 2DCSP. Experimental results showed that the proposed model is more efficient than the existing model.",

keywords = "Binary variables, Cutting stock problem, Deterministic model",

author = "Lu, {Hao Chun} and Ko, {Yu Chien} and Huang, {Yao Huei}",

note = "Funding Information: Acknowledgments The authors would like to thank the editor and anonymous referee for providing most valuable comments for us to improve the quality of this manuscript. This research was supported by the project granted by ROC NSC 99-2221-E-030-005-and NSC 100-2221-E-030 -009-.",

year = "2014",

month = feb,

doi = "10.1007/s11590-012-0598-x",

language = "English",

volume = "8",

pages = "569--579",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

T1 - A note on "Reducing the number of binary variables in cutting stock problems"

AU - Lu, Hao Chun

AU - Ko, Yu Chien

AU - Huang, Yao Huei

N1 - Funding Information: Acknowledgments The authors would like to thank the editor and anonymous referee for providing most valuable comments for us to improve the quality of this manuscript. This research was supported by the project granted by ROC NSC 99-2221-E-030-005-and NSC 100-2221-E-030 -009-.

PY - 2014/2

Y1 - 2014/2

N2 - This study proposes a deterministic model to solve the two-dimensional, cutting stock problem (2DCSP) using a much smaller number of binary variables and thereby reducing the complexity of 2DCSP. Expressing a 2DCSP with m stocks and n cutting rectangles requires 2n2 + n(m + 1) binary variables in the traditional model. In contrast, the proposed model uses n2 + n⌈log2 m⌉ binary variables to express the 2DCSP. Experimental results showed that the proposed model is more efficient than the existing model.

AB - This study proposes a deterministic model to solve the two-dimensional, cutting stock problem (2DCSP) using a much smaller number of binary variables and thereby reducing the complexity of 2DCSP. Expressing a 2DCSP with m stocks and n cutting rectangles requires 2n2 + n(m + 1) binary variables in the traditional model. In contrast, the proposed model uses n2 + n⌈log2 m⌉ binary variables to express the 2DCSP. Experimental results showed that the proposed model is more efficient than the existing model.

KW - Binary variables

KW - Cutting stock problem

KW - Deterministic model

UR - http://www.scopus.com/inward/record.url?scp=84893722569&partnerID=8YFLogxK

U2 - 10.1007/s11590-012-0598-x

DO - 10.1007/s11590-012-0598-x

M3 - Article

AN - SCOPUS:84893722569

SN - 1862-4472

VL - 8

SP - 569

EP - 579

JO - Optimization Letters

JF - Optimization Letters

IS - 2

ER -

A note on "Reducing the number of binary variables in cutting stock problems"

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this