Reducing the number of cuts in generating three-staged cutting patterns

Three-staged guillotine patterns are widely used in the manufacturing industry to cut stock plates into rectangular items. The cutting cost often increases with the number of cuts required. This paper focuses on the rectangular two-dimensional cutting stock problem, where three-staged guillotine patterns are used, and the objective is to minimize the sum of plate and cutting costs. The column generation framework is used to solve the problem. It uses a pattern-generation procedure to obtain the patterns. The cutting cost is considered in both the pattern-generation procedure and the objective of the linear programming formulation. The computational results indicate that the approach can reduce the number of cuts, without increasing the plate cost.     

Heuristic for constrained two-dimensional three-staged patterns

Three-staged cutting patterns are often used in dividing large plates into small rectangular items. Vertical cuts separate the plate into segments in the first stage, horizontal cuts split each segment into strips in the second stage, and vertical cuts divide each strip into items in the third stage. A heuristic algorithm for generating constrained three-staged patterns is presented in this paper. The optimization objective is to maximize the pattern value that is the total value of the included items, while the frequency of each item type should not exceed the specified upper bound. The algorithm uses an exact procedure to generate strips and two heuristic procedures to generate segments and the pattern. The pattern-generation procedure first determines an initial solution and then uses its information to generate more segments to extend the solution space. Computational results show that the algorithm is effective in improving solution quality.     

A new algorithm for multi-dimensional dynamic programming problems

The new algorithm presented here solves medium size multi-dimensional dynamic programming problems in a relatively short computational time with no fast-memory restraints. The algorithm converges to the global optimal solution under some differentiability and convexity assumptions.The procedure is to solve a succession of dynamic programming problems, the state sets of which are limited to only a very small subset of the original state space. The interrelated definition of state sets for successive subproblems facilitates an algorithmic convergence while moving the subsets to contain the optimal states at the end.     

A dynamic programming optimization procedure for a two-product biomass-to-methane conversion system

The conversion of biomass to methane involves the scheduling of perishable material into a production facility with a decreasing production rate. A complex optimal scheduling problem arises when two different types of biomass are used in a conversion facility of limited capacity. The decision variables for the scheduler are the replacement times of old material with inventoried material and the order in which the different types should be processed. Such a scheduling problem is formulated as a dynamic programming problem in which an unusual time transformation allows for a significant reduction of the state space.     

A procedure for one-parametric linear programming

A procedure is proposed for the parametric linear programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The solution vector and the optimum value are determined explicitly as rational functions of the parameter. In addition to standard linear programming technique, only the determination of eigenvalues is required. The procedure is compared to those by Dinkelbach and Zsigmond, and a numerical example is given.     

Intensional dynamic programming. A Rosetta stone for structured dynamic programming

We present intensional dynamic programming (IDP), a generic framework for structured dynamic programming over atomic, propositional and relational representations of states and actions. We first develop set-based dynamic programming and show its equivalence with classical dynamic programming. We then show how to describe state sets intensionally using any form of structured knowledge representation and obtain a generic algorithm that can optimally solve large, even infinite, MDPs without explicit state space enumeration. We derive two new Bellman backup operators and algorithms. In order to support the view of IDP as a Rosetta stone for structured dynamic programming, we review many existing techniques that employ either propositional or relational knowledge representation frameworks.     

A dynamic programming based reduction procedure for the multidimensional 0–1 knapsack problem

This paper presents a preprocessing procedure for the 0–1 multidimensional knapsack problem. First, a non-increasing sequence of upper bounds is generated by solving LP-relaxations. Then, a non-decreasing sequence of lower bounds is built using dynamic programming. The comparison of the two sequences allows either to prove that the best feasible solution obtained is optimal, or to fix a subset of variables to their optimal values. In addition, a heuristic solution is obtained. Computational experiments with a set of large-scale instances show the efficiency of our reduction scheme. Particularly, it is shown that our approach allows to reduce the CPU time of a leading commercial software.     

A new dynamic programming algorithm for the single item capacitated dynamic lot size model

We develop a new dynamic programming method for the single item capacitated dynamic lot size model with non-negative demands and no backlogging. This approach builds the Optimal value function in piecewise linear segments. It works very well on the test problems, requiring less than 0.3 seconds to solve problems with 48 periods on a VAX 8600. Problems with the time horizon up to 768 periods are solved. Empirically, the computing effort increases only at a quadratic rate relative to the number of periods in the time horizon.This research was supported in part by NSF grants DDM-8814075 and DMC-8504786.     

A sequential heuristic procedure for one-dimensional cutting

The article examines the Sequential Heuristic Procedure (SHP) for optimising one-dimensional stock cutting when all stock lengths are different. In order to solve a bicriterial multidimensional knapsack problem with side constraints a lexicographic approach is applied. An item-oriented solution was found through a combination of approximations and heuristics that minimize the influence of ending conditions leading to almost optimal solutions. The computer program CUT was developed, based on the proposed algorithm. Two sample problems are presented and solved. A statistical analysis of parameters that affect material utilisation was also made.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

A logarithmic barrier cutting plane method for convex programming

The paper presents a logarithmic barrier cutting plane algorithm for convex (possibly non-smooth, semi-infinite) programming. Most cutting plane methods, like that of Kelley, and Cheney and Goldstein, solve a linear approximation (localization) of the problem and then generate an additional cut to remove the linear program's optimal point. Other methods, like the central cutting plane methods of Elzinga-Moore and Goffin-Vial, calculate a center of the linear approximation and then adjust the level of the objective, or separate the current center from the feasible set. In contrast to these existing techniques, we develop a method which does not solve the linear relaxations to optimality, but rather stays in the interior of the feasible set. The iterates follow the central path of a linear relaxation, until the current iterate either leaves the feasible set or is too close to the boundary. When this occurs, a new cut is generated and the algorithm iterates. We use the tools developed by den Hertog, Roos and Terlaky to analyze the effect of adding and deleting constraints in long-step logarithmic barrier methods for linear programming. Finally, implementation issues and computational results are presented. The test problems come from the class of numerically difficult convex geometric and semi-infinite programming problems.This work was completed under the support of a research grant of SHELL.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116.     

A relaxed cutting plane method for semi-infinite semi-definite programming

In this paper, we develop two discretization algorithms with a cutting plane scheme for solving combined semi-infinite and semi-definite programming problems, i.e., a general algorithm when the parameter set is a compact set and a typical algorithm when the parameter set is a box set in the m-dimensional space. We prove that the accumulation point of the sequence points generated by the two algorithms is an optimal solution of the combined semi-infinite and semi-definite programming problem under suitable assumption conditions. Two examples are given to illustrate the effectiveness of the typical algorithm.     

A central cutting plane algorithm for the convex programming problem

An algorithm is developed for solving the convex programming problem which iteratively proceeds to the optimum by constructing a cutting plane through the center of a polyhedral approximation to the optimum. This generates a sequence of primal feasible points whose limit points satisfy the Kuhn—Tucker conditions of the problem. Additionally, we present a simple, effective rule for dropping prior cuts, an easily calculated bound on the objective function, and a rate of convergence.     

A cutting plane method from analytic centers for stochastic programming

The stochastic linear programming problem with recourse has a dual block-angular structure. It can thus be handled by Benders' decomposition or by Kelley's method of cutting planes; equivalently the dual problem has a primal block-angular structure and can be handled by Dantzig-Wolfe decomposition—the two approaches are in fact identical by duality. Here we shall investigate the use of the method of cutting planes from analytic centers applied to similar formulations. The only significant difference form the aforementioned methods is that new cutting planes (or columns, by duality) will be generated not from the optimum of the linear programming relaxation, but from the analytic center of the set of localization.This research has been supported by the Fonds National de la Recherche Scientifique Suisse (grant # 12-26434.89), NSERC-Canada and FCAR-Quebec.Corresponding author.     

A procedure for parameterizing a constraint in linear programming

A post-optimal procedure for parameterizing a constraint in linear programming is proposed. In the derivation of the procedure, the technique of pivotal operations (Jordan eliminations) is applied. The procedure is compared to another by Orchard-Hays [2], and a numerical example of the procedure is provided.     

A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem

In this paper we present a heuristic method to generate constrained two-dimensional guillotine cutting patterns. This problem appears in different industrial processes of cutting rectangular plates to produce ordered items, such as in the glass, furniture and circuit board business. The method uses a state space relaxation of a dynamic programming formulation of the problem and a state space ascent procedure of subgradient optimization type. We propose the combination of this existing approach with an and/or-graph search and an inner heuristic that turns infeasible solutions provided in each step of the ascent procedure into feasible solutions. Results for benchmark and randomly generated instances indicate that the method’s performance is competitive compared to other methods proposed in the literature. One of its advantages is that it often produces a relatively tight upper bound to the optimal value. Moreover, in most cases for which an optimal solution is obtained, it also provides a certificate of optimality.     

A new algorithm for quadratic programming

We present a new finite algorithm for quadratic programming. Our algorithm is based on the solution procedures of linear programming (pivoting, Bland's rule, Hungarian Methods, criss-cross method), however this method does not require the enlargement of the basic tableau as Frank-Wolfe method does. It can be considered as a feasible point active-set method. We solve linear equation systems in oder to reach an active constraint set (complementary solutions) and we solve a feasibility problem in order to check that optimality can be reached on this active set or to improve the actual solution. This algorithm is a straightforward generalization of Klafszky's and Terlaky's Hungarian Method. It has nearly the same structure as Ritter's algorithm (which is based on conjugate directions), but it does not use conjugate directions.     

A dynamic programming heuristic for the P-median problem

A new heuristic algorithm is proposed for the P-median problem. The heuristic restricts the size of the state space of a dynamic programming algorithm. The approach may be viewed as an extension of the myopic or greedy adding algorithm for the P-median model. The approach allows planners to identify a large number of solutions all of which perform well with respect to the P-median objective of minimizing the demand weighted average distance between customer locations and the nearest of the P selected facilities. In addition, the results indicate regions in which it is desirable to locate facilities. Computational results from three test problems are discussed.