T-shape homogenous block patterns for the two-dimensional cutting problem

This paper presents an algorithm for unconstrained T-shape homogenous block cutting patterns of rectangular pieces. A vertical cut divides the stock sheet into two segments. Each segment consists of sections that have the same length and direction. A section contains a row of homogenous blocks. A homogenous block consists of homogenous strips of the same piece type. Each cut on the block produces just one strip. The directions of two strips cut successively from a block are either parallel or orthogonal. The algorithm uses a dynamic programming recursion to generate optimal blocks, solves knapsack problems to obtain the block layouts on the sections and the section layout on segments of various lengths, and optimally selects two segments to compose the cutting pattern. The computational results indicate that the algorithm is efficient in improving material usage, and the computation time is reasonable.     

Fast heuristic for constrained homogenous T-shape cutting patterns

Homogenous T-shape (HTS) cutting patterns are welcomed when the two-phase process is used to produce rectangular pieces from the stock plate, where the plate is cut into homogenous strips at the first phase, and the strips are divided into pieces at the second phase. A heuristic is presented for generating constrained HTS patterns, where the objective is to maximize the pattern value that is equal to the total value of the included pieces, observing the upper bound constraint on the frequency of each piece type. The heuristic is based on dynamic programming and branch-and-bound techniques. It can yield solutions close to optimal with short computation time. By providing good initial solutions, the heuristic can greatly improve the time efficiency of an existing exact branch-and-bound algorithm.     

Heuristics with a new block strategy for the single and multiple containers loading problems

A heuristic algorithm using new block strategy for the heterogeneous single and multiple containers loading problem (CLP) is proposed in this paper. In order to solve the single CLP, this algorithm fills unused spaces with the homogeneous load-blocks of identically oriented boxes and splits residual space into three child-spaces starting with an empty container. An initial container pattern is first built applying this approach recursively until all boxes are stowed or no unused spaces are left. And then, alternative container patterns are generated after replacing the load-blocks of the pattern-determining spaces in the initial container pattern with the alternative-blocks previously stored. Finally, an improvement procedure compares these alternatives with the initial container pattern to identify an improved container pattern. An algorithm for the multiple CLP uses the single CLP algorithm to generate an initial solution and uses improvement procedures to improve the initial solution. Numerical experiments with 715 test cases for the single CLP and 47 test cases for the multiple the CLP revealed the excellent performance of this algorithm.     

A polynomial algorithm for the earthwork allocation problem with borrow and waste site selection

In road construction projects, earthwork is planned together with horizontal and vertical alignments. This study focuses on earthwork operations that basically include cutting the hills and filling the holes on the road path. The candidate borrow and waste sites can also be used to obtain or heap earth when the available cut and fill amounts are not balanced or operating these sites reduces the total earthwork cost. Total earthwork cost contains the transportation cost and the overall cost related to opening the candidate sites. The problem is to determine which borrow and waste sites to operate, and the earth flows between cut, fill, waste, and borrow sites such that the total cost is minimized. It is shown that the problem is a generalization of the well-known lot-sizing problem. A fixed charge network flow problem formulation is presented, and a polynomial time dynamic programming algorithm is developed for solving the problem.     

熊蜂用于控制飞行的气动力和力矩

采用计算流体力学方法研究熊蜂用于控制飞行的气动力和力矩．结果表明,悬停时,每1个翅膀运动参数主要控制1个或2个气动力和力矩．当左右翅运动学参数对称变化时,改变拍动幅角（或拍动频率）主要可使垂直力改变．改变平均拍动角主要可使俯仰力矩改变．改变拍动攻角,上拍和下拍攻角等值同向变化时,主要可使垂直力改变;等值反向变化时,主要可使水平力改变．改变转动模式,当翅膀前拍靠近昆虫腹部和后拍靠近昆虫背部的转动模式相同变化时,主要可使垂直力改变;当翅膀前拍靠近昆虫腹部和后拍靠近昆虫背部的转动模式相反变化时,主要可使水平力和俯仰力矩改变．改变转动时间对气动力和力矩几乎无影响．当左右翅运动学参数反对称变化时,改变拍动幅角（或拍动频率）主要可使滚转力矩改变．改变拍动攻角,上拍和下拍攻角等值同向变化时,主要可使滚转力矩改变;等值反向变化时,主要可使偏航力矩改变．改变转动模式,当翅膀前拍靠近昆虫腹部和后拍靠近昆虫背部的转动模式相同变化时,主要可使侧向力和滚转力矩改变;当翅膀前拍靠近昆虫腹部和后拍靠近昆虫背部的转动模式相反变化时,主要可使偏航力矩改变．改变翅膀运动参数可分别控制3个方向的力矩及垂直力．改变拍动角可以改变垂直力;改变拍动角的平均位置可以改变俯仰力矩;反对称改变左右翅的拍动攻角可以改变滚转力矩;反对称改变拍动起始时刻可以改变偏航力矩．通过对翅膀运动参数的适当调整熊蜂即可实现快速转弯飞行．     

A new dynamic programming procedure for three-staged cutting patterns

Three-staged patterns are often used to solve the 2D cutting stock problem of rectangular items. They can be divided into items in three stages: Vertical cuts divide the plate into segments; then horizontal cuts divide the segments into strips, and finally vertical cuts divide the strips into items. An algorithm for unconstrained three-staged patterns is presented, where a set of rectangular item types are packed into the plate so as to maximize the pattern value, and there is no constraint on the frequencies of each item type. It can be used jointly with the linear programming approach to solve the cutting stock problem. The algorithm solves three large knapsack problems to obtain the optimal pattern: One for the item layout on the widest strip, one for the strip layout on the longest segment, and the third for the segment layout on the plate. The computational results indicate that the algorithm is efficient.     

Branch and bound algorithm for a transfer line design problem: Stations with sequentially activated multi-spindle heads

In this paper, a new transfer line balancing problem is considered. The main difference from the simple assembly line balancing problem is that the operations are grouped into blocks (batches). All the operations of the same block are carried out simultaneously by one piece of equipment (multi-spindle head). Nevertheless, the blocks assigned to the same workstation are executed in series. The line cost consists of the sum of block and workstation costs. At the considered line design stage, the set of all available blocks is given. The aim is to find a subset from the given set of available blocks and to find a partition of this subset to workstations such that each operation is executed once and the line cost is minimal while all the precedence, cycle time, and compatibility (operation inclusion and block exclusion) constraints are respected. A new lower bound based on solving a special set partitioning problem is presented and a branch and bound algorithm is developed. The experimental results prove the quality of the lower bound and applicability of the suggested branch and bound algorithm for medium sized industrial cases.     

Cartographic line simplification and polygon CSG formulæ in O(n log n) time

A constructive solid geometry (CSG) conversion for a polygon takes a list of vertices and produces a formula representing the polygon as an intersection and union of primitive halfspaces. The cartographers' favorite line simplification algorithm recursively selects from a list of data points those to be used to represent a linear feature, such as a coastline, on a map. By using a data structure that maintains convex hulls of polygonal lines under splits, both were known to have O(n log n) time solutions in the worst-case. This paper shows that both are easier than sorting by presenting an O(n log^* n) algorithm for maintaining convex hulls under splits at extreme points. It opens the question of whether there are practical, linear-time solutions to these problems.     

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.     

Algorithms for solving nonlinear dynamic decision models

In this paper we discuss two Newton-type algorithms for solving economic models. The models are preprocessed by reordering the equations in order to minimize the dimension of the simultaneous block. The solution algorithms are then applied to this block. The algorithms evaluate numerically, as required, selected columns of the Jacobian of the simultaneous part. Provisions also exist for similar systems to be solved, if possible, without actually reinitialising the Jacobian. One of the algorithms also uses the Broyden update to improve the Jacobian. Global convergence is maintained by an Armijo-type stepsize strategy.The global and local convergence of the quasi-Newton algorithm is discussed. A novel result is established for convergence under relaxed descent directions and relating the achievement of unit stepsizes to the accuracy of the Jacobian approximation. Furthermore, a simple derivation of the Dennis-Moré characterisation of the Q-superlinear convergence rate is given.The model equation reordering algorithm is also described. The model is reordered to define heart and loop variables. This is also applied recursively to the subgraph formed by the loop variables to reduce the total number of above diagonal elements in the Jacobian of the complete system. The extension of the solution algorithms to consistent expectations are discussed. The algorithms are compared with Gauss-Seidel SOR algorithms using the USA and Spanish models of the OECD Interlink system.     

The generalized faro shuffle

The standard faro shuffle, an idealized riffle shuffle, divides the deck into two equal portions, and perfectly interlaces them. The simple cut takes one card from the top to the bottom of the deck. It is known that for decks of even size, the faro shuffle and simple cut generate all possible permutations, while if the deck is of odu size, only a small fraction are available. This paper considers a generalized faro shuffle wherein the deck is divided into n rather than 2, portions and these portions are “interlaced” together. It is shown that the generalized faro shuffle and the simple cut generate either the symmetric group of the deck, the alternating group of the deck, or in one special case, only a small fraction of the possible permutations. Whether the symmetric group or alternating group is generated depends on the parity of the simple cut and the generalized faro shuffle as group operations.     

An approximation algorithm for cutting out convex polygons

We provide an O(logn)-approximation algorithm for the following problem. Given a convex n-gon P, drawn on a convex piece of paper, cut P out of the piece of paper in the cheapest possible way. No polynomial-time approximation algorithm was known for this problem posed in 1985.     

An algorithm for solving the indefinite least squares problem with equality constraints

An algorithm for computing the solution of indefinite least squares problems and of indefinite least squares problems with equality constrained is presented. Such problems arise when solving total least squares problems and in H ^∞-smoothing. The proposed algorithm relies only on stable orthogonal transformations reducing recursively the associated augmented matrix to proper block anti-triangular form. Some numerical results are reported showing the properties of the algorithm.     

Determining an optimum location for an undesirable facility in a workroom environment

This paper deals with the problem of placing an undesirable but necessary piece of equipment, process or facility into a working environment. Locating a piece of equipment that produces contaminants or creates stresses for nearby workers, placing a storage facility for flammable materials or locating hazardous waste in the workroom environment, are all typical examples of the undesirable facility location problem. The degree of undesirability between an existing facility or worker and the new undesirable entity is reflected through a weighting factor. The problem is formally defined to be the selection of a location within the convex region that maximizes the minimum weighted Euclidean distance with respect to all existing facilities. A ‘Maximin’ model is formulated and two solution procedures introduced. A geometrical approach and an algorithmic approach are described in detail. An example is provided for each solution procedure and the computational efficiency of the algorithm is discussed and illustrated.     

Convex n-ominoes

Unit squares having their vertices at integer points in the Carresian plane are called cells. A connected union of n distinct cells having no finite cut set is an n-omino. Two n-ominoes are the same if one is mapped onto the other by a translation of the plane. An n-omino is convex if the cells in each row and each column to an a connected strip. When viewed from a distance, most convex n-ominoes resemble rods tilted 45° from the vertical with horizontal (and vertical) thickness roughly equal to 2.37597. If c(n) denotes the number of convex n-ominoes, then c(n) ～ fyⁿ, where y = 2.30914 and f = 2.67564. (It is understood that all constants are accurate to within -$\text{1}\text{2}$ in the last place.)     

Symmetric chains,Gelfand–Tsetlin chains,and the Terwilliger algebra of the binary Hamming scheme

The de Bruijn–Tengbergen–Kruyswijk (BTK) construction is a simple algorithm that produces an explicit symmetric chain decomposition of a product of chains. We linearize the BTK algorithm and show that it produces an explicit symmetric Jordan basis (SJB). In the special case of a Boolean algebra, the resulting SJB is orthogonal with respect to the standard inner product and, moreover, we can write down an explicit formula for the ratio of the lengths of the successive vectors in these chains (i.e., the singular values). This yields a new constructive proof of the explicit block diagonalization of the Terwilliger algebra of the binary Hamming scheme. We also give a representation theoretic characterization of this basis that explains its orthogonality, namely, that it is the canonically defined (up to scalars) symmetric Gelfand–Tsetlin basis.     

The diameter and radius of simple graphs

This paper develops some properties of simple blocks—block graphs which are determined up to isomorphism by the degrees of their vertices. It is first shown that if G is a simple block graph on six or more points, then G cannot be minimal or critical and must contain a triangle—have girth three.Then the most useful necessary conditions for a graph to be simple are established; if a graph is simple, it has diameter less than or equal to three and dradius less than or equal to two.     

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.     

Generalized Lorenz models and their routes to chaos. II. Energy-conserving horizontal mode truncations

All attempts to generalize the three-dimensional Lorenz model by selecting higher-order Fourier modes can be divided into three categories, namely: vertical, horizontal and vertical–horizontal mode truncations. The previous study showed that the first method allowed only construction of a nine-dimensional system when the selected modes were energy-conserving. The results presented in this paper demonstrate that a five-dimensional model is the lowest-order generalized Lorenz model that can be constructed by the second method and that its route to chaos is the same as that observed in the original Lorenz model. It is shown that the onset of chaos in both systems is determined by a number of modes that describe the vertical temperature difference in a convection roll. In addition, a simple rule that allows selecting modes that conserve energy for each method is derived.     

INTERIOR POINT PROJECTED REDUCED HESSIAN METHOD WITH TRUST REGION STRATEGY FOR NONLINEAR CONSTRAINED OPTIMIZATION

§1　IntroductionIn this paper we analyze an interior point scaling projected reduced Hessian methodwith trust region strategy for solving the nonlinear equality constrained optimizationproblem with nonnegative constraints on variables:min　f(x)s.t.　c(x) =0 (1.1)x≥0where f∶Rn→R is the smooth nonlinear function,notnecessarily convex and c(x)∶Rn→Rm(m≤n) is the vector nonlinear function.There are quite a few articles proposing localsequential quadratic programming reduced Hessian methods…