Bin packing and related problems: General arc-flow formulation with graph compression

We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems—including multi-constraint variants—by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model.Our formulation is equivalent to Gilmore and Gomory׳s, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern.The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and other problems. We report computational results obtained with many benchmark test datasets, some of them showing a large advantage of this formulation with respect to the traditional ones.     

Evaluation of algorithms for one-dimensional cutting

The paper deals with the problem of evaluating and comparing different one-dimensional stock cutting algorithms regarding trim loss. Different types of problems are identified. An evaluation method is developed which enables a comparison of solutions of all types of problems. A practical example of this methods implementation is presented.Scope and purposeThere are many algorithms and methods for one-dimensional stock cutting with different factors that need to be taken into account. Therefore a general comparison between them is very difficult if not impossible. However, if we assume that trim loss is the most important factor common to different methods, we can overcome this problem by limiting the comparison to trim loss. In different cutting stock problems and in different approaches to them trim loss is defined differently. For the comparison of different solutions to be possible, we need to find a common definition to the trim loss. Such a general definition is introduced by the General One-Dimensional Cutting Stock Problem type (G1D-CSP). In this paper, a problem generator algorithm PGEN for G1D-CSP is presented and the method for evaluation and comparison of different one-dimensional cutting stock algorithms is proposed.     

An Innovative Genetic Algorithm for a Multi-Objective Optimization of Two-Dimensional Cutting-Stock Problem

This paper addressed an important variant of two-dimensional cutting stock problem. The objective was not only to minimize trim loss, as in traditional cutting stock problems, but rather to minimize the number of machine setups. This additional objective is crucial for the life of the machines and affects both the time and the cost of cutting operations. Since cutting stock problems are well known to be NP-hard, we proposed an approximate method to solve this problem in a reasonable time. This approach differs from the previous works by generating a front with many interesting solutions. By this way, the decision maker or production manager can choose the best one from the set based on other additional constraints. This approach combined a genetic algorithm with a linear programming model to estimate the optimal Pareto front of these two objectives. The effectiveness of this approach was evaluated through a set of instances collected from the literature. The experimental results for different-size problems show that this algorithm provides Pareto fronts very near to the optimal ones.     

A combined approach to the solution to the general one-dimensional cutting stock problem

In this article a combined method for the solution to the general one-dimensional cutting stock problem (G1D-CSP) is proposed. The main characteristic of G1D-CSP lies in that all stock lengths can be different. The new approach combines two existing methods: sequential heuristic procedure (SHP) and branch-and-bound. The algorithm based on the proposed method leads to almost optimal solutions, which are substantially better than the solutions of known methods at the expense of slightly increased time complexity, which is still low. So, the new method is suitable for all sizes of the problem. A comparison with the SHP is presented.     

An improved tabu search approach with mixed objective function for one-dimensional cutting stock problems

In this paper, a methodology with both efficiency and effectiveness of using improved tabu search approach is applied successfully to solve one-dimensional cutting stock problem (1D-CSP). By introducing a varying mixed objective function, the chance of obtaining optimum solution in solving 1D-CSP, which is treated as a sequence problem, has increased. The total incentive trim loss, which functions as an incentive term in this paper, makes it possible to obtain good 1D-CSP results through the use of the new proposed TS approach. After testing against actual sample cases from shipyards and literatures, the solutions obtained from the proposed algorithm are superior. Computational results indicate that the methodology proposed outperforms the ones from other meta-heuristic methods.     

An algorithm for the determination of optimal cutting patterns

This paper presents a new mathematical programming formulation for the problem of determining the optimal manner in which several product rolls of given sizes are to be cut out of raw rolls of one or more standard types. The objective is to perform this task so as to maximize the profit taking account of the revenue from the sales, the costs of the original rolls, the costs of changing the cutting pattern and the costs of disposal of the trim. A mixed integer linear programming (MILP) model is proposed which is solved to global optimality using standard techniques. A number of example problems, including an industrial case study, are presented to illustrate the efficiency and applicability of the proposed model.Scope and purposeOne-dimensional cutting stock (trim loss) problems arise when production items must be physically divided into pieces with a diversity of sizes in one dimension (e.g. when slitting master rolls of paper into narrower width rolls). Such problems occur when there are no economies of scale associated with the production of the larger raw (master) rolls. In general, the objectives in solving such problems are to [5]:

• •minimize trim loss;
• •avoid production over-runs and/or;
• •avoid unnecessary slitter setups.

The above problem is particularly important in the paper converting industry when a set of paper rolls need to be cut from raw paper rolls. Since the width of a product is fully independent of the width of the raw paper a highly combinatorial problem arises. In general, the cutting process always produces inevitable trim-loss which has to be burned or processed in some waste treatment plant. Trim-loss problems in the paper industry have, in recent years, mainly been solved using heuristic rules. The practical problem formulation has, therefore, in most cases been restricted by the fact that the solution methods ought to be able to handle the entire problem. Consequently, only a suboptimal solution to the original problem has been obtained and very often this rather significant economic problem has been left to a manual stage. This work presents a novel algorithm for efficiently determining optimal cutting patterns in the paper converting process. A mixed-integer linear programming model is proposed which is solved to global optimality using available computer tools. A number of example problems including an industrial case study are presented to illustrate the applicability of the proposed algorithm.     

Row and column generation technique for a multistage cutting stock problem

The multistage cutting stock problem (CSP) generalizes the one-dimensional CSP when a lengthwise cutting process is distributed over two or more successive stages. At every stage of the cutting process incoming rolls are slit into smaller rolls by width. The problem is to minimize total trim loss occurring at all stages of technological process meeting customer demands for finished rolls. We propose a row and column generation technique for solving the multistage one-dimensional CSP. The technique is a generalization of the column generation method suggested by Gilmore and Gomory for solving a classic CSP. The procedure generates only those intermediate rolls (rows) and cutting patterns (columns) that are needed. An auxiliary problem embedded into the frame of the revised simplex algorithm is a non-linear knapsack problem that can be solved efficiently. Computational results prove the overall method is a valuable addition to the tool set for modeling and solving the multistage CSP.Scope and purposeWe investigate a broad class of large-scale linear programming models and suggest a new and efficient way to solve them. The proposed method belongs to a category of decomposition techniques generalizing the famous column generation method. An iteration of the revised simplex algorithm may “enrich” the LP matrix either by generating a new column, as a purely column generation method does, or by generating a combination of a new row and a pair of new columns. The method is a row and column generation technique that we propose and investigate. Applications modeled by a multistage CSP occur in the industries that use a multistage cutting process: paper, leather, film, steel, etc., or a nested packing/loading process: transportation. The unknown variables in the multistage cutting stock problem are intermediate sizes (rows) and cutting patterns (columns). According to the algorithm both are to be generated dynamically. The proposed algorithm brings tremendous benefits in terms of the quality of solutions and computational performance.     

Lower bounds for on-line two-dimensional packing algorithms

Summary Many problems, such as cutting stock problems and the scheduling of tasks with a shared resource, can be viewed as two-dimensional bin packing problems. Using the two-dimensional packing model of Baker, Coffman, and Rivest, a finite list L of rectangles is to be packed into a rectangular bin of finite width but infinite height, so as to minimize the total height used. An algorithm which packs the list in the order given without looking ahead or moving pieces already packed is called an on-line algorithm. Since the problem of finding an optimal packing is NP-hard, previous work has been directed at finding approximation algorithms. Most of the approximation algorithms which have been studied are on-line except that they require the list to have been previously sorted by height or width. This paper examines lower bounds for the worst-case performance of on-line algorithms for both non-preordered lists and for lists preordered by increasing or decreasing height or width.This author's work was supported by the Joint Services Electronics Program (U.S. Army, U.S. Navy and U.S. Air Force) under Contract DAAG-29-78-C-0016     

Roll assortment optimization in a paper mill: An integer programming approach

Fine paper mills produce a variety of paper grades to satisfy demand for a large number of sheeted products. Huge reels of different paper grades are produced on a cyclical basis on paper machines. These reels are then cut into rolls of smaller size which are then either sold as such, or sheeted into finished products in converting plants. A huge number of roll sizes would be required to cut all finished products without trim loss and they cannot all be inventoried. An assortment of rolls is inventoried with the implication that the sheeting operations may yield trim loss. The selection of the assortment of roll sizes to stock and the assignment of these roll sizes to finished products have a significant impact on performances. This paper presents a model to decide the parent roll assortment and assignments to finished products based on these products demand processes, desired service levels, trim loss and inventory holding costs. Risk pooling economies made by assigning several finished products to a given roll size is a fundamental aspect of the problem. The overall model is a binary non-linear program. Two solution methods are developed: a branch and price algorithm based on column generation and a fast pricing heuristic, and a marginal cost heuristic. The two methods are tested on real data and also on randomly generated problem instances. The approach proposed was implemented by a large pulp and paper company.     

Variable neighbourhood search for the variable sized bin packing problem

The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.     

板材排样中非拟合多边形的构造实现方法

非拟合多边形可用于处理两维的不规则形状的板材排样问题.先前,基于非拟合多边形的构造很难实现,并且也没有通用的方式来处理多种特殊情况,从而非拟合多边形并没有被广泛的使用.本文介绍了一种基于环绕的实现方式来构造非拟合多边形,对各种特殊情况能统一解决,例如互锁,交叉等.通过对ESICUP的数据集测试,表明该方法具有一定的效果,可以对板材排样的解决思路提供一定的借鉴.     

Algorithms for 3D guillotine cutting problems: Unbounded knapsack, cutting stock and strip packing

We present algorithms for the following three-dimensional (3D) guillotine cutting problems: unbounded knapsack, cutting stock and strip packing. We consider the case where the items have fixed orientation and the case where orthogonal rotations around all axes are allowed. For the unbounded 3D knapsack problem, we extend the recurrence formula proposed by [1] for the rectangular knapsack problem and present a dynamic programming algorithm that uses reduced raster points. We also consider a variant of the unbounded knapsack problem in which the cuts must be staged. For the 3D cutting stock problem and its variants in which the bins have different sizes (and the cuts must be staged), we present column generation-based algorithms. Modified versions of the algorithms for the 3D cutting stock problems with stages are then used to build algorithms for the 3D strip packing problem and its variants. The computational tests performed with the algorithms described in this paper indicate that they are useful to solve instances of moderate size.     

混合遗传算法在圆形件优化排样中的应用研究

本文研究的是圆形件优化排样问题,是将卷材切成若干种圆形毛坯,使所产生的废料最少以达到节约材料的目的。本文在我们提出的放置算法(ASA)的基础上,采用混合遗传算法作为搜索策略;实验测试结果表明,本文算法可以和排样领域著名的法国学者Hifi在国外检索刊物上提出的算法相媲美,该算法的计算时间可以满足一般实践应用的要求,所得排样方案的材料利用率较高。     

New heuristics for one-dimensional bin-packing

Several new heuristics for solving the one-dimensional bin packing problem are presented. Some of these are based on the minimal bin slack (MBS) heuristic of Gupta and Ho. A different algorithm is one based on the variable neighbourhood search metaheuristic. The most effective algorithm turned out to be one based on running one of the former to provide an initial solution for the latter. When tested on 1370 benchmark test problem instances from two sources, this last hybrid algorithm proved capable of achieving the optimal solution for 1329, and could find for 4 instances solutions better than the best known. This is remarkable performance when set against other methods, both heuristic and optimum seeking.Scope and purposePacking items into boxes or bins is a task that occurs frequently in distribution and production. A large variety of different packing problems can be distinguished, depending on the size and shape of the items, as well as on the form and capacity of the bins (H. Dyckhoff and U. Finke, Cutting and Packing in Production and Distribution: a Typology and Bibliography, Springer, Berlin, 1992). Similar problems occur in minimising material wastage while cutting pieces into particular smaller ones and in the scheduling of identical processors in order to minimise total completion time. This work addresses the basic packing problem, known as the one-dimensional bin packing problem, where it is required to pack a number of items into the smallest possible number of bins of pre-specified equal capacity. Even though this problem is simple to state, it is NP hard, i.e., it is unlikely that there exists an algorithm that could solve every instance of it in polynomial time. Solution of more general realistic packing problems is probably contingent upon the availability of effective and computationally efficient solution procedures for the basic problem. In this work we present several heuristics capable of doing that. Extensive computational testing attests to the power of these heuristics, as well as to their computational efficiency.     

半在线入库堆垛问题的动态求解算法

堆场垛位优化问题一直是仓储管理的难点和焦点之一,垛位优化可以保证物料装卸和出入库的高效率,同时对保证合同交货期也起着至关重要的作用。针对仓储和生产一体化下的入库堆垛问题,本文通过分析将其归结为一类半在线的A型装箱问题,并依据问题的特点,建立了最小化总倒垛次数的优化模型。根据货场天车在相邻入库过程中存在空闲作业量的特点,设计了一种前序货物允许移动的动态堆垛策略,结合堆垛约束后嵌入到经典装箱启发式算法中,最后通过仿真算例验证了该策略的有效性。     

Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape

In this paper, the two-dimensional cutting/packing problem with items that correspond to simple polygons that may contain holes are studied in which we propose algorithms based on no-fit polygon computation. We present a GRASP based heuristic for the 0/1 version of the knapsack problem, and another heuristic for the unconstrained version of the knapsack problem. This last heuristic is divided in two steps: first it packs items in rectangles and then use the rectangles as items to be packed into the bin. We also solve the cutting stock problem with items of irregular shape, by combining this last heuristic with a column generation algorithm. The algorithms proposed found optimal solutions for several of the tested instances within a reasonable runtime. For some instances, the algorithms obtained solutions with occupancy rates above 90% with relatively fast execution time.     

Using Wang's two-dimensional cutting stock algorithm to optimally solve difficult problems

P. Y. Wang's classic bottom-up two-dimensional cutting stock algorithm generates cutting patterns by building rectangles both horizontally and vertically. This algorithm uses a parameter β ₁ to tradeoff the number of rectangles generated by the algorithm and hence the quality of the cutting pattern solution obtained versus the amount of computer resources required. Several researchers have made relatively straightforward modifications to Wang's basic algorithm resulting in improved computational times. However, even with these modifications, Wang's approach tends to require large amounts of computer resources in order to optimally or near-optimally solve difficult two-dimensional guillotine cutting stock problems. In this paper, we present an iterative approach that judiciously uses Wang's basic algorithm (with some previously defined modifications) to obtain optimal cutting patterns to difficult two-dimensional cutting stock problems in reasonable computer run times.     

Dantzig-Wolfe decomposition and branch-and-price solving in G12

The G12 project is developing a software environment for stating and solving combinatorial problems by mapping a high-level model of the problem to an efficient combination of solving methods. Model annotations are used to control this process. In this paper we explain the mapping to branch-and-price solving. Dantzig-Wolfe decomposition is automatically performed using the additional information given by the model annotations. The models obtained can then be solved using column generation and branch-and-price. G12 supports the selection of specialised subproblem solvers, the aggregation of identical subproblems to reduce symmetries, automatic disaggregation when required by branch-and-bound, the use of specialised subproblem constraint-branching rules, and different master problem solvers including a hybrid solver based on the volume algorithm. We demonstrate the benefits of the G12 framework on three examples: a trucking problem, cutting stock, and two-dimensional bin packing.     

一种求解圆形下料问题的快速算法

本文研究圆形件优化排样算法,目的是提高材料利用率。本文提出了一种新的放置算法(圆弧搜索算法,ASA),与文献中算法相比,ASA在较短的时间内产生了可以和排样领域著名的法国学者Hifi在SCI和EI检索刊物中提出的较复杂方法GA-BH在利用率方面相媲美的效果;对随机生成例题的计算结果表明,本文算法的计算时间可以满足一般实践应用的要求,所得排样方案的材料利用率较高。     

一种求解圆形下料问题的快速算法

本文研究圆形件优化排样算法,目的是提高材料利用率。本文提出了一种新的放置算法(圆弧搜索算法,ASA),与文献中算法相比,ASA在较短的时间内产生了可以和排样领域著名的法国学者Hifi在SCI和EI检索刊物中提出的较复杂方法GA-BH在利用率方面相媲美的效果;对随机生成例题的计算结果表明,本文算法的计算时间可以满足一般实践应用的要求,所得排样方案的材料利用率较高。