下料问题
整数规划
解算器
背包问题
水准点(测量)
数学优化
集合(抽象数据类型)
计算机科学
整数(计算机科学)
线性规划
数学
算法
最优化问题
程序设计语言
大地测量学
地理
作者
Panos M. Pardalos,Enrico Malaguti,Dimitri Thomopulos
出处
期刊:INFORMS journal on computing
日期:2016-10-05
卷期号:28 (4): 736-751
被引量:33
标识
DOI:10.1287/ijoc.2016.0710
摘要
We propose a framework to model general guillotine restrictions in two-dimensional cutting problems formulated as mixed-integer linear programs (MIPs). The modeling framework requires a pseudopolynomial number of variables and constraints, which can be effectively enumerated for medium-size instances. Our modeling of general guillotine cuts is the first one that, once it is implemented within a state-of-the-art MIP solver, can tackle instances of challenging size. We mainly concentrate our analysis on the guillotine two-dimensional knapsack problem (G2KP), for which a model, and an exact procedure able to significantly improve the computational performance, are given. We also show how the modeling of general guillotine cuts can be extended to other relevant problems such as the guillotine two-dimensional cutting stock problem and the guillotine strip packing problem (GSPP). Finally, we conclude the paper discussing an extensive set of computational experiments on G2KP and GSPP benchmark instances from the literature.
科研通智能强力驱动
Strongly Powered by AbleSci AI