Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Minimizing the object dimensions in circle and sphere packing problems

Given a fixed set of identical or different-sized circular items, the problem we deal with consists on finding the smallest object within which the items can be packed. Circular, triangular, squared, rectangular and also strip objects are considered. Moreover, 2D and 3D problems are treated. Twice-differentiable models for all these problems are presented. A strategy to reduce the complexity of evaluating the models is employed and, as a consequence, instances with a large number of items can be considered. Numerical experiments show the flexibility and reliability of the new unified approach. (C) 2007 Elsevier Ltd. All rights reserved.

Newton`s iterates can converge to non-stationary points

In this note we discuss the convergence of Newton`s method for minimization. We present examples in which the Newton iterates satisfy the Wolfe conditions and the Hessian is positive definite at each step and yet the iterates converge to a non-stationary point. These examples answer a question posed by Fletcher in his 1987 book Practical methods of optimization.

Structured minimal-memory inexact quasi-Newton method and secant preconditioners for augmented Lagrangian optimization

Augmented Lagrangian methods for large-scale optimization usually require efficient algorithms for minimization with box constraints. On the other hand, active-set box-constraint methods employ unconstrained optimization algorithms for minimization inside the faces of the box. Several approaches may be employed for computing internal search directions in the large-scale case. In this paper a minimal-memory quasi-Newton approach with secant preconditioners is proposed, taking into account the structure of Augmented Lagrangians that come from the popular Powell-Hestenes-Rockafellar scheme. A combined algorithm, that uses the quasi-Newton formula or a truncated-Newton procedure, depending on the presence of active constraints in the penalty-Lagrangian function, is also suggested. Numerical experiments using the Cute collection are presented.

A Robust, Fully Adaptive Hybrid Level-Set/Front-Tracking Method for Two-Phase Flows with an Accurate Surface Tension Computation

We present a variable time step, fully adaptive in space, hybrid method for the accurate simulation of incompressible two-phase flows in the presence of surface tension in two dimensions. The method is based on the hybrid level set/front-tracking approach proposed in [H. D. Ceniceros and A. M. Roma, J. Comput. Phys., 205, 391400, 2005]. Geometric, interfacial quantities are computed from front-tracking via the immersed-boundary setting while the signed distance (level set) function, which is evaluated fast and to machine precision, is used as a fluid indicator. The surface tension force is obtained by employing the mixed Eulerian/Lagrangian representation introduced in [S. Shin, S. I. Abdel-Khalik, V. Daru and D. Juric, J. Comput. Phys., 203, 493-516, 2005] whose success for greatly reducing parasitic currents has been demonstrated. The use of our accurate fluid indicator together with effective Lagrangian marker control enhance this parasitic current reduction by several orders of magnitude. To resolve accurately and efficiently sharp gradients and salient flow features we employ dynamic, adaptive mesh refinements. This spatial adaption is used in concert with a dynamic control of the distribution of the Lagrangian nodes along the fluid interface and a variable time step, linearly implicit time integration scheme. We present numerical examples designed to test the capabilities and performance of the proposed approach as well as three applications: the long-time evolution of a fluid interface undergoing Rayleigh-Taylor instability, an example of bubble ascending dynamics, and a drop impacting on a free interface whose dynamics we compare with both existing numerical and experimental data.

On the manifold structure of the set of unparameterized embeddings with low regularity

Given manifolds M and N, with M compact, we study the geometrical structure of the space of embeddings of M into N, having less regularity than C(infinity) quotiented by the group of diffeomorphisms of M.

A quantum chemical study on a set of non-imidazole H(3) antihistamine molecules

Molecular orbital calculations were carried out on a set of 28 non-imidazole H(3) antihistamine compounds using the Hartree-Fock method in order to investigate the possible relationships between electronic structural properties and binding affinity for H3 receptors (pK(i)). It was observed that the frontier effective-for-reaction molecular orbital (FERMO) energies were better correlated with pK(i) values than highest occupied molecular orbital (HOMO) and lowest unoccupied molecular orbital (LUMO) energy values. Exploratory data analysis through hierarchical cluster (HCA) and principal component analysis (PCA) showed a separation of the compounds in two sets, one grouping the molecules with high pK(i) values, the other gathering low pK(i) value compounds. This separation was obtained with the use of the following descriptors: FERMO energies (epsilon(FERMO)), charges derived from the electrostatic potential on the nitrogen atom (N(1)), electronic density indexes for FERMO on the N(1) atom (Sigma((FERMO))c(i)(2)). and electrophilicity (omega`). These electronic descriptors were used to construct a quantitative structure-activity relationship (QSAR) model through the partial least-squares (PLS) method with three principal components. This model generated Q(2) = 0.88 and R(2) = 0.927 values obtained from a training set and external validation of 23 and 5 molecules, respectively. After the analysis of the PLS regression equation and the values for the selected electronic descriptors, it is suggested that high values of FERMO energies and of Sigma((FERMO))c(i)(2), together with low values of electrophilicity and pronounced negative charges on N(1) appear as desirable properties for the conception of new molecules which might have high binding affinity. 2010 Elsevier Inc. All rights reserved.

Classification of Parkinson’s Disease using MultiPass Lvq,Logistic Model Tree,K-Star for Audio Data set : Classification of Parkinson Disease using Audio Dataset

Parkinson's disease (PD) is a degenerative illness whose cardinal symptoms include rigidity, tremor, and slowness of movement. In addition to its widely recognized effects PD can have a profound effect on speech and voice.The speech symptoms most commonly demonstrated by patients with PD are reduced vocal loudness, monopitch, disruptions of voice quality, and abnormally fast rate of speech. This cluster of speech symptoms is often termed Hypokinetic Dysarthria.The disease can be difficult to diagnose accurately, especially in its early stages, due to this reason, automatic techniques based on Artificial Intelligence should increase the diagnosing accuracy and to help the doctors make better decisions. The aim of the thesis work is to predict the PD based on the audio files collected from various patients.Audio files are preprocessed in order to attain the features.The preprocessed data contains 23 attributes and 195 instances. On an average there are six voice recordings per person, By using data compression technique such as Discrete Cosine Transform (DCT) number of instances can be minimized, after data compression, attribute selection is done using several WEKA build in methods such as ChiSquared, GainRatio, Infogain after identifying the important attributes, we evaluate attributes one by one by using stepwise regression.Based on the selected attributes we process in WEKA by using cost sensitive classifier with various algorithms like MultiPass LVQ, Logistic Model Tree(LMT), K-Star.The classified results shows on an average 80%.By using this features 95% approximate classification of PD is acheived.This shows that using the audio dataset, PD could be predicted with a higher level of accuracy.

The impact of big-boxes on local retail : What happens when IKEA comes to town?

The development of large discount retailers, or big-boxes as they are sometimes referred to, are often subject to heated debate and their entry on a market is greeted with either great enthusiasm or dread. For instance, the world’s largest retailer Wal-Mart (Forbes 2014) has a number of anti- and pro-groups dedicated to its being and the event of a Wal-Mart entry tends to be met with protests and campaigns (Decamme 2013) but also welcomed by, for instance, consumers (Davis & DeBonis 2013). Also in Sweden, the entry of a big box is a hot topic and before IKEA’s opening i Borlänge 2013, the first in Sweden in more than five years, great expectations were mixed with worry (Västerbottens-Kuriren 2011).The presence of large scale discount retailers is not, however, a novel phenomenon but a part of a long-term change in retailing that has taken place globally over the past couple of decades (Taylor & Smalling, 2005). As noted by Dawson (2006), the trend in Europe has over the past few decades gone towards an increasing concentration of large firms along with a decrease of smaller firms.This trend is also detectable in the Swedish retail industry. Over the past decade, the retailing industry in Sweden has increased by around 190 Billion SEK, and its share of GDP has risen from 2,7% to 2,9%, while the number of employees have increased from 200 000 to 250 000 (HUI 2013). This growth, however, has not been distributed evenly but rather it has been oriented mainly towards out-of-town retail clusters. Parallel to this development, the number of large retailers has risen at the expense of market shares of smaller independent firms (Rämme et al 2010). Thereby, the presence of large scale retailers is simply part of a changing retail landscape.The effects of this development, where large scale retailing agents relocate shopping to out-of-town shopping areas, have been heavily debated. On the one hand, the big-boxes are accused of displacing independent small retail businesses in the city-centers and the residential areas, resulting in, to some extent, reduced employment opportunities and less availability for the consumers - especially the elderly (Ljungberg et al 2006). In addition, as access to shopping now tends to require some sort of a motorized vehicle, environmental aspects to the discussion have emerged. Ultimately these types of concerns have resulted in calls for regulations against this development (Olsson 2010). On the other hand, the proponents of the new shopping landscape argue that this evolution implies productivity gains, the benefits of lower prices and an increased variety of products (Maican & Orth 2012). Moreover it is argued that it leads to, for instance, better services (such as longer opening hours) and a creative destruction transformation pressure on retailers, which brings about a renewal of city-centerIIretail and services, increasing their attractivity (Bergström 2010). The belief in benefits of a big box entry can be exemplified by the attractivity of IKEA, and the fact that municipalities are prepared to commit to expenses amounting up to hundreds of millions in order to attract the entry of this big-box. Borlänge municipality, for instance, agreed to expenses of about 350 million SEK in order to secure the entry of IKEA, which opened in 2013 (Blomgren 2009).Against this backdrop, the overall effects of large discount retailers become important: Are the economic benefits enough to warrant subsidies or are there, on the contrary, some very compelling grounds for regulations against these types of establishments? In other words; how is overall retail in a region where a store like IKEA enters affected? And how are local retail firms affected?In order to answer these questions, the purpose of this thesis is to study how entry of a big-box retailer affects the entry region. The object of this study is IKEA - one of the world’s largest retailers, with 345 stores, active in over 40 countries and with profits of about 3.3 billion (IKEA 2013; IKEA 2014). By studying the effects of IKEA-entry, both on an aggregated level and on firm level, this thesis intends to find indications of how large discount retail establishments in general can be expected to affect the economic development both in a region overall, but also on the local firm level, something which is of interest to both policymakers as well as the retailing industry in general.The first paper examines the effects of IKEA on retail revenues and employment in the municipalities that IKEA chose to enter between 2000 and 2011; Gothenburg, Haparanda, Kalmar and Karlstad. By means of a matching method we first identify non-entry municipalities that have a similar probability of IKEA entry as the true entry municipalities. Then, using these non-entry municipalities as a control group, the causal effects of IKEA entry can be estimated using a treatment-control approach. We also extend the analysis to examine the spatial impact of IKEA by estimating the effects on retail in neighboring municipalities. It is found that a new IKEA store increases revenues in durable goods trade with 20% in the entry municipality and the number of employees with 17%. Only small, and in most cases statistically insignificant, negative effects were found in neighboring municipalities.It appears that there is a positive net effect on durables retail sales and employment in the entry municipality. However, the analysis is based on data on an aggregated municipality level and thereby it remains unclear if and how the effects vary within the entry municipalities. In addition, the data used in the first study includes the sales and employment of IKEA itself, which could account for the majority of the increases in employment and retail. Thereby the potential spillover effects on incumbent retailers in the entry municipalities cannot be discerned in the first study.IIITo examine effects of IKEA entry on incumbent retail firms, the second paper in this thesis analyses how IKEA entry affects the revenues and employment of local retail firms in three municipalities; Haparanda, Kalmar and Karlstad, which experienced entry by IKEA between 2000 and 2010. In this second study, we exclude Gothenburg due to the fact that big-box entry appears to have weaker effects in metropolitan areas (as indicated by Artz & Stone 2006). By excluding Gothenburg we aim to reduce the geographical heterogeneity in our study. We obtain control municipalities that are as similar as possible to the three entry municipalities using the same method as in the previous study, but including a slightly different set of variables in the selection equation. Using similar retail firms in the control municipalities as our comparison group, we estimate the impact of IKEA entry on revenues and employment for retail firms located at varying distances from the IKEA entry site.The results generated in this study imply that entry by IKEA increases revenues in incumbent retail firms by, on average, 11% in the entry municipalities. In addition, we do not find any significant impact on retail revenues in the city centers of the entry municipalities. However, we do find that retail firms within 1 km of the IKEA experience increases in revenues of about 26%, which indicates large spillover effects in the area nearby the entry site. As expected, this impact decreases as we expand the buffer zone: firms located between 0-2 km experiences a 14% increase and firms in 2-5 km experiences an increase of 10%. We do not find any significant impacts on retail employment.

Simple Question, Complex Answer : Pathways Towards a 50% Decrease in Building Energy Use

Addressing building energy use is a pressing issue for building sector decision makers across Europe. In Sweden, some regions have adopted a target of reducing energy use in buildings by 50% until 2050. However, building codes currently do not support as ambitious objectives as these, and novel approaches to addressing energy use in buildings from a regional perspective are called for. The purpose of this licentiate thesis was to provide a deeper understanding of most relevant issues with regard to energy use in buildings from a broad perspective and to suggest pathways towards reaching the long-term savings objective. Current trends in building sector structure and energy use point to detached houses constructed before 1981 playing a key role in the energy transition, especially in the rural areas of Sweden. In the Swedish county of Dalarna, which was used as a study area in this thesis, these houses account for almost 70% of the residential heating demand. Building energy simulations of eight sample houses from county show that there is considerable techno-economic potential for energy savings in these houses, but not quite enough to reach the 50% savings objective. Two case studies from rural Sweden show that savings well beyond 50% are achievable, both when access to capital and use of high technology are granted and when they are not. However, on a broader scale both direct and indirect rebound effects will have to be expected, which calls for more refined approaches to energy savings. Furthermore, research has shown that the techno-economic potential is in fact never realised, not even in the most well-designed intervention programmes, due to the inherent complexity of human behaviour with respect to energy use. This is not taken account of in neither current nor previous Swedish energy use legislation. Therefore an approach that considers the technical prerequisites, economic aspects and the perspective of the many home owners, based on Community-Based Social Marketing methodology, is suggested as a way forward towards reaching the energy savings target.