Generating unconstrained two-dimensional non-guillotine cutting patterns by a Recursive Partitioning Algorithm

In this study, a dynamic programming approach to deal with the unconstrained two-dimensional non-guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two-staged and non-staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of pro blem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method. Journal of the Operational Research Society (2012) 63, 183-200. doi: 10.1057/jors.2011.6 Published online 17 August 2011

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50 000 instances). It is also effective for solving the instances of problem set Cover III (almost 100 000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes. Journal of the Operational Research Society (2010) 61, 306-320. doi: 10.1057/jors.2008.141 Published online 4 February 2009

A communication model and partitioning algorithm for streaming applications for an embedded MPSoC

Energy efficient embedded computing enables new application scenarios in mobile devices like software-defined radio and video processing. The hierarchical multiprocessor considered in this work may contain dozens or hundreds of resource efficient VLIW CPUs. Programming this number of CPU cores is a complex task requiring compiler support. The stream programming paradigm provides beneficial properties that help to support automatic partitioning. This work describes a compiler for streaming applications targeting the self-build hierarchical CoreVA-MPSoC multiprocessor platform. The compiler is supported by a programming model that is tailored to fit the streaming programming paradigm. We present a novel simulated-annealing (SA) based partitioning algorithm, called Smart SA. The overall speedup of Smart SA is 12.84 for an MPSoC with 16 CPU cores compared to a single CPU implementation. Comparison with a state of the art partitioning algorithm shows an average performance improvement of 34.07%.

Radiotherapy and temozolomide for newly diagnosed glioblastoma: recursive partitioning analysis of the EORTC 26981/22981-NCIC CE3 phase III randomized trial

PURPOSE: The European Organisation for Research and Treatment of Cancer and National Cancer Institute of Canada trial on temozolomide (TMZ) and radiotherapy (RT) in glioblastoma (GBM) has demonstrated that the combination of TMZ and RT conferred a significant and meaningful survival advantage compared with RT alone. We evaluated in this trial whether the recursive partitioning analysis (RPA) retains its overall prognostic value and what the benefit of the combined modality is in each RPA class. PATIENTS AND METHODS: Five hundred seventy-three patients with newly diagnosed GBM were randomly assigned to standard postoperative RT or to the same RT with concomitant TMZ followed by adjuvant TMZ. The primary end point was overall survival. The European Organisation for Research and Treatment of Cancer RPA used accounts for age, WHO performance status, extent of surgery, and the Mini-Mental Status Examination. RESULTS: Overall survival was statistically different among RPA classes III, IV, and V, with median survival times of 17, 15, and 10 months, respectively, and 2-year survival rates of 32%, 19%, and 11%, respectively (P < .0001). Survival with combined TMZ/RT was higher in RPA class III, with 21 months median survival time and a 43% 2-year survival rate, versus 15 months and 20% for RT alone (P = .006). In RPA class IV, the survival advantage remained significant, with median survival times of 16 v 13 months, respectively, and 2-year survival rates of 28% v 11%, respectively (P = .0001). In RPA class V, however, the survival advantage of RT/TMZ was of borderline significance (P = .054). CONCLUSION: RPA retains its prognostic significance overall as well as in patients receiving RT with or without TMZ for newly diagnosed GBM, particularly in classes III and IV.

Tools for mixed-criticality partitioned systems: partitioning algorithm and extensibility support

The development of mixed-criticality virtualized multicore systems poses new challenges that are being subject of active research work. There is an additional complexity: it is now required to identify a set of partitions, and allocate applications to partitions. In this job, a number of issues have to be considered, such as the criticality level of the application, security and dependability requirements, operating system used by the application, time requirements granularity, specific hardware needs, etc. MultiPARTES [6] toolset relies on Model Driven Engineering (MDE) [12], which is a suitable approach in this setting. In this paper, it is described the support provided for automatic system partitioning generation and toolset extensibility.

Recursive partitioning for tumor classification with gene expression microarray data

Precise classification of tumors is critically important for cancer diagnosis and treatment. It is also a scientifically challenging task. Recently, efforts have been made to use gene expression profiles to improve the precision of classification, with limited success. Using a published data set for purposes of comparison, we introduce a methodology based on classification trees and demonstrate that it is significantly more accurate for discriminating among distinct colon cancer tissues than other statistical approaches used heretofore. In addition, competing classification trees are displayed, which suggest that different genes may coregulate colon cancers.

Methodological shifts in ratio-based modelling of corporate collapse

The year 1968 saw a major shift from univariate to multivariate methodological approaches to ratio-based modelling of corporate collapse. This was facilitated by the introduction of a new statistical tool called Multiple Discriminant Analysis (MDA). However, it did not take long before other statistical tools were developed. The primary objective for developing these tools was to enable deriving models that would at least do as good a job asMDA, but rely on fewer assumptions. With the introduction of new statistical tools, researchers became pre-occupied with testing them in signalling collapse. lLTUong the ratio-based approaches were Logit analysis, Neural Network analysis, Probit analysis, ID3, Recursive Partitioning Algorithm, Rough Sets analysis, Decomposition analysis, Going Concern Advisor, Koundinya and Purl judgmental approach, Tabu Search and Mixed Logit analysis. Regardless of which methodological approach was chosen, most were compared to MDA. This paper reviews these various approaches. Emphasis is placed on how they fared against MDA in signalling corporate collapse.

A parallel wilf algorithm for complex zeros of a polynomial

A global recursive bisection algorithm is described for computing the complex zeros of a polynomial. It has complexityO(n 3 p) wheren is the degree of the polynomial andp the bit precision requirement. Ifn processors are available, it can be realized in parallel with complexityO(n 2 p); also it can be implemented using exact arithmetic. A combined Wilf-Hansen algorithm is suggested for reduction in complexity.

Parallel circuit partitioning on a reduced array architecture

The physical design of a VLSI circuit involves circuit partitioning as a subtask. Typically, it is necessary to partition a large electrical circuit into several smaller circuits such that the total cross-wiring is minimized. This problem is a variant of the more general graph partitioning problem, and it is known that there does not exist a polynomial time algorithm to obtain an optimal partition. The heuristic procedure proposed by Kernighan and Lin1,2 requires O(n2 log2n) time to obtain a near-optimal two-way partition of a circuit with n modules. In the VLSI context, due to the large problem size involved, this computational requirement is unacceptably high. This paper is concerned with the hardware acceleration of the Kernighan-Lin procedure on an SIMD architecture. The proposed parallel partitioning algorithm requires O(n) processors, and has a time complexity of O(n log2n). In the proposed scheme, the reduced array architecture is employed with due considerations towards cost effectiveness and VLSI realizability of the architecture.The authors are not aware of any earlier attempts to parallelize a circuit partitioning algorithm in general or the Kernighan-Lin algorithm in particular. The use of the reduced array architecture is novel and opens up the possibilities of using this computing structure for several other applications in electronic design automation.

Dynamic State Estimation of Power Systems with Quantization Eects: A Recursive Filter Approach

In this paper, a recursive filter algorithm is developed to deal with the state estimation problem for power systems with quantized nonlinear measurements. The measurements from both the remote terminal units and the phasor measurement unit are subject to quantizations described by a logarithmic quantizer. Attention is focused on the design of a recursive filter such that, in the simultaneous presence of nonlinear measurements and quantization effects, an upper bound for the estimation error covariance is guaranteed and subsequently minimized. Instead of using the traditional approximation methods in nonlinear estimation that simply ignore the linearization errors, we treat both the linearization and quantization errors as norm-bounded uncertainties in the algorithm development so as to improve the performance of the estimator. For the power system with such kind of introduced uncertainties, a filter is designed in the framework of robust recursive estimation, and the developed filter algorithm is tested on the IEEE benchmark power system to demonstrate its effectiveness.

Use Multilevel Graph Partitioning Scheme to solve traveling salesman problem

The traveling salesman problem is although looking very simple problem but it is an important combinatorial problem. In this thesis I have tried to find the shortest distance tour in which each city is visited exactly one time and return to the starting city. I have tried to solve traveling salesman problem using multilevel graph partitioning approach.Although traveling salesman problem itself very difficult as this problem is belong to the NP-Complete problems but I have tried my best to solve this problem using multilevel graph partitioning it also belong to the NP-Complete problems. I have solved this thesis by using the k-mean partitioning algorithm which divides the problem into multiple partitions and solving each partition separately and its solution is used to improve the overall tour by applying Lin Kernighan algorithm on it. Through all this I got optimal solution which proofs that solving traveling salesman problem through graph partition scheme is good for this NP-Problem and through this we can solved this intractable problem within few minutes.Keywords: Graph Partitioning Scheme, Traveling Salesman Problem.

Automatic decomposition of unstructured meshes employing genetic algorithms for parallel FEM computations

Parallel execution of computational mechanics codes requires efficient mesh-partitioning techniques. These mesh-partitioning techniques divide the mesh into specified number of submeshes of approximately the same size and at the same time, minimise the interface nodes of the submeshes. This paper describes a new mesh partitioning technique, employing Genetic Algorithms. The proposed algorithm operates on the deduced graph (dual or nodal graph) of the given finite element mesh rather than directly on the mesh itself. The algorithm works by first constructing a coarse graph approximation using an automatic graph coarsening method. The coarse graph is partitioned and the results are interpolated onto the original graph to initialise an optimisation of the graph partition problem. In practice, hierarchy of (usually more than two) graphs are used to obtain the final graph partition. The proposed partitioning algorithm is applied to graphs derived from unstructured finite element meshes describing practical engineering problems and also several example graphs related to finite element meshes given in the literature. The test results indicate that the proposed GA based graph partitioning algorithm generates high quality partitions and are superior to spectral and multilevel graph partitioning algorithms.

一种测量深海应答器坐标的方法

提出一种适用于深海应答器坐标测量的方法:垂线相交法。这种方法利用立体几何原理,获得应答器坐标。即测量母船在距应答器适中的位置沿两条相互垂直的航迹航行,分别找到两条航迹上与应答器斜距最小的点,过这两个点在水平面上做两条垂线,交点的经纬度坐标就是应答器的经纬度坐标。分析了影响测量误差的重要因素,并提出测量原则以满足精度要求,使测量系统具有很好的鲁棒性。为提高测距精度,采用射线声学理论中的RRA算法对声线进行修正。仿真实验证明了垂线相交法的有效性。该测量方法对深度没有要求,简化了繁琐的现场操作和水声测量系统,具有很高的工程实用价值。