Two-Dimensional Bin Packing Problem with Guillotine Restrictions

This thesis, after presenting recent advances obtained for the two-dimensional bin packing problem, focuses on the case where guillotine restrictions are imposed. A mathematical characterization of non-guillotine patterns is provided and the relation between the solution value of the two-dimensional problem with guillotine restrictions and the two-dimensional problem unrestricted is being studied from a worst-case perspective. Finally it presents a new heuristic algorithm, for the two-dimensional problem with guillotine restrictions, based on partial enumeration, and computationally evaluates its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases.

L'algoritmo bionomico per il Traveling Salesman Problem

In questa tesi viene presentato un nuovo metaeuristico per la risoluzione del Traveling Salesman Problem (TSP) simmetrico. Tale metodo, detto algoritmo bionomico, è una variante dell'algoritmo genetico che usa un metodo innovativo di generazione del parents set. Nella tesi vengono proposti diversi metodi di crossover specifici per il TSP ma che possono essere facilmente estesi per altri problemi di ottimizzazione combinatoria. Tali metodi sono stati sperimentati su un insieme di problemi test, i risultati computazionali mostrano l'efficienza dei metodi proposti. In particolare uno dei metodi domina gli altri sia per la miglior qualità delle soluzioni prodotte che per il minor tempo di calcolo impiegato.

Set up of a procedure for correlation analysis between current discharge and dose delivery in a pulsed power plasma device for medical application

This thesis work aims to find a procedure for isolating specific features of the current signal from a plasma focus for medical applications. The structure of the current signal inside a plasma focus is exclusive of this class of machines and a specific analysis procedure has to be developed. The hope is to find one or more features that shows a correlation with the dose erogated. The study of the correlation between the current discharge signal and the dose delivered by a plasma focus could be of some importance not only for the practical application of dose prediction but also for expanding the knowledge anbout the plasma focus physics. Vatious classes of time-frequency analysis tecniques are implemented in order to solve the problem.

Immunomodulatory therapy to achieve maximum efficacy: doses, monitoring, compliance, and self-infusion at home

The Oxford Programme for Immunomodulatory Immunoglobulin Therapy has been operating since 1992 at Oxford Radcliffe Hospitals in the UK. Initially, this program was set up for patients with multifocal motor neuropathy or chronic inflammatory demyelinating poly-neuropathy to receive reduced doses of intravenous immunoglobulin (IVIG) in clinic on a regular basis (usually every 3 weeks). The program then rapidly expanded to include self-infusion at home, which monitoring showed to be safe and effective. It has been since extended to the treatment of other autoimmune diseases in which IVIG has been shown to be efficacious.

Methodological issues in quantifying the magnitude of the tuberculosis problem in a prison population

SETTING: Correctional settings and remand prisons. OBJECTIVE: To critically discuss calculations for epidemiological indicators of the tuberculosis (TB) burden in prisons and to provide recommendations to improve study comparability. METHODS: A hypothetical data set illustrates issues in determining incidence and prevalence. The appropriate calculation of the incidence rate is presented and problems arising from cross-sectional surveys are clarifi ed. RESULTS: Cases recognized during the fi rst 3 months should be classifi ed as prevalent at entry and excluded from any incidence rate calculation. The numerator for the incidence rate includes persons detected as having developed TB during a specifi ed period of time subsequent to the initial 3 months. The denominator is persontime at risk from 3 months onward to the end point (TB or end of the observation period). Preferably, entry time, exit time and event time are known for each inmate to determine person-time at risk. Failing that, an approximation consists of the sum of monthly head counts, excluding prevalent cases and those persons no longer at risk from both the numerator and the denominator. CONCLUSIONS: The varying durations of inmate incarceration in prisons pose challenges for quantifying the magnitude of the TB problem in the inmate population. Recommendations are made to measure incidence and prevalence.

The impact of body mass index on the development of systemic inflammatory response syndrome and sepsis in patients with polytrauma

PURPOSE: Obesity is a growing problem in industrial nations. Our aim was to examine how overweight patients coped with systemic inflammatory response syndrome (SIRS) after polytrauma. METHODS: A total of 651 patients were included in this retrospective study, with an ISS≥16 and age≥16 years. The sample was subdivided into three groups: body mass index (BMI; all in kg/m(2))<25, BMI 25-30 and BMI>30, or low, intermediate and high BMI. The SIRS score was measured over 31 days after admission together with measurements of C-reactive protein (CRP), interleukin-6 (IL-6) and procalcitonin (PCT). Data are given as the mean±SEM if not otherwise indicated. Kruskal-Wallis and χ(2) tests were used for statistical analysis and the significance level was set at p<.05. RESULTS: The maximum SIRS score was reached in the low BMI-group at 3.4±0.4, vs. 2.3±0.1 and 2.5±0.2 in the intermediate BMI-group and high BMI-group, respectively (p<.0001). However, the maximum SIRS score was reached earlier in the BMI 25-30 group at 1.8±0.2 days, vs. 3.4±0.4 and 2.5±0.2 days in the BMI<25 and BMI>30 groups, respectively (p<.0001). The incidence of sepsis was significantly higher in the low BMI group at 46.1%, vs. 0.2% and 0% in the BMI 25-30 and BMI>30 groups, respectively (p<.0001). No significant differences in the CRP, IL-6 or PCT levels were found between groups. CONCLUSIONS: A higher BMI seemed to be protective for these patients with polytrauma-associated inflammatory problems.

On a Problem of Burnside

Burnside posed the question as to whether or not there exist groups having an external automorphism that behaves in a certain, specific way like an inner automorphism: we shall define such automorphisms to be nearly-inner. NI-groups are fairly rare. With the aid of the computer algebra system Magma - in particular with the aid of its small group database - we set out to test this hypothesis.

The Choice of Expedient Regulatory Controls on Housing Market Using Short-Term Equilibria Model

Khutoretsky dealt with the problem of maximising a linear utility function (MUF) over the set of short-term equilibria in a housing market by reducing it to a linear programming problem, and suggested a combinatorial algorithm for this problem. Two approaches to the market adjustment were considered: the funding of housing construction and the granting of housing allowances. In both cases, locally optimal regulatory measures can be developed using the corresponding dual prices. The optimal effects (with the regulation expenditures restricted by an amount K) can be found using specialised models based on MUF: a model M1 for choice of the optimum structure of investment in housing construction, and a model M2 for optimum distribution of housing allowances. The linear integer optimisation problems corresponding to these models are initially difficult but can be solved after slight modifications of the parameters. In particular, the necessary modification of K does not exceed the maximum construction cost of one dwelling (for M1) or the maximum size of one housing allowance (for M2). The result is particularly useful since slight modification of K is not essential in practice.

Problem of Tragedy and Tragic Consciousness in Russia at the turn of the 19th Century

This project intertwines philosophical and historico-literary themes, taking as its starting point the concept of tragic consciousness inherent in the epoch of classicism. The research work makes use of ontological categories in order to describe the underlying principles of the image of the world which was created in philosophical and scientific theories of the 17th century as well as in contemporary drama. Using these categories brought Mr. Vilk to the conclusion that the classical picture of the world implied a certain dualism; not the Manichaean division between light and darkness but the discrimination between nature and absolute being, i.e. God. Mr. Vilk begins with an examination of the philosophical essence of French classical theatre of the XVII and XVIII centuries. The history of French classical tragedy can be divided into three periods: from the mid 17th to early 19th centuries when it triumphed all over France and exerted a powerful influence over almost all European countries; followed by the period of its rejection by the Romantics, who declared classicism to be "artificial and rational"; and finally our own century which has taken a more moderate line. Nevertheless, French classical tragedy has never fully recovered its status. Instead, it is ancient tragedy and the works of Shakespeare that are regarded to be the most adequate embodiment of the tragic. Consequently they still provoke a great number of new interpretations ranging from specialised literary criticism to more philosophical rumination. An important feature of classical tragedy is a system of rules and unities which reveals a hidden ontological structure of the world. The ontological picture of the dramatic world can be described in categories worked out by medieval philosophy - being, essence and existence. The first category is to be understood as a tendency toward permanency and stability (within eternity) connected with this or that fragment of dramatic reality. The second implies a certain set of permanent elements that make up the reality. And the third - existence - should be understood as "an act of being", as a realisation of permanently renewed processes of life. All of these categories can be found in every artistic reality but the accents put on one or another and their interrelations create different ontological perspectives. Mr. Vilk plots the movement of thought, expressed in both philosophical and scientific discourses, away from Aristotle's essential forms, and towards a prioritising of existence, and shows how new forms of literature and drama structured the world according to these evolving requirements. At the same time the world created in classical tragedy fully preserves another ontological paradigm - being - as a fundamental permanence. As far as the tragic hero's motivations are concerned this paradigm is revealed in the dedication of his whole self to some cause, and his oath of fidelity, attitudes which shape his behaviour. It may be the idea of the State, or personal honour, or something borrowed from the emotional sphere, passionate love. Mr. Vilk views the conflicting ambivalence of existence and being, duty as responsibility and duty as fidelity, as underlying the main conflict of classical tragedy of the 17th century. Having plotted the movement of the being/existence duality through its manifestations in 17th century tragedy, Mr. Vilk moves to the 18th century, when tragedy took a philosophical turn. A dualistic view of the world became supplanted by the Enlightenment idea of a natural law, rooted in nature. The main point of tragedy now was to reveal that such conflicts as might take place had an anti-rational nature, that they arose as the result of a kind of superstition caused by social reasons. These themes Mr. Vilk now pursues through Russian dramatists of the 18th and early 19th centuries. He begins with Sumarakov, whose philosophical thought has a religious bias. According to Sumarakov, the dualism of the divineness and naturalness of man is on the one hand an eternal paradox, and on the other, a moral challenge for humans to try to unite the two opposites. His early tragedies are not concerned with social evils or the triumph of natural feelings and human reason, but rather the tragic disharmony in the nature of man and the world. Mr Vilk turns next to the work of Kniazhnin. He is particularly keen to rescue his reputation from the judgements of critics who accuse him of being imitative, and in order to do so, analyses in detail the tragedy "Dido", in which Kniazhnin makes an attempt to revive the image of great heroes and city-founders. Aeneas represents the idea of the "being" of Troy, his destiny is the re-establishment of the city (the future Rome). The moral aspect behind this idea is faithfulness, he devotes himself to Gods. Dido is also the creator of a city, endowed with "natural powers" and abilities, but her creation is lacking internal stability grounded in "being". The unity of the two motives is only achieved through Dido's sacrifice of herself and her city to Aeneus. Mr Vilk's next subject is Kheraskov, whose peculiarity lies in the influence of free-mason mysticism on his work. This section deals with one of the most important philosophical assumptions contained in contemporary free-mason literature of the time - the idea of the trinitarian hierarchy inherent in man and the world: body - soul - spirit, and nature - law - grace. Finally, Mr. Vilk assess the work of Ozerov, the last major Russian tragedian. The tragedies which earned him fame, "Oedipus in Athens", "Fingal" and "Dmitri Donskoi", present a compromise between the Enlightenment's emphasis on harmony and ontological tragic conflict. But it is in "Polixene" that a real meeting of the Russian tradition with the age-old history of the genre takes place. The male and female characters of "Polixene" distinctly express the elements of "being" and "existence". Each of the participants of the conflict possesses some dominant characteristic personifying a certain indispensable part of the moral world, a certain "virtue". But their independent efforts are unable to overcome the ontological gap separating them. The end of the tragedy - Polixene's sacrificial self-immolation - paradoxically combines the glorification of each party involved in the conflict, and their condemnation. The final part of Mr. Vilk's research deals with the influence of "Polixene" upon subsequent dramatic art. In this respect Katenin's "Andromacha", inspired by "Polixene", is important to mention. In "Andromacha" a decisive divergence from the principles of the philosophical tragedy of Russian classicism and the ontology of classicism occurs: a new character appears as an independent personality, directed by his private interest. It was Katenin who was to become the intermediary between Pushkin and classical tragedy.

Extensions to Gene Set Enrichment

Motivation: Gene Set Enrichment Analysis (GSEA) has been developed recently to capture moderate but coordinated changes in the expression of sets of functionally related genes. We propose number of extensions to GSEA, which uses different statistics to describe the association between genes and phenotype of interest. We make use of dimension reduction procedures, such as principle component analysis to identify gene sets containing coordinated genes. We also address the problem of overlapping among gene sets in this paper. Results: We applied our methods to the data come from a clinical trial in acute lymphoblastic leukemia (ALL) [1]. We identified interesting gene sets using different statistics. We find that gender may have effects on the gene expression in addition to the phenotype effects. Investigating overlap among interesting gene sets indicate that overlapping could alter the interpretation of the significant results.

Metaheuristics for the Order Batching Problem in Manual Order Picking Systems

In manual order picking systems, order pickers walk or drive through a distribution warehouse in order to collect items which are requested by (internal or external) customers. In order to perform these operations efficiently, it is usually required that customer orders are combined into (more substantial) picking orders of limited size. The Order Batching Problem considered in this paper deals with the question of how a given set of customer orders should be combined such that the total length of all tours is minimized which are necessary to collect all items. The authors introduce two metaheuristic approaches for the solution of this problem: the first one is based on Iterated Local Search; the second on Ant Colony Optimization. In a series of extensive numerical experiments, the newly developed approaches are benchmarked against classic solution methods. It is demonstrated that the proposed methods are not only superior to existing methods but provide solutions which may allow distribution warehouses to be operated significantly more efficiently.

The Car Resequencing Problem with Pull-Off Tables

The car sequencing problem determines sequences of different car models launched down a mixed-model assembly line. To avoid work overloads of workforce, car sequencing restricts the maximum occurrence of labor-intensive options, e.g., a sunroof, by applying sequencing rules. We consider this problem in a resequencing context, where a given number of buffers (denoted as pull-off tables) is available for rearranging a stirred sequence. The problem is formalized and suited solution procedures are developed. A lower bound and a dominance rule are introduced which both reduce the running time of our graph approach. Finally, a real-world resequencing setting is investigated.

Obesity and overweight as a risk factor for pneumonia in polytrauma patients: a retrospective cohort study

BACKGROUND Obesity is a growing problem in western societies. The aim of this retrospective cohort study was to determine the association between the overweight and obese polytrauma patients and pneumonia after injury. METHODS A total of 628 patients with an Injury Severity Score (ISS) of 16 or greater and 16 years or older were included in this retrospective study. The sample was subdivided into three groups as follows: body mass index (BMI) of less than 25 kg/m2; BMI of 25 kg/m2 to 30 kg/m2; and BMI more than 30 kg/m2. The Murray score was assessed at admission and at its maximum during hospitalization to determine pulmonary problems. Pneumonia was defined as bacteriologically positive sputum with appropriate radiologic and laboratory changes (C-reactive protein and interleukin 6). Data are given as mean ± SEM. One-way analysis of variance and the Kruskal-Wallis test were used for the analyses, and the significance level was set at p < 0.05; Bonferroni-Dunn test was performed as post hoc analysis. RESULTS The Abbreviated Injury Scale (AIS) score for the thorax was 3.2 ± 0.1 in the group with a BMI of less than 25 kg/m2, 3.3 ± 0.1 in the group with a BMI of 25 kg/m2 to 30 kg/m2, and 2.8 ± 0.2 in the group with BMI of more than 30 kg/m2 (p = 0.044). The Murray score at admission was elevated with increasing BMI (0.8 ± 0.8 for BMI < 25 kg/m2, 0.9 ± 0.9 for BMI 25–30 kg/m2, and 1.0 ± 0.8 for BMI > 30 kg/m2; p = 0.137); the maximum Murray score during hospitalization revealed significant differences (1.2 ± 0.9 for BMI < 25 kg/m2, 1.6 ± 1.0 for BMI 25–30 kg/m2, and 1.5 ± 0.9 for BMI > 30 kg/m2; p < 0.001). The incidence of pneumonia also increased with increasing BMI (1.6% for BMI < 25 kg/m2, 2.0% for BMI 25–30 kg/m2, and 3.1% for BMI > 30 kg/m2; p = 0.044). CONCLUSION Obesity leads to an increased incidence of pneumonia in a polytrauma situation. LEVEL OF EVIDENCE Prognostic/epidemiologic study, level IV.

The influence of body mass index on injury pattern in polytrauma: thorax as the main source of complications

Background: Obesity is a growing problem in industrial nations. The aim of this study was to determine the relationship between the body mass index (BMI) and the pattern of injury after polytrauma. Methods: This retrospective study included 651 patients with an injury severity score (ISS) ≥16 and aged ≥16 years who were subdivided into three groups: BMI < 25 kg/m2, BMI 25–30 kg/m2, and BMI > 30 kg/m2. The Abbreviated Injury Scale (AIS) was used to quantify the injuries in the different anatomical regions. The Murray score was assessed at admission and at its maximum during hospitalization to evaluate pulmonary problems. Data are presented as means ± standard errors of the means. One way analysis of variance, χ2 test and Kruskal-Wallis test were used for the analyses and the significance level was set at p < 0.05. Results: The AIS of the thorax was 3.2 ± 0.1 in the BMI < 25 kg/m2 group, 3.3 ± 0.1 in the BMI 25–30 kg/m2 group, and 2.8 ± 0.2 in the BMI > 30 kg/m2 group; p < 0.05. The Murray score at admission increased significantly with increasing BMI (0.8 ± 0.8 for BMI < 25 kg/m2, 0.9 ± 0.9 for BMI 25–30 kg/m2, and 1.0 ± 0.8 for BMI > 30 kg/m2; p < 0.05) as was the maximum Murray score during hospitalization (1.2 ± 0.9 for BMI < 25 kg/m2, 1.6 ± 1.0 for BMI 25–30 kg/m2, and 1.5 ± 0.9 for BMI > 30 kg/m2; p < 0.001). The number of ventilator days was also elevated significantly with increasing BMI (5.9 ± 0.4 for BMI < 25 kg/m2, 7.7 ± 0.8 for BMI 25–30 kg/m2, and 7.9 ± 1.6 for BMI > 30 kg/m2; p < 0.05). Conclusion: Overweight and obesity lead to a higher incidence of thoracic trauma in a polytrauma situation and may additionally handicap ventilation in an obstructive manner.

Thoracic target volume delineation using various maximum-intensity projection computed tomography image sets for stereotactic body radiation therapy

The motion of lung tumors during respiration makes the accurate delivery of radiation therapy to the thorax difficult because it increases the uncertainty of target position. The adoption of four-dimensional computed tomography (4D-CT) has allowed us to determine how a tumor moves with respiration for each individual patient. Using information acquired during a 4D-CT scan, we can define the target, visualize motion, and calculate dose during the planning phase of the radiotherapy process. One image data set that can be created from the 4D-CT acquisition is the maximum-intensity projection (MIP). The MIP can be used as a starting point to define the volume that encompasses the motion envelope of the moving gross target volume (GTV). Because of the close relationship that exists between the MIP and the final target volume, we investigated four MIP data sets created with different methodologies (3 using various 4D-CT sorting implementations, and one using all available cine CT images) to compare target delineation. It has been observed that changing the 4D-CT sorting method will lead to the selection of a different collection of images; however, the clinical implications of changing the constituent images on the resultant MIP data set are not clear. There has not been a comprehensive study that compares target delineation based on different 4D-CT sorting methodologies in a patient population. We selected a collection of patients who had previously undergone thoracic 4D-CT scans at our institution, and who had lung tumors that moved at least 1 cm. We then generated the four MIP data sets and automatically contoured the target volumes. In doing so, we identified cases in which the MIP generated from a 4D-CT sorting process under-represented the motion envelope of the target volume by more than 10% than when measured on the MIP generated from all of the cine CT images. The 4D-CT methods suffered from duplicate image selection and might not choose maximum extent images. Based on our results, we suggest utilization of a MIP generated from the full cine CT data set to ensure a representative inclusive tumor extent, and to avoid geometric miss.