检索结果-内蒙古大学图书馆

New lower bounds based on column generation and constraint programming for the pattern minimization problem

COMPUTERS & OPERATIONS RESEARCH 2009年第11期36卷 2944-2954页

作者： Alves, Claudio Macedo, Rita de Carvalho, Jose Valerio Univ Minho Ctr Invest Algoritmi Escola Engn P-4710057 Braga Portugal

The pattern minimization problem is a cutting and packing problem that consists in finding a cutting plan with the minimum number of different patterns. This objective may be relevant when changing from one pattern to another involves a cost for setting up the cutting machine. When the minimization of the number of different patterns is done by assuming that no more than the minimum number of rolls can be used, the problem is also referred to as the cutting stock problem with setup costs. Most of the approaches described in the literature are based on heuristics. Solving the problem exactly has been a real challenge, and only very few exact solution methods have been reported so far in the literature. In this paper, we intend to contribute to the resolution of the pattern minimization problem with new results. We explore a different integer programming model that can be solved using column generation, and we describe different strategies to strengthen it, among which are constraint programming and new families of valid inequalities. Lower bounds for the pattern minimization problem are derived from the new integer programming model, and also from a constraint programming model. Our approaches were tested on a set of real instances, and on a set of random instances from the literature. For these instances, the computational experiments show a clear improvement on the quality of the lower bounds. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Cutting and packing problems pattern minimization problem Lower bounds Integer programming Constraint programming

来源：评论

学校读者我要写书评

暂无评论

A BRANCH-AND-PRICE-AND-CUT ALGORITHM FOR THE pattern minimization problem

A BRANCH-AND-PRICE-AND-CUT ALGORITHM FOR THE PATTERN MINIMIZ...

引用

5th ALIO/EURO Workshop on Applied Combinatorial Optimization

作者： Alves, Claudio Valerio de Carvalho, J. M. Univ Minho Escola Engn P-4710057 Braga Portugal

In cutting stock problems, after an optimal (minimal stock usage) cutting plan has been devised, one might want to further reduce the operational costs by minimizing the number of setups. A setup operation occurs each time a different cutting pattern begins to be produced. The related optimization problem is known as the pattern minimization problem, and it is particularly hard to solve exactly. In this paper, we present different techniques to strengthen a formulation proposed in the literature. Dual feasible functions are used for the first time to derive valid inequalities from different constraints of the model, and from linear combinations of constraints. A new arc flow formulation is also proposed. This formulation is used to de. ne the branching scheme of our branch-and-price-and-cut algorithm, and it allows the generation of even stronger cuts by combining the branching constraints with other constraints of the model. The computational experiments conducted on instances from the literature show that our algorithm finds optimal integer solutions faster than other approaches. A set of computational results on random instances is also reported.

关键词： pattern minimization problem column generation cutting planes branch-and-bound dual feasible functions

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：