A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting

The one-dimensional cutting stock problem (1D-CSP) and the two-dimensional two-stage guillotine constrained cutting problem (2D-2CP) are considered in this paper. The Gilmore–Gomory models of these problems have very strong continuous relaxations providing a good bound in an LP-based solution approach. In recent years, there have been several efforts to attack the one-dimensional problem by LP-based branch-and-bound with column generation (called branch-and-price) and by general-purpose Chvátal–Gomory cutting planes. In this paper we investigate a combination of both approaches, i.e., the LP relaxation at each branch-and-price node is strengthened by Chvátal–Gomory and Gomory mixed-integer cuts. The branching rule is that of branching on variables of the Gilmore–Gomory formulation. Tests show that, for 1D-CSP, general-purpose cuts are useful only in exceptional cases. However, for 2D-2CP their combination with branching is more effective than either approach alone and mostly better than other methods from the literature.     

A Parallel Grasp for the Steiner Tree Problem in Graphs Using a Hybrid Local Search Strategy

In this paper, we present a parallel greedy randomized adaptive search procedure (GRASP) for the Steiner problem in graphs. GRASP is a two-phase metaheuristic. In the first phase, solutions are constructed using a greedy randomized procedure. Local search is applied in the second phase, leading to a local minimum with respect to a specified neighborhood. In the Steiner problem in graphs, feasible solutions can be characterized by their non-terminal nodes (Steiner nodes) or by their key-paths. According to this characterization, two GRASP procedures are described using different local search strategies. Both use an identical construction procedure. The first uses a node-based neighborhood for local search, while the second uses a path-based neighborhood. Computational results comparing the two procedures show that while the node-based variant produces better quality solutions, the path-based variant is about twice as fast. A hybrid GRASP procedure combining the two neighborhood search strategies is then proposed. Computational experiments with a parallel implementation of the hybrid procedure are reported, showing that the algorithm found optimal solutions for 45 out of 60 benchmark instances and was never off by more than 4% of the optimal solution value. The average speedup results observed for the test problems show that increasing the number of processors reduces elapsed times with increasing speedups. Moreover, the main contribution of the parallel algorithm concerns the fact that larger speedups of the same order of the number of processors are obtained exactly for the most difficult problems.     

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.     

One-dimensional cutting stock optimization in consecutive time periods

The paper deals with the general one-dimensional cutting stock problem (G1D-CSP), where optimization is not limited to a single order. Stock cutting is treated as a permanent business process in a company in which consecutive order sets need to be fulfilled either for production needs or for its customers. Exact demand for future orders is not known in advance. The unutilized and partly utilized stock lengths left after fulfilling current order sets are stored and used later. The goal is the reduction of trim loss and costs over a broader time-span. A new approach is suggested where previously developed method for G1D-CSP is modified. Several practical examples of the cutting process for several consecutive order sets are presented. An extension to a currently used typology for cutting stock problems is proposed.     

Local search with a generalized neighborhood in the optimization problem for pseudo-Boolean functions

In the optimization problem for pseudo-Boolean functions we consider a local search algorithm with a generalized neighborhood. This neighborhood is constructed for a locally optimal solution and includes nearby locally optimal solutions. We present some results of simulations for pseudo-Boolean functions whose optimization is equivalent to the problems of facility location, set covering, and competitive facility location. The goal of these experiments is to obtain a comparative estimate for the locally optimal solutions found by the standard local search algorithm and the local search algorithm using a generalized neighborhood.     

An algorithm for the two-dimensional assortment problem

In this paper we consider the two-dimensional assortment problem. This is the problem of choosing from a set of stock rectangles a subset which can be used for cutting into a number of smaller rectangular pieces. Constraints are imposed upon the number of such pieces which result from the cutting.A heuristic algorithm for the guillotine cutting version of the problem is developed based on a greedy procedure for generating two-dimensional cutting patterns, a linear program for choosing the cutting patterns to use and an interchange procedure to decide the best subset of stock rectangles to cut.Computational results are presented for a number of test problems which indicate that the algorithm developed produces good quality results both for assortment problems and for two-dimensional cutting problems.     

Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem

We compare two branch-and-price approaches for the cutting stock problem. Each algorithm is based on a different integer programming formulation of the column generation master problem. One formulation results in a master problem with 0–1 integer variables while the other has general integer variables. Both algorithms employ column generation for solving LP relaxations at each node of a branch-and-bound tree to obtain optimal integer solutions. These different formulations yield the same column generation subproblem, but require different branch-and-bound approaches. Computational results for both real and randomly generated test problems are presented.     

A hybrid approach based on genetic algorithms to solve the problem of cutting structural beams in a metalwork company

This work presents a hybrid approach based on the use of genetic algorithms to solve efficiently the problem of cutting structural beams arising in a local metalwork company. The problem belongs to the class of one-dimensional multiple stock sizes cutting stock problem, namely 1-dimensional multiple stock sizes cutting stock problem. The proposed approach handles overproduction and underproduction of beams and embodies the reusability of remnants in the optimization process. Along with genetic algorithms, the approach incorporates other novel refinement algorithms that are based on different search and clustering strategies. Moreover, a new encoding with a variable number of genes is developed for cutting patterns in order to make possible the application of genetic operators. The approach is experimentally tested on a set of instances similar to those of the local metalwork company. In particular, comparative results show that the proposed approach substantially improves the performance of previous heuristics.     

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.     

Heuristic and exact methods for the cutting sequencing problem

Cutting stock problems deal with the generation of a set of cutting patterns that minimizes waste. Sometimes it is also important to find the processing sequence of this set of patterns to minimize the maximum queue of partially cut orders. In such instances a cutting sequencing problem has to be solved. This paper presents a new mathematical model and a three-phase approach for the cutting sequencing problem. In the first phase, a greedy algorithm produces a good starting solution that is improved in the second phase by a tabu search, or a generalized local search procedure, while, in the last phase, the problem is optimally solved by an implicit enumeration procedure that uses the best solution previously found as an upper bound. Computing experience, based on 300 randomly generated problems, shows the good performance of the heuristic methods presented.     

Cutting and packing problems for irregular objects with continuous rotations: mathematical modelling and non-linear optimization

We further improve our methodology for solving irregular packing and cutting problems. We deal with an accurate representation of objects bounded by circular arcs and line segments and allow their continuous rotations and translations within rectangular and circular containers. We formulate a basic irregular placement problem which covers a wide spectrum of packing and cutting problems. We provide an exact non-linear programming (NLP) model of the problem, employing ready-to-use phi-functions. We develop an efficient solution algorithm to search for local optimal solutions for the problem in a reasonable time. The algorithm reduces our problem to a sequence of NLP subproblems and employs optimization procedures to generate starting feasible points and feasible subregions. Our algorithm allows us to considerably reduce the number of inequalities in NLP subproblems. To show the benefits of our methodology we give computational results for a number of new challenger and the best known benchmark instances.     

Multi-job Cutting Stock Problem with Due Dates and Release Dates

The common feature of cutting stock problems is to cut some form of stock materials to produce smaller pieces of materials in quantities matching orders received. Most research on cutting stock problems focuses on either generating cutting patterns to minimize wastage or determining the required number of stock materials to meet orders. In this paper, we examine a variation of cutting stock problems that arises in some industries where meeting orders' due dates is more important than minimizing wastage of materials. We develop two two-dimensional cutting stock models with due date and release date constraints. Since adding due dates and release dates makes the traditional cutting stock problem even more difficult to solve, we develop both LP-based and non-LP-based heuristics to obtain good solutions. The computational results show that the solution procedures are easy to implement and work very well.     

A 3-flip neighborhood local search for the set covering problem

The set covering problem (SCP) calls for a minimum cost family of subsets from n given subsets, which together covers the entire ground set. In this paper, we propose a local search algorithm for SCP, which has the following three characteristics. (1) The use of 3-flip neighborhood, which is the set of solutions obtainable from the current solution by exchanging at most three subsets. As the size of 3-flip neighborhood is O(n³), the neighborhood search becomes expensive if implemented naively. To overcome this, we propose an efficient implementation that reduces the number of candidates in the neighborhood without sacrificing the solution quality. (2) We allow the search to visit the infeasible region, and incorporate the strategic oscillation technique realized by adaptive control of penalty weights. (3) The size reduction of the problem by using the information from the Lagrangian relaxation is incorporated, which is indispensable for solving very large instances. According to computational comparisons on benchmark instances with other existing heuristic algorithms for SCP, our algorithm performs quite effectively for various types of problems, especially for very large-scale instances.     

A new Lagrangian net algorithm for solving max-bisection problems

The max-bisection problem is an NP-hard combinatorial optimization problem. In this paper, a new Lagrangian net algorithm is proposed to solve max-bisection problems. First, we relax the bisection constraints to the objective function by introducing the penalty function method. Second, a bisection solution is calculated by a discrete Hopfield neural network (DHNN). The increasing penalty factor can help the DHNN to escape from the local minimum and to get a satisfying bisection. The convergence analysis of the proposed algorithm is also presented. Finally, numerical results of large-scale G-set problems show that the proposed method can find a better optimal solutions.     

求解混合流水线调度问题的离散人工蜂群算法

本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(HFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。     

考虑生产计划的多周期切割问题优化研究

切割生产广泛存在于工业企业,是原材料加工的重要环节。已有文献主要关注单周期切割问题,但是切割计划也是生产计划的一部分,切割计划和生产计划应该协调优化,达到全局最优。本文研究考虑生产计划的多周期切割问题,目标是最小化运营成本,包括准备成本、切割成本、库存成本以及母材消耗成本。首先建立混合整数规划模型;提出动态规划启发式算法;最后对算例在多种情境下测试,分析成本因子变化对最优结果的影响。算法结果与CPLEX最优结果比较,平均误差为1.85%,表明算法是有效的。     

Analyzing the Complexity of Finding Good Neighborhood Functions for Local Search Algorithms

A drawback to using local search algorithms to address NP-hard discrete optimization problems is that many neighborhood functions have an exponential number of local optima that are not global optima (termed L-locals). A neighborhood function η is said to be stable if the number of L-locals is polynomial. A stable neighborhood function ensures that the number of L-locals does not grow too large as the instance size increases and results in improved performance for many local search algorithms. This paper studies the complexity of stable neighborhood functions for NP-hard discrete optimization problems by introducing neighborhood transformations. Neighborhood transformations between discrete optimization problems consist of a transformation of problem instances and a corresponding transformation of solutions that preserves the ordering imposed by the objective function values. In this paper, MAX Weighted Boolean SAT (MWBS), MAX Clause Weighted SAT (MCWS), and Zero-One Integer Programming (ZOIP) are shown to be NPO-complete with respect to neighborhood transformations. Therefore, if MWBS, MCWS, or ZOIP has a stable neighborhood function, then every problem in NPO has a stable neighborhood function. These results demonstrate the difficulty of finding effective neighborhood functions for NP-hard discrete optimization problems.This research is supported in part by the Air Force Office of Scientific Research (F49620-01-1-0007, FA9550-04-1-0110).     

A variable neighborhood search with an effective local search for uncapacitated multilevel lot-sizing problems

In this study, we improved the variable neighborhood search (VNS) algorithm for solving uncapacitated multilevel lot-sizing (MLLS) problems. The improvement is twofold. First, we developed an effective local search method known as the Ancestors Depth-first Traversal Search (ADTS), which can be embedded in the VNS to significantly improve the solution quality. Second, we proposed a common and efficient approach for the rapid calculation of the cost change for the VNS and other generate-and-test algorithms. The new VNS algorithm was tested against 176 benchmark problems of different scales (small, medium, and large). The experimental results show that the new VNS algorithm outperforms all of the existing algorithms in the literature for solving uncapacitated MLLS problems because it was able to find all optimal solutions (100%) for 96 small-sized problems and new best-known solutions for 5 of 40 medium-sized problems and for 30 of 40 large-sized problems.     

A comparison of local search methods for flow shop scheduling

Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing.     

A hybrid genetic local search algorithm for the permutation flowshop scheduling problem

Traditionally, the permutation flowshop scheduling problem (PFSP) was with the criterion of minimizing makespan. The permutation flowshop scheduling problem to minimize the total flowtime has attracted more attention from researchers in recent years. In this paper, a hybrid genetic local search algorithm is proposed to solve this problem with each of both criteria. The proposed algorithm hybridizes the genetic algorithm and a novel local search scheme that combines two local search methods: the Insertion Search (IS) and the Insertion Search with Cut-and-Repair (ISCR). It employs the genetic algorithm to do the global search and two local search methods to do the local search. Two local search methods play different roles in the search process. The Insertion Search is responsible for searching a small neighborhood while the Insertion Search with Cut-and-Repair is responsible for searching a large neighborhood. Furthermore, the orthogonal-array-based crossover operator is designed to enhance the GA’s capability of intensification. The experimental results show the advantage of combining the two local search methods. The performance of the proposed hybrid genetic algorithm is very competitive. For the PFSP with the total flowtime criterion, it improved 66 out of the 90 current best solutions reported in the literature in short-term search and it also improved all the 20 current best solutions reported in the literature in long-term search. For the PFSP with the makespan criterion, the proposed algorithm also outperforms the other three methods recently reported in the literature.