次梯度方法
放松(心理学)
整数规划
数学
数学优化
树(集合论)
线性规划松弛
分界
分支和切割
剖切面法
还原(数学)
搜索树
上下界
下料问题
矩形
算法
最优化问题
组合数学
搜索算法
几何学
数学分析
社会心理学
心理学
出处
期刊:Operations Research
[Institute for Operations Research and the Management Sciences]
日期:1985-02-01
卷期号:33 (1): 49-64
被引量:554
摘要
We consider the two-dimensional cutting problem of cutting a number of rectangular pieces from a single large rectangle so as to maximize the value of the pieces cut. We develop a Lagrangean relaxation of a zero-one integer programming formulation of the problem and use it as a bound in a tree search procedure. Subgradient optimization is used to optimize the bound derived from the Lagrangean relaxation. Problem reduction tests derived from both the original problem and the Lagrangean relaxation are given. Incorporating the bound and the reduction tests into a tree search procedure enables moderately sized problems to be solved.
科研通智能强力驱动
Strongly Powered by AbleSci AI