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.     

Journey to the center of mathematics

Opening a copy of The Mathematical Intelligencer you may ask yourself uneasily, “What is this anyway—a mathematical journal, or what?” Or you may ask, “Where am I?” Or even “Who am I?” This sense of disorientation is at its most acute when you open to Colin Adams’s column. Relax. Breathe regularly. It’s mathematical, it’s a humor column, and it may even be harmless.     

More from the mathematical ethicist

Opening a copy ofThe Mathematical Intelligencer you may ask yourself uneasily, “What is this anyway—a mathematical journal, or what?” Or you may ask, “Where am I?” Or even “Who am I?” This sense of disorientation is at its most acute when you open to Colin Adams’s column.Relax. Breathe regularly. It’s mathematical, it’s a humor column, and it may even be harmless.     

Pivot selection methods of the Devex LP code

Pivot column and row selection methods used by the Devex code since 1965 are published here for the first time. After a fresh look at the iteration process, the author introduces dynamic column weighting factors as a means of estimating gradients for the purpose of selecting a maximum gradient column. The consequent effect of this column selection on rounding error is observed. By allowing that a constraint may not be positioned so exactly as its precise representation in the computer would imply, a wider choice of pivot row is made available, so making room for a further selection criterion based on pivot size. Three examples are given of problems having between 2500 and 5000 rows, illustrating the overall time and iteration advantages over the standard simplex methods used today. The final illustration highlights why these standard methods take so many iterations. These algorithms were originally coded for the Atlas computer and were re-coded in 1969 for the Univac 1108.     

Chaotic analysis of pressure fluctuation signal in the gas–liquid–solid slurry column

The pressure signal of a slurry column is easily obtained by using a pressure sensor, and a chaotic analysis method is used to analyze these signals in order to indicate the flow pattern of the slurry column. The slopes of the correlation integral curve indicate the flow pattern of the slurry column in various operating conditions. The flow pattern is dispersed bubble regime when the superficial velocity is low and the correlation integral curve has two slopes. The flow pattern changes into transition regime with increase in the superficial velocity, the correlation integral curve has only one slope. In the case of the flow pattern becoming a slugging regime, there are several slopes to the correlation integral curve. So it is convenient to find out the flow pattern in the slurry column by solving the slopes of the correlation integral of the pressure signal. The maximum Lyapunov exponent represents the chaos in a slurry column with various solid holdups. The maximum Lyapunov exponent is nearly similar at different heights when the flow patterns are dispersed bubble regime and slugging regime, but the maximum Lyapunov exponent at the axial height is quite different when the flow pattern is transition regime.     

The shape of the strongest column with a follower load

An elastic column subjected to a follower load loses stability, as the load increases, through undamped oscillations around its equilibrium position (flutter). For a column with fixed volume and varying but similar cross section, the existence of a critical load is shown rigorously. The necessary conditions for making the critical load and the fundamental frequency of the column stationary with respect to variations in the column shape are derived. A numerical method for finding the optimal shape is given.     

How to Choose the Right Dean for Your University: Remembering the Five P's of Deanship

Abstract

In this column, as in many other print and electronic forums, information technology (IT) is discussed at length in terms of applications for students, faculty, staff, and administrators; in terms of hardware, software, and infrastructure; and in terms of strategic planning, budgeting, and fund-raising. There is only one person on every campus who must constantly assess and balance all these factors and constituencies: the president. However, a presidential perspective—the view from 30,000 feet—does not appear often in discussions about IT in higher education. This column shares my recent conversation on the subject with Carol A. Cartwright, president of Kent State University, a CEO to whom I am privileged to have unique access.     

A unifying model for matrix-based pairing situations

We present a unifying framework for transferable utility coalitional games that are derived from a non-negative matrix in which every entry represents the value obtained by combining the corresponding row and column. We assume that every row and every column is associated with a player, and that every player is associated with at most one row and at most one column. The instances arising from this framework are called pairing games, and they encompass assignment games and permutation games as two polar cases. We show that the core of a pairing game is always non-empty by proving that the set of pairing games coincides with the set of permutation games. Then we exploit the wide range of situations comprised in our framework to investigate the relationship between pairing games that have different player sets, but are defined by the same underlying matrix. We show that the core and the set of extreme core allocations are immune to the merging of a row player with a column player. Moreover, the core is also immune to the reverse manipulation, i.e., to the splitting of a player into a row player and a column player. Other common solution concepts fail to be either merging-proof or splitting-proof in general.     

Optimum shape of columns with general conservative end loading

In this paper, the optimal shape of a column with the most general conservative state of loading is determined. The boundary conditions of a column contain, in general, 16 parameters; it is shown that the boundary values of a column with general conservative loading may, at most, depend on nine constants. The influence of these parameters on the optimal shape and corresponding buckling load is also obtained.     

Buckling of stepped composite columns

The stability of elastic columns subjected to axial pressure is studied. An elastic multistepped column with rectangular cross sections are considered assuming that at the re-entrant corners of the column stable cracks are located. The influence of a crack on the loss of stability of the column is described by means of local flexibility and the function of compliance coupled with the stress intensity factor, which is known from the linear elastic fracture mechanics. A column with a single step is studied in more detail. The influence of crack location and length on the buckling load is assessed numerically. Russian translation published in Mekhanika Kompozitnykh Materialov, Vol. 42, No. 1, pp. 87–100, January–February, 2006.     

基于列随机矩阵的逐次差分代换与正半定型的机械化判定

本文选择列随机平均矩阵T_n作为基本代换矩阵,建立了基于T_n的逐次差分代换方法.获得了R_+~n上正半定型,不定型判定的充要条件.并进一步证明了:正定型的差分代换集序列正向终止.根据这些结果编写的Maple程序TSDS3,能够自动证明代数型不等式,对不成立的不等式总能输出反例.该程序虽可能不停机,但大量的应用实例证实了该方法的实用性.     

基于BP网络的混凝土耗能器骨架曲线拟合

结合5种混凝土延性柱耗能器在低周期反复荷载作用下的试验数据研究,利用神经网络的工作原理,通过建立神经网络的输入层、隐含层、输出层,确定输入单元、输出单元和隐含层节点数,从而建立了BP神经网络的模型,并根据已有的部分试验数据数据.对网络进行训练,对各种混凝土延性柱耗能器骨架曲线进行了预测拟合,实现混凝土延性柱耗能器骨架曲线的数字化,使其成为具有分析和判断的拟合曲线功能,完整的描绘混凝土延性柱耗能器的骨架曲线,为后续混凝土延性柱耗能器性能研究的仿真模拟提供了可靠的数据模型.结果表明,这种方法是可行的.     

特征标表各列零点个数不超过2个的有限群

继续考虑特征标的零点对有限群结构的影响, 并给出了特征标表中 每列至多有两个零点的有限群的分类,从而完成了特征标表中每列至多 $p$ ($p$是群的阶的最小素因子)个零点的有限群的完全分类.     

Optimal design of multi-purpose structures

The paper presents the optimal (maximum transverse stiffness) design of an elastic, simply supported member of given volume that is to serve as a beam or as a column at different times during its design life. The optimal design can be interpreted in two ways. It is the design that has the maximum Euler buckling load in column action, subject to a prescribed maximum deflection in beam action under a uniformly distributed load; it is also the design that has the least deflection at midspan under a uniformly distributed load, subject to a lower limit on its buckling load in column action. The effectiveness of the optimal design is judged by comparing it with a prismatic bar of the same volume.The author is grateful to Professor W. Prager for suggesting several improvements to an earlier version of the paper.     

Optimization of the capacity of wireless mesh networks

This is a summary of the authors PhD thesis supervised by Hervé Rivano and defended on 29 October 2009 at the Université de Nice-Sophia Antipolis. The thesis is written in French and is available from . This work deals with the optimization of the capacity of wireless mesh networks, defined as the throughput offered to each flow. We develop optimization models integrating the cross-layer characteristics of radio communications. The joint routing and scheduling is studied and solved using column generation. A linear formulation focusing on the transport capacity available on the network cuts is derived. We prove the equivalence of the models, and adapt the resolution method into a cross line and column generation process. Thorough tests, a contention area located around the gateways which constraints the capacity is highlighted. These results are applied to a quantitative study of the effects of acknowledgments on the capacity. Finally, a stability study of a protocol routing a traffic injected arbitrarily is investigated.     

On the convergence of the block principal pivotal algorithm for the LCP

We show that the block principal pivot algorithm (BPPA) for the linear complementarity problem (LCP) solves the problem for a special class of matrices in at most n block principal pivot steps. We provide cycling examples for the BPPA in which the matrix is positive definite or symmetric positive definite. For LCP of order three, we prove that strict column (row) diagonal dominance is a sufficient condition to avoid cycling.     

Decomposition methods for the lot-sizing and cutting-stock problems in paper industries

We investigate the one-dimensional cutting-stock problem integrated with the lot-sizing problem in the context of paper industries. The production process in paper mill industries consists of producing raw materials characterized by rolls of paper and cutting them into smaller rolls according to customer requirements. Typically, both problems are dealt with in sequence, but if the decisions concerning the cutting patterns and the production of rolls are made together, it can result in better resource management. We investigate Dantzig–Wolfe decompositions and develop column generation techniques to obtain upper and lower bounds for the integrated problem. First, we analyze the classical column generation method for the cutting-stock problem embedded in the integrated problem. Second, we propose the machine decomposition that is compared with the classical period decomposition for the lot-sizing problem. The machine decomposition model and the period decomposition model provide the same lower bound, which is recognized as being better than the linear relaxation of the classical lot-sizing model. To obtain feasible solutions, a rounding heuristic is applied after the column generation method. In addition, we propose a method that combines an adaptive large neighborhood search and column generation method, which is performed on the machine decomposition model. We carried out computational experiments on instances from the literature and on instances adapted from real-world data. The rounding heuristic applied to the first column generation method and the adaptive large neighborhood search combined with the column generation method are efficient and competitive.     

On the integral equation method for buckling loads

An initial value method for the integral equation of the column is presented for determining the buckling load of columns. The differential equation of the column is reduced to a Fredholm integral equation. An initial value problem is derived for this integral equation, which is reduced to a set of ordinary differential equations with prescribed initial conditions in order to find the Fredholm resolvent. The singularities of the resolvent occur at the eigenvalues. Integration of the equations proceeds until the integrals become excessively large, indicating that a critical load has been reached. To check this method, numerical results are given for two examples, for which the critical load is well known. One is the Euler load of a simply supported beam, and the other case is the buckling load of a cantilever beam under its own weight. The advantage of this initial value method is that it can be applied easily to solve other nonlinear problems for which the critical loads are unknown. This approach will be illustrated in future papers.     

Biproportional scaling of matrices and the iterative proportional fitting procedure

A short proof is given of the necessary and sufficient conditions for the convergence of the Iterative Proportional Fitting procedure. The input consists of a nonnegative matrix and of positive target marginals for row sums and for column sums. The output is a sequence of scaled matrices to approximate the biproportional fit, that is, the scaling of the input matrix by means of row and column divisors in order to fit row and column sums to target marginals. Generally it is shown that certain structural properties of a biproportional scaling do not depend on the particular sequence used to approximate it. Specifically, the sequence that emerges from the Iterative Proportional Fitting procedure is analyzed by means of the L ₁-error that measures how current row and column sums compare to their target marginals. As a new result a formula for the limiting L ₁-error is obtained. The formula is in terms of partial sums of the target marginals, and easily yields the other well-known convergence characterizations.     

Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem

The routing and wavelength assignment (RWA) problem typically occurs in wavelength division multiplexing optical networks. Given a number of available wavelengths, we consider here the problem of maximising the number of accepted connections with respect to the clash and continuity constraints. We first propose a new strategy which combines two existing models. This leads to an improved column generation scheme. We also present two heuristics to compute feasible solutions: a hybrid heuristic and the integer solution at the root node of the column generation. Our approaches are compared with the best existing results on a set of classic RWA instances.