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

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.

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.

Prediction of hemodynamic severity of coarctation by magnetic resonance imaging.

A published formula containing minimal aortic cross-sectional area and the flow deceleration pattern in the descending aorta obtained by cardiovascular magnetic resonance predicts significant coarctation of the aorta (CoA). However, the existing formula is complicated to use in clinical practice and has not been externally validated. Consequently, its clinical utility has been limited. The aim of this study was to derive a simple and clinically practical algorithm to predict severe CoA from data obtained by cardiovascular magnetic resonance. Seventy-nine consecutive patients who underwent cardiovascular magnetic resonance and cardiac catheterization for the evaluation of native or recurrent CoA at Children's Hospital Boston (n = 30) and the University of California, San Francisco (n = 49), were retrospectively reviewed. The published formula derived from data obtained at Children's Hospital Boston was first validated from data obtained at the University of California, San Francisco. Next, pooled data from the 2 institutions were analyzed, and a refined model was created using logistic regression methods. Finally, recursive partitioning was used to develop a clinically practical prediction tree to predict transcatheter systolic pressure gradient ≥ 20 mm Hg. Severe CoA was present in 48 patients (61%). Indexed minimal aortic cross-sectional area and heart rate-corrected flow deceleration time in the descending aorta were independent predictors of CoA gradient ≥ 20 mm Hg (p <0.01 for both). A prediction tree combining these variables reached a sensitivity and specificity of 90% and 76%, respectively. In conclusion, the presented prediction tree on the basis of cutoff values is easy to use and may help guide the management of patients investigated for CoA.

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.

Energy-aware Task Allocation onto Unrelated Heterogeneous Multicore Platform for Mixed Criticality Systems

Presented at Work in Progress Session, IEEE Real-Time Systems Symposium (RTSS 2015). 1 to 4, Dec, 2015. San Antonio, U.S.A..

The management of brain metastases

Brain metastases occur in 20-50% of NSCLC and 50-80% of SCLC. In this review, we will look at evidence-based medicine data and give some perspectives on the management of BM. We will address the problems of multiple BM, single BM and prophylactic cranial irradiation. Recursive Partitioning Analysis (RPA) is a powerful prognostic tool to facilitate treatment decisions. Dealing with multiple BM, the use of corticosteroids was established more than 40 years ago by a unique randomized trial (RCT). Palliative effect is high (_80%) as well as side-effects. Whole brain radiotherapy (WBRT) was evaluated in many RCTs with a high (60-90%) response rate; several RT regimes are equivalent, but very high dose per fraction should be avoided. In multiple BM from SCLC, the effect of WBRT is comparable to that in NSCLC but chemotherapy (CXT) although advocated is probably less effective than RT. Single BM from NSCLC occurs in 30% of all BM cases; several prognostic classifications including RPA are very useful. Several options are available in single BM: WBRT, surgery (SX), radiosurgery (RS) or any combination of these. All were studied in RCTs and will be reviewed: the addition of WBRT to SX or RS gives a better neurological tumour control, has little or no impact on survival, and may be more toxic. However omitting WBRT after SX alone gives a higher risk of cerebro-spinal fluid dissemination. Prophylactic cranial irradiation (PCI) has a major role in SCLC. In limited disease, meta-analyses have shown a positive impact of PCI in the decrease of brain relapse and in survival improvement, especially for patients in complete remission. Surprisingly, this has been recently confirmed also in extensive disease. Experience with PCI for NSCLC is still limited, but RCT suggest a reduction of BM with no impact on survival. Toxicity of PCI is a matter of debate, as neurological or neuro-cognitive impairment is already present prior to PCI in almost half of patients. However RT toxicity is probably related to total dose and dose per fraction. Perspectives : Future research should concentrate on : 1) combined modalities in multiple BM. 2) Exploration of treatments in oligo-metastases. 3) Further exploration of PCI in NSCLC. 4) Exploration of new, toxicity-sparing radiotherapy techniques (IMRT, Tomotherapy etc).

An information theoretic framework for image segmentation

In this paper, an information theoretic framework for image segmentation is presented. This approach is based on the information channel that goes from the image intensity histogram to the regions of the partitioned image. It allows us to define a new family of segmentation methods which maximize the mutual information of the channel. Firstly, a greedy top-down algorithm which partitions an image into homogeneous regions is introduced. Secondly, a histogram quantization algorithm which clusters color bins in a greedy bottom-up way is defined. Finally, the resulting regions in the partitioning algorithm can optionally be merged using the quantized histogram

Impact of Prophylactic Cranial Irradiation Timing on Brain Relapse Rates in Patients With Stage IIIB Non-Small-Cell Lung Carcinoma Treated With Two Different Chemoradiotherapy Regimens.

PURPOSE: To retrospectively assess the influence of prophylactic cranial irradiation (PCI) timing on brain relapse rates in patients treated with two different chemoradiotherapy (CRT) regimens for Stage IIIB non-small-cell lung cancer (NSCLC). METHODS AND MATERIALS: A cohort of 134 patients, with Stage IIIB NSCLC in recursive partitioning analysis Group 1, was treated with PCI (30 Gy at 2 Gy/fr) following one of two CRT regimens. Regimen 1 (n = 58) consisted of three cycles of induction chemotherapy (ICT) followed by concurrent CRT (C-CRT). Regimen 2 (n = 76) consisted of immediate C-CRT during thoracic radiotherapy. RESULTS: At a median follow-up of 27.6 months (range, 7.2-40.4), 65 patients were alive. Median, progression-free, and brain metastasis-free survival (BMFS) times for the whole study cohort were 23.4, 15.4, and 23.0 months, respectively. Median survival time and the 3-year survival rate for regimens 1 and 2 were 19.3 vs. 26.1 months (p = 0.001) and 14.4% vs. 34.4% (p < .001), respectively. Median time from the initiation of primary treatment to PCI was 123.2 (range, 97-161) and 63.4 (range, 55-74) days for regimens 1 and 2, respectively (p < 0.001). Overall, 11 (8.2%) patients developed brain metastasis (BM) during the follow-up period: 8 (13.8%) in regimen 1 and 3 (3.9%) in regimen 2 (p = 0.03). Only 3 (2.2%) patients developed BM at the site of first failure, and for 2 of them, it was also the sole site of recurrence. Median BMFS for regimens 1 and 2 were 17.4 (13.5-21.3) vs. 26.0 (22.9-29.1 months), respectively (p < 0.001). CONCLUSION: These results suggest that in Stage IIIB NSCLC patients treated with PCI, lower BM incidence and longer survival rates result from immediate C-CRT rather than ITC-first regimens. This indicates the benefit of earlier PCI use without delay because of induction protocols.

Salvage radiosurgery for selected patients with recurrent malignant gliomas.

Purpose. To analyse the survival after salvage radiosurgery and to identify prognostic factors. Methods. We retrospectively reviewed 87 consecutive patients, with recurrent high-grade glioma, that underwent stereotactic radiosurgery between 1997 and 2010. We evaluated the survival after initial diagnosis and after reirradiation. The prognostic factors were analysed by bivariate and multivariate Cox regression model. Results. The median age was 48 years old. The primary histology included anaplastic astrocytoma (47%) and glioblastoma (53%). A margin dose of 18 Gy was administered in the majority of cases (74%). The median survival after initial diagnosis was 21 months (39 months for anaplastic astrocytoma and 18.5 months for glioblastoma) and after reirradiation it was 10 months (17 months for anaplastic astrocytoma and 7.5 months for glioblastoma). In the bivariate analyses, the prognostic factors significantly associated with survival after reirradiation were age, tumour and treatment volume at recurrence, recursive partitioning analyses classification, Karnofsky performance score, histology, and margin to the planning target volume. Only the last four showed significant association in the multivariate analyses. Conclusion. stereotactic radiosurgery is a safe and may be an effective treatment option for selected patients diagnosed with recurrent high-grade glioma. The identified prognostic factors could help individualise the treatment.