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.

Energy Efficiency through Thermal Energy Storage : Possibilities for the Swedish Building Stock

The need for heating and cooling in buildings constitutes a considerable part of the total energy use in a country and reducing this need is of outmost importance in order to reach national and international goals for reducing energy use and emissions. One important way of reaching these goals is to increase the proportion of renewable energy used for heating and cooling of buildings. Perhaps the largest obstacle with this is the often occurring mismatch between the availability of renewable energy and the need for heating or cooling, hindering this energy to be used directly. This is one of the problems that can be solved by using thermal energy storage (TES) in order to save the heat or cold from when it is available to when it is needed. This thesis is focusing on the combination of TES techniques and buildings to achieve increased energy efficiency for heating and cooling. Various techniques used for TES as well as the combination of TES in buildings have been investigated and summarized through an extensive literature review. A survey of the Swedish building stock was also performed in order to define building types common in Sweden. Within the scope of this thesis, the survey resulted in the selection of three building types, two single family houses and one office building, out of which the two residential buildings were used in a simulation case study of passive TES with increased thermal mass (both sensible and latent). The second case study presented in the thesis is an evaluation of an existing seasonal borehole storage of solar heat for a residential community. In this case, real measurement data was used in the evaluation and in comparisons with earlier evaluations. The literature reviews showed that using TES opens up potential for reduced energy demand and reduced peak heating and cooling loads as well as possibilities for an increased share of renewable energy to cover the energy demand. By using passive storage through increased thermal mass of a building it is also possible to reduce variations in the indoor temperature and especially reduce excess temperatures during warm periods, which could result in avoiding active cooling in a building that would otherwise need it. The analysis of the combination of TES and building types confirmed that TES has a significant potential for increased energy efficiency in buildings but also highlighted the fact that there is still much research required before some of the technologies can become commercially available. In the simulation case study it was concluded that only a small reduction in heating demand is possible with increased thermal mass, but that the time with indoor temperatures above 24 °C can be reduced by up to 20%. The case study of the borehole storage system showed that although the storage system worked as planned, heat losses in the rest of the system as well as some problems with the system operation resulted in a lower solar fraction than projected. The work presented within this thesis has shown that TES is already used successfully for many building applications (e.g. domestic hot water stores and water tanks for storing solar heat) but that there still is much potential in further use of TES. There are, however, barriers such as a need for more research for some storage technologies as well as storage materials, especially phase change material storage and thermochemical storage.

Energy Efficiency through Thermal Energy Storage - Evaluation of the Possibilities for the Swedish Building Stock, Phase 1

As a first step in assessing the potential of thermal energy storage in Swedish buildings, the current situation of the Swedish building stock and different storage methods are discussed in this paper. Overall, many buildings are from the 1960’s or earlier having a relatively high energy demand, creating opportunities for large energy savings. The major means of heating are electricity for detached houses and district heating for multi dwelling houses and premises. Cooling needs are relatively low but steadily increasing, emphasizing the need to consider energy storage for both heat and cold. The thermal mass of a building is important for passive storage of thermal energy but this has not been considered much when constructing buildings in Sweden. Instead, common ways of storing thermal energy in Swedish buildings today is in water storage tanks or in the ground using boreholes, while latent thermal energy storage is still very uncommon.

Energy savings potential in existing houses : Energy simulation results for Dalarna's single-family housing stock

Vägar till en halverad energianvändning i Dalarnas byggnadsbestånd

Minimization of stock weight during close-die forging of a spindle

In this paper, Finite Element method and full-scale experiments have been used to study a hot forging method for fabri-cation of a spindle using reduced initial stock size. The forging sequence is carried out in two stages. In the first stage, the hot rolled cylindrical billet is pre-formed and pierced in a closed die using a spherical nosed punch to within 20 mm of its base. This process of piercing or impact extrusion leads to high strains within the work piece but requires high press loads. In the second stage, the resulting cylinder is placed in a die with a flange chamber and upset forged to form a flange. The stock mass is optimized for complete die filling. Process parameters such as effective strain distribution, material flow and forging load in different stages of the process are analyzed. It is concluded from the simulations that minor modifications of piercing punch geometry to reduce contact between the punch and emerging vertical walls of the cylinder appreciably reduces the piercing load. In the flange chamber, a die surfaces angle of 52° instead of 45° is pro-posed to ensure effective material flow and exert sufficient tool pressure to achieve complete cavity filling. In order to achieve better compression, it is also proposed to shorten both the length of the inserted punch and the die “tongues” by a few mm.

The tax treatment of employee stock options : generous to a fault

In the 2000 budgets, both the federal and Ontario governments introduced changes to the tax treatment of employee stock options for the explicit purpose of making their tax treatment in Canada similar to or more favourable than that in the United States. The federal budget added a deferral, similar to that currently applicable to options granted by Canadian-controlled private corporations, for up to $100,000 per year of public company stock options. The Ontario budget introduced an exemption from tax for employees involved in research and development on the first $100,000 per year of employee benefits arising on the exercise of qualified stock options or on eligible capital gains arising from the sale of shares acquired by the exercise of eligible stock options. These proposals reflect the apparent acceptance by the two governments that there is a “brain drain” from Canada to the United States of knowledge workers in the “new” economy and that reductions in Canadian taxes should stem this drain. In the author’s view, the tax treatment of employee stock options, even without these changes, is overly generous. Both the federal and provincial proposals ignore the fact that most employee stock options are taxed more favourably in Canada than in the United States in any event. In particular, most employee stock option benefits in Canada are taxed at capital gains tax rates, whereas in the United States most are taxed at full rates. While the US Internal Revenue Code does provide capital gains tax treatment for certain employee stock option benefits, a number of preconditions must be met. Most important, the shares acquired pursuant to the options must be held for a minimum of one year after the option is exercised. In addition, there are monetary limits on the amount of options that qualify for capital gains treatment. In Canada, there are generally no holding period requirements or monetary limits that apply in order for the option holder to benefit from capital gains tax rates. Empirical evidence indicates that the vast majority of employees in the United States exercise their options and immediately sell the shares acquired. These “cashless exercises” do not benefit from capital gains treatment in the United States, whereas similar cashless exercises in Canada generally do. This empirical evidence suggests not only that the 2000 budget proposals are unwarranted, but also that the existing treatment of employee stock options in Canada is already more generous than that in the United States. This article begins with a theoretical “benchmark” for the taxation of employee stock options. The author suggests that employee stock options should be treated in the same manner as other income from employment. In theory, the value of the benefit should be included in income when the option is granted or vests. However, owing to the practical difficulty of valuing employee stock options, the theoretical benchmark proposed is that the value of the benefit (the difference between the fair market value of the shares acquired and the strike price under the option) be taxed when the shares are acquired, and the employer be entitled to a corresponding deduction. The employee stock option rules in Canada and the United States are then compared and contrasted with each other and the benchmark treatment. The article then examines the arguments that have been made for favourable treatment of employee stock options. Included in this critique is a review of the recent empirical work on the Canadian brain drain. Empirical studies suggest that the brain drain—if it exists at all—is small and that, despite what many newspapers and right-wing think-tanks would have us believe, lower taxes in the United States are not the cause. One study, concluding that taxes do have an effect on migration, suggests that even if Canada adopted a tax system identical to that in the United States, the brain drain would be reduced by a mere 10 percent. Indeed, even if Canada eliminated income tax altogether, it would not stop the brain drain. If governments here want to spend money in order to stem the brain drain, they should focus on other areas. For example, Canada produces fewer university graduates in the fields of mathematics, sciences, and engineering than any other G7 country except Italy. The short supply of university graduates in these fields, the apparent loss of top-calibre academics to US
universities, and the consequent lower levels of university research in these areas (an important spawning ground for new ideas in the “new” knowledge-based economy) suggest that Canada may be better served by devoting more resources to its university institutions, particularly in post-graduate programs, rather than continuing the current trend of budget cuts that universities have endured and may further endure if taxes are reduced.
As far as employee stock options are concerned, if Canada does want to look to the United States for guidance on tax reform (which it seems to do with increasing frequency of late), it should adopt the US rules applicable to nonstatutory options, which are close to the proposed benchmark treatment. In the absence of preferential tax treatment, employee stock options would still be included in compensation packages provided that there were sound business reasons for their use. No persuasive evidence has been put forward that the use of stock options, in the absence of tax incentives, is suboptimal. Indeed, the US experience suggests quite the opposite.

Price exhaustion and number preference : time and price confluence in Australian stock prices

Confluence occurs when different trading filters generate signals that point to the same directional move. Using regression analysis, this paper investigates confluence trading signals associated with number preference and price exhaustion, for a sample of Australian stocks. The results show that certain price levels tend to act as psychological barriers, and that price exhaustion signals are a real phenomenon in the Australian stock market. It is shown also that confluence exists in the Australian stock market. Importantly, confluence is associated with price retracements that are of economic and statistical significance, offering profitable trading opportunities. The results suggest that Australian stocks do not follow a random walk.

On the extent of speculative activity in the Indian stock market during badla and post-badla period

The authors test the existence of speculative activity in the Indian stock market during badla and post-badla period. They further investigate whether speculative activity migrated to single stocks futures market after banning of badla system. In both the tests it is found that there is no evidence of strong speculative activity in the Indian market. The research raises some questions on the regulators decision of banning badla system and sheds some light on the future decisions with respect to single stock futures market.

Simultaneous volatility transmissions and spillover effects: U.S. and Hong Kong stock and futures markets

Contemporaneous transmission effects across volatilities of the Hong Kong Stock and Index futures markets and futures volume of trade are tested by employing a structural systems approach. Competing measures of volatility spillover, constructed from the overnight U.S. S&P500 index futures, are tested and found to impact on the Hong Kong asset return volatility and volume of trade patterns. The examples utilize intra-day 15-min sampled data from this medium-sized Asia Pacific equity and derivative exchange. Both the intra- and inter-day patterns in the Hong Kong market are allowed for in the estimation process.

Factors influencing money left on the table by property trust IPO issuers

While previous listed property trust (LPT) initial public offering (IPO) studies have identified low under pricing returns, this study specifically examines the amount of money left on the table by the pre-IPO owners in this category of IPO. This study investigates 58 property trust IPOs in Australia from 1994 to 2004 and finds that the amount of money left by LPT IPOs is considerably less than industrial company IPOs, implying considerably less uncertainty about the valuation of such IPOs compared to industrials. We also find that more recent (post 2000) LPT IPOs in Australia appear to be significantly different to previous LPT IPOs in both money left and under pricing terms.

Diminishing and negative welfare returns of economic growth : an index of sustainable economic welfare (ISEW) for Thailand

Thailand has achieved remarkable levels of economic growth over the last three decades. This sustained economic growth has played a major role in reducing absolute poverty levels from nearly one third of the population in 1975 to presently less than 10%, thus increasing the welfare of many Thais. This performance ranks Thailand as one of the world's most successful economies during this period. However, an increasing number of studies have begun to find that at a certain point achieving economic growth stops improving welfare and actually begins to diminish it due to the hidden and traditionally unreported costs of associated with this growth. With one exception, these new studies have focussed on high-income countries. This study will estimate an index of sustainable economic welfare (ISEW) for a developing country, Thailand, over a 25-year period, 1975–1999. This paper concludes that even low–middle income countries are beginning to approach the point in which economic growth produces both diminishing and, at times, negative welfare returns as the costs of achieving economic growth begin to outweigh the benefits. These results are important for policy makers and highlight the importance of implementing alternative welfare enhancing interventions that must be considered in place of simply achieving economic growth. The emphasis of this paper is not on the methodology of estimating the ISEW for Thailand, but rather on the policy implications for developing countries of diminishing and negative welfare returns brought about through the achievement of economic growth.