A parallel algorithm for two-staged two-dimensional fixed-orientation cutting problems

In this paper, we study the two-staged two-dimensional fixed-orientation cutting problem. We investigate the use of the parallel beam search algorithm for approximately solving the problem. The beam-search can be viewed as a truncated tree-search in which a subset of generated nodes are investigated. The proposed approach tries to explore some of these nodes in parallel by applying a master-slave paradigm. The master processor serves to guide the search-resolution by using a best-first search strategy for selecting the successive sets of nodes, called elite nodes. Whereas each slave processor develops the search tree and updates the global list of the master processor in an asynchronous manner. Each processor is based on combining a partial lower bound and a complementary upper bound, obtained by solving a series of bounded knapsack problems. The proposed method is analyzed computationally on a set of benchmark instances of the literature and their results are compared to those provided by existing algorithms. Encouraging and new results have been obtained.     

A recursive algorithm for constrained two-dimensional cutting problems

This paper presents a recursive algorithm for constrained two-dimensional guillotine cutting problems of rectangular items. The algorithm divides a stock plate into a sequence of small rectangular blocks. For the current block considered, it selects an item, puts it at the left-bottom corner of the block, and determines the direction of the dividing cut that divides the unoccupied region of the block into two smaller blocks for further consideration. The dividing cut is either along the upper edge or along the right edge of the selected item. The upper bound obtained from the unconstrained solution is used to shorten the searching space. The computational results on benchmark problems indicate that the algorithm can improve the solutions, and is faster than other algorithms.     

A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems

This paper presents a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional non-guillotine cutting problem, the problem of cutting the rectangular pieces from a large rectangle so as to maximize the value of the pieces cut. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures.     

Improved state space relaxation for constrained two-dimensional guillotine cutting problems

Christofides and Hadjiconstantinou (1995) introduced a dynamic programming state space relaxation for obtaining upper bounds for the Constrained Two-dimensional Guillotine Cutting Problem. The quality of those bounds depend on the chosen item weights, they are adjusted using a subgradient-like algorithm. This paper proposes Algorithm X, a new weight adjusting algorithm based on integer programming that provably obtains the optimal weights. In order to obtain even better upper bounds, that algorithm is generalized into Algorithm X2 for obtaining optimal two-dimensional item weights. We also present a full hybrid method, called Algorithm X2D, that computes those strong upper bounds but also provides feasible solutions obtained by: (1) exploring the suboptimal solutions hidden in the dynamic programming matrices; (2) performing a number of iterations of a GRASP based primal heuristic; and (3) executing X2H, an adaptation of Algorithm X2 to transform it into a primal heuristic. Extensive experiments with instances from the literature and on newly proposed instances, for both variants with and without item rotation, show that X2D can consistently deliver high-quality solutions and sharp upper bounds. In many cases the provided solutions are certified to be optimal.     

A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size

We consider a two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as its subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a mixed integer linear programming model for the solution of this knapsack problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by Cintra et al. [3].     

Staged and constrained two-dimensional guillotine cutting problems: An AND/OR-graph approach

An AND/OR-graph approach has been proposed by Morabito et al. to solve non-staged and unconstrained two-dimensional guillotine cutting problems. Basically, this approach consists of representing cutting patterns as complete paths in an AND/OR graph (where nodes and arcs correspond to rectangles and cuts, respectively) and choosing a search strategy to traverse or enumerate the nodes of the graph. In this present paper, the AND/OR-graph approach is extended to solve staged and constrained problems. Computational experiments with examples from the literature are performed and indicate that this approach generates good and fast solutions using a microcomputer. In addition to the fact that the AND/OR-graph approach can handle important constraints, it can be easily extended to solve cutting and packing problems with multiple dimensions.     

Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns

Two-staged patterns are often used in manufacturing industries to divide stock plates into rectangular items. A heuristic algorithm is presented to solve the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns. It uses the column-generation method to solve the residual problems repeatedly, until the demands of all items are satisfied. Each pattern is generated using a procedure for the constrained single large object placement problem to guarantee the convergence of the algorithm. The computational results of benchmark and practical instances indicate the following: (1) the algorithm can solve most instances to optimality, with the gap to optimality being at most one plate for those solutions whose optimality is not proven and (2) for the instances tested, the algorithm is more efficient (on average) in reducing the number of plates used than a published algorithm and a commercial stock cutting software package.     

Superlinearly convergent quasi-newton algorithms for nonlinearly constrained optimization problems

A class of algorithms for nonlinearly constrained optimization problems is proposed. The subproblems of the algorithms are linearly constrained quadratic minimization problems which contain an updated estimate of the Hessian of the Lagrangian. Under suitable conditions and updating schemes local convergence and a superlinear rate of convergence are established. The convergence proofs require among other things twice differentiable objective and constraint functions, while the calculations use only first derivative data. Rapid convergence has been obtained in a number of test problems by using a program based on the algorithms proposed here.Research supported by NSF Grant GJ-35292 at the University of Wisconsin.     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为$2-\frac 2m$,其中$m$是机器数目。     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为$2-frac 2m$,其中$m$是机器数目。     

Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

Due to their fundamental nature and numerous applications, sphere constrained polynomial optimization problems have received a lot of attention lately. In this paper, we consider three such problems: (i) maximizing a homogeneous polynomial over the sphere; (ii) maximizing a multilinear form over a Cartesian product of spheres; and (iii) maximizing a multiquadratic form over a Cartesian product of spheres. Since these problems are generally intractable, our focus is on designing polynomial-time approximation algorithms for them. By reducing the above problems to that of determining the L ₂-diameters of certain convex bodies, we show that they can all be approximated to within a factor of Ω((log n/n) ^d/2–1) deterministically, where n is the number of variables and d is the degree of the polynomial. This improves upon the currently best known approximation bound of Ω((1/n) ^d/2–1) in the literature. We believe that our approach will find further applications in the design of approximation algorithms for polynomial optimization problems with provable guarantees.     

Integrating two-dimensional cutting stock and lot-sizing problems

The two-dimensional cutting stock problem (2DCSP) consists in the minimization of the number of plates used to cut a set of items. In industry, typically, an instance of this problem is considered at the beginning of each planning time period, what may result in solutions of poor quality, that is, excessive waste, when a set of planning periods is considered. To deal with this issue, we consider an integrated problem, in which the 2DCSP is extended from the solution in only a single production planning period to a solution in a set of production planning periods. The main difference of the approach in this work and the ones in the literature is to allow sufficiently large residual plates (leftovers) to be stored and cut in a subsequent period of the planning horizon, which may further help in the minimization of the waste. We propose two integrated integer programming models to optimize the combined two-dimensional cutting stock and lot-sizing problems, minimizing the total cost, which includes material, waste and storage costs. Two heuristics based on the industrial practice to solve the problem were also presented. Computational results for the proposed models and for the heuristics are presented and discussed.     

An efficient approach for large-scale two-dimensional guillotine cutting stock problems

We present an efficient method for solving approximately both constrained and unconstrained two-dimensional cutting stock problems. The algorithm guarantees a constant approximation ratio for some versions of the problem. The performance of the proposed algorithm is evaluated on several large-scale randomly generated problem instances and on many instances of the literature. Computational results show that our algorithm produces high-quality solutions within reasonable computational times.     

MIP models for two-dimensional non-guillotine cutting problems with usable leftovers

In this study we deal with the two-dimensional non-guillotine cutting problem of how to cut a set of larger rectangular objects to a set of smaller rectangular items in exactly a demanded number of pieces. We are concerned with the special case of the problem in which the non-used material of the cutting patterns (objects leftovers) may be used in the future, for example if it is large enough to fulfill future item demands. Therefore, the problem is seen as a two-dimensional non-guillotine cutting/packing problem with usable leftovers, also known in the literature as a two-dimensional residual bin-packing problem. We use multilevel mathematical programming models to represent the problem appropriately, which basically consists of cutting the ordered items using a set of objects of minimum cost, among all possible solutions of minimum cost, choosing one that maximizes the value of the usable leftovers, and, among them, selecting one that minimizes the number of usable leftovers. Because of special characteristics of these multilevel models, they can be reformulated as one-level mixed integer programming (MIP) models. Illustrative numerical examples are presented and analysed.     

Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems

This paper is concerned with the problem of unconstrained two-dimensional cutting of small rectangular pieces, each of which has its own profit and size, from a large rectangular plate so as to maximize the profit-sum of the pieces produced. Hifi and Zissimopoulos's recursive algorithm using G and Kang's upper bound is presently the most efficient exact algorithm for the problem. We propose a best-first branch and bound algorithm based upon the bottom-up approach that is more efficient than their recursive algorithm. The proposed algorithm uses efficient upper bound and branching strategies that can reduce the number of nodes that must be searched significantly. We demonstrate the efficiency of the proposed algorithm through computational experiments.     

An integer programming model for two- and three-stage two-dimensional cutting stock problems

In this paper, an integer programming model for two-dimensional cutting stock problems is proposed. In the problems addressed, it is intended to cut a set of small rectangular items of given sizes from a set of larger rectangular plates in such a way that the total number of used plates is minimized.