Arc-flow model for the two-dimensional guillotine cutting stock problem
| Autor: | Cláudio Alves, Rita Macedo, J. M. Valério de Carvalho |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Mathematical optimization
021103 operations research General Computer Science Linear programming 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Upper and lower bounds Linear programming relaxation Constraint (information theory) Cutting stock problem Modeling and Simulation 0202 electrical engineering electronic engineering information engineering Combinatorial optimization 020201 artificial intelligence & image processing Integer programming Algorithm Cutting-plane method Mathematics |
| Zdroj: | Computers & Operations Research. 37:991-1001 |
| ISSN: | 0305-0548 |
| DOI: | 10.1016/j.cor.2009.08.005 |
| Popis: | We describe an exact model for the two-dimensional cutting stock problem with two stages and the guillotine constraint. It is an integer linear programming (ILP) arc-flow model, formulated as a minimum flow problem, which is an extension of a model proposed by Valerio de Carvalho for the one dimensional case. In this paper, we explore the behavior of this model when it is solved with a commercial software, explicitly considering all its variables and constraints. We also derive a new family of cutting planes and a new lower bound, and consider some variants of the original problem. The model was tested on a set of real instances from the wood industry, with very good results. Furthermore the lower bounds provided by the linear programming relaxation of the model compare favorably with the lower bounds provided by models based on assignment variables. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect