The Cutting Stock Problem in the Flat Glass Industry -- Selection of Stock Sizes

In the glass industry holding good stock sizes appears to have at least as big an impact on trim loss as cutting up the stock plates efficiently. In this paper two tech niques are described for determining "optimal" stock sizes, one a heuristic method and the other an integer programming algorithm. Several actual applications within the glass industry are described, and illustrative results of the improvements in wastage that have been achieved are given.     

A genetic algorithm solution for one-dimensional bundled stock cutting

This paper discusses a one-dimensional cutting stock problem in which lumber is cut in bundles. The nature of this problem is such that the traditional approaches of linear programming with an integer round-up procedure or sequential heuristics are not effective. A good solution to this problem must consider trim loss, stock usage and ending inventory levels. A genetic search algorithm is proposed and results compared to optimal solutions for an integer programming formulation of the problem.     

A branch-and-price algorithm for the two-stage guillotine cutting stock problem

We investigate the two-stage guillotine two-dimensional cutting stock problem. This problem commonly arises in the industry when small rectangular items need to be cut out of large stock sheets. We propose an integer programming formulation that extends the well-known Gilmore and Gomory model by explicitly considering solutions that are obtained by both slitting some stock sheets down their widths and others down their heights. To solve this model, we propose an exact branch-and-price algorithm. To the best of our knowledge, this is the first contribution with regard to obtaining integer optimal solutions to Gilmore and Gomory model. Extensive results, on a set of real-world problems, indicate that the proposed algorithm delivers optimal solutions for instances with up to 809 items and that the hybrid cutting strategy often yields improved solutions. Furthermore, our computational study reveals that the proposed modelling and algorithmic strategy outperforms a recently proposed arc-flow model-based solution strategy.     

Optimising a nonlinear utility function in multi-objective integer programming

In this paper we develop an algorithm to optimise a nonlinear utility function of multiple objectives over the integer efficient set. Our approach is based on identifying and updating bounds on the individual objectives as well as the optimal utility value. This is done using already known solutions, linear programming relaxations, utility function inversion, and integer programming. We develop a general optimisation algorithm for use with k objectives, and we illustrate our approach using a tri-objective integer programming problem.     

A two-objective mathematical model without cutting patterns for one-dimensional assortment problems

This paper considers a one-dimensional cutting stock and assortment problem. One of the main difficulties in formulating and solving these kinds of problems is the use of the set of cutting patterns as a parameter set in the mathematical model. Since the total number of cutting patterns to be generated may be very huge, both the generation and the use of such a set lead to computational difficulties in solution process. The purpose of this paper is therefore to develop a mathematical model without the use of cutting patterns as model parameters. We propose a new, two-objective linear integer programming model in the form of simultaneous minimization of two contradicting objectives related to the total trim loss amount and the total number of different lengths of stock rolls to be maintained as inventory, in order to fulfill a given set of cutting orders. The model does not require pre-specification of cutting patterns. We suggest a special heuristic algorithm for solving the presented model. The superiority of both the mathematical model and the solution approach is demonstrated on test problems.     

Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem

This paper deals with an unrelated machine scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. We present a zero-one integer programming formulation of this problem. The linear programming relaxation of this formulation affords a tight lower bound and often generates an integer optimal solution for the problem. By exploiting the special structures inherent in the formulation, we develop some classes of strong valid inequalities that can be used to tighten the initial formulation, as well as to provide cutting planes in the context of a branch-and-cut procedure. A major computational bottleneck is the solution of the underlying linear programming relaxation because of the extremely high degree of degeneracy inherent in the formulation. In order to overcome this difficulty, we employ a Lagrangian dual formulation to generate lower and upper bounds and to drive the branch-and-bound algorithm. As a practical instance of the unrelated machine scheduling problem, we describe a combinatorial naval defense problem. This problem seeks to schedule a set of illuminators (passive homing devices) in order to strike a given set of targets using surface-to-air missiles in a naval battle-group engagement scenario. We present computational results for this problem using suitable realistic data.     

The cutting stock problem and integer rounding

An integer programming problem is said to have the integer round-up property if its optimal value is given by the least integer greater than or equal to the optimal value of its linear programming relaxation. In this paper we prove that certain classes of cutting stock problems have the integer round-up property. The proof of these results relies upon the decomposition properties of certain knapsack polyhedra.This research was partially supported by National Science Foundation grants ECS-8005350 and 81-13534 to Cornell University.     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

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].     

One-level reformulation of the bilevel Knapsack problem using dynamic programming

In this paper, we consider the Bilevel Knapsack Problem (BKP), which is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions for a parametric Knapsack Problem. We introduce a new reformulation of the BKP into a one-level integer programming problem using dynamic programming. We propose an algorithm that allows the BKP to be solved exactly in two steps. In the first step, a dynamic programming algorithm is used to compute the set of follower reactions to leader decisions. In the second step, an integer problem that is equivalent to the BKP is solved using a branch-and-bound algorithm. Numerical results are presented to show the performance of our method.     

A partitioning algorithm for the network loading problem

This paper proposes a Benders-like partitioning algorithm to solve the network loading problem. The approach is an iterative method in which the integer programming solver is not used to produce the best integer point in the polyhedral relaxation of the set of feasible capacities. Rather, it selects an integer solution that is closest to the best known integer solution. Contrary to previous approaches, the method does not exploit the original mixed integer programming formulation of the problem. The effort of computing integer solutions is entirely left to a pure integer programming solver while valid inequalities are generated by solving standard nonlinear multicommodity flow problems. The method is compared to alternative approaches proposed in the literature and appears to be efficient for computing good upper bounds.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

Linear programs for constraint satisfaction problems

A novel representation is described that models some important NP-hard problems, such as the propositional satisfiability problem (SAT), the Traveling Salesperson Problem (TSP), the Quadratic Assignment Problem (QAP), and the Minimal Set Covering Problem (MSCP) by means of only two types of constraints: ‘choice constraints’ and ‘exclusion constraints’. In its main section the paper presents an approach for solving an m-CNF-SAT problem (Conjunctive Normal Form Satisfaction: n variables, p clauses, clause length m) by integer programming. The approach is unconventional, because 2n distinct 0–1 variables are used for each clause of the m-CNF-SAT problem. The constraint matrix A forces that for every clause exactly one 0–1 variable is set equal to 1 (choice constraint), and no two 0–1 variables, representing a literal and its complement, are both set equal to 1 (exclusion constraints). The particular m-CNF-SAT instance is coded in a cost vector, which serves for maximization of the number of satisfied clauses. The paper presents a modification of the Simplex for solving the obtained integer program. A main theorem of the paper is that this algorithm always finds a 0–1 integer solution. A solution of the integer program corresponds to a solution of the m-CNF-SAT and vice versa. The results of significant experimental tests are reported, and the procedure is compared to other approaches. The same modelling technique is then used for the Traveling Salesperson Problem, for the Minimal Set Covering, and for the Quadratic Assignment Problem: it is shown that a uniform approach is thus useful.     

Computational experience with a group theoretic integer programming algorithm

This paper gives specific computational details and experience with a group theoretic integer programming algorithm. Included among the subroutines are a matrix reduction scheme for obtaining group representations, network algorithms for solving group optimization problems, and a branch and bound search for finding optimal integer programming solutions. The innovative subroutines are shown to be efficient to compute and effective in finding good integer programming solutions and providing strong lower bounds for the branch and bound search.This research was supported in part by the U.S. Army Research Office (Durham) under contract no. DAHC04-70-C-0058. This paper is not an official National Bureau of Economic Research publication.     

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.     

New integer programming formulations and an exact algorithm for the ordered cutting stock problem

Apart from trim loss minimization, there are many other issues concerning cutting processes that arise in real production systems. One of these is related to the number of stacks that need to be opened near the cutting machines. Many researchers have worked in the last years on cutting stock problems with additional constraints on the number of open stacks. In this paper, we address a related problem: the Ordered Cutting Stock Problem (OCSP). In this case, a stack is opened for every new client's order, and it is closed only when all the items of that order are cut. The OSCP has been introduced recently in the literature. Our aim is to provide further insight into this problem. This paper describes three new integer programming formulations for solving it, and an exact algorithm based on column generation, branch-and-bound and cutting planes. We report on computational experiments on a set of random instances. The results show that good lower bounds can be computed quickly, and that optimal solutions can be found in a reasonable amount of time.     

Computational study of a column generation algorithm for bin packing and cutting stock problems

This paper reports on our attempt to design an efficient exact algorithm based on column generation for the cutting stock problem. The main focus of the research is to study the extend to which standard branch-and-bound enhancement features such as variable fixing, the tightening of the formulation with cutting planes, early branching, and rounding heuristics can be usefully incorporated in a branch-and-price algorithm. We review and compare lower bounds for the cutting stock problem. We propose a pseudo-polynomial heuristic. We discuss the implementation of the important features of the integer programming column generation algorithm and, in particular, the implementation of the branching scheme. Our computational results demonstrate the efficiency of the resulting algorithm for various classes of bin packing and cutting stock problems. Received October 18, 1996 / Revised version received May 14, 1998?Published online July 19, 1999     

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

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

Mixed integer programming models for dispatching vehicles at a container terminal

This paper presents scheduling models for dispatching vehicles to accomplish a sequence of container jobs at the container terminal, in which the starting times as well as the order of vehicles for carrying out these jobs need to be determined. To deal with this scheduling problem, three mixed 0–1 integer programming models, Model I, Model II and Model III are provided. We present interesting techniques to reformulate the two mixed integer programming models, Model I and Model II, as pure 0–1 integer programming problems with simple constraint sets and present a lower bound for the optimal value of Model I. Model III is a complicated mixed integer programming model because it involves a set of non-smooth constraints, but it can be proved that its solutions may be obtained by the so-called greedy algorithm. We present numerical results showing that Model III is the best among these three models and the greedy algorithm is capable of solving large scale problems.