An investigation into feature construction to assist word sense disambiguation

Identifying the correct sense of a word in context is crucial for many tasks in natural language processing (machine translation is an example). State-of-the art methods for Word Sense Disambiguation (WSD) build models using hand-crafted features that usually capturing shallow linguistic information. Complex background knowledge, such as semantic relationships, are typically either not used, or used in specialised manner, due to the limitations of the feature-based modelling techniques used. On the other hand, empirical results from the use of Inductive Logic Programming (ILP) systems have repeatedly shown that they can use diverse sources of background knowledge when constructing models. In this paper, we investigate whether this ability of ILP systems could be used to improve the predictive accuracy of models for WSD. Specifically, we examine the use of a general-purpose ILP system as a method to construct a set of features using semantic, syntactic and lexical information. This feature-set is then used by a common modelling technique in the field (a support vector machine) to construct a classifier for predicting the sense of a word. In our investigation we examine one-shot and incremental approaches to feature-set construction applied to monolingual and bilingual WSD tasks. The monolingual tasks use 32 verbs and 85 verbs and nouns (in English) from the SENSEVAL-3 and SemEval-2007 benchmarks; while the bilingual WSD task consists of 7 highly ambiguous verbs in translating from English to Portuguese. The results are encouraging: the ILP-assisted models show substantial improvements over those that simply use shallow features. In addition, incremental feature-set construction appears to identify smaller and better sets of features. Taken together, the results suggest that the use of ILP with diverse sources of background knowledge provide a way for making substantial progress in the field of WSD.

An integer linear programming approach for approximate string comparison

We introduce a problem called maximum common characters in blocks (MCCB), which arises in applications of approximate string comparison, particularly in the unification of possibly erroneous textual data coming from different sources. We show that this problem is NP-complete, but can nevertheless be solved satisfactorily using integer linear programming for instances of practical interest. Two integer linear formulations are proposed and compared in terms of their linear relaxations. We also compare the results of the approximate matching with other known measures such as the Levenshtein (edit) distance. (C) 2008 Elsevier B.V. All rights reserved.

Job rotation in assembly lines employing disabled workers

In this paper we consider the programming of job rotation in the assembly line worker assignment and balancing problem. The motivation for this study comes from the designing of assembly lines in sheltered work centers for the disabled, where workers have different task execution times. In this context, the well-known training aspects associated with job rotation are particularly desired. We propose a metric along with a mixed integer linear model and a heuristic decomposition method to solve this new job rotation problem. Computational results show the efficacy of the proposed heuristics. (C) 2009 Elsevier B.V. All rights reserved.

On the effects of geographical constraints on task execution in complex

In the present work, the effects of spatial constraints on the efficiency of task execution in systems underlain by geographical complex networks are investigated, where the probability of connection decreases with the distance between the nodes. The investigation considers several configurations of the parameters defining the network connectivity, and the Barabasi-Albert network model is also considered for comparisons. The results show that the effect of connectivity is significant only for shorter tasks, the locality of connection simplied by the spatial constraints reduces efficiency, and the addition of edges can improve the efficiency of the execution, although with increasing locality of the connections the improvement is small.

Scheduling Grid Applications with Software Requirements

The aim of task scheduling is to minimize the makespan of applications, exploiting the best possible way to use shared resources. Applications have requirements which call for customized environments for their execution. One way to provide such environments is to use virtualization on demand. This paper presents two schedulers based on integer linear programming which schedule virtual machines (VMs) in grid resources and tasks on these VMs. The schedulers differ from previous work by the joint scheduling of tasks and VMs and by considering the impact of the available bandwidth on the quality of the schedule. Experiments show the efficacy of the schedulers in scenarios with different network configurations.

Proximal methods for nonlinear programming: double regularization and inexact subproblems

This paper describes the first phase of a project attempting to construct an efficient general-purpose nonlinear optimizer using an augmented Lagrangian outer loop with a relative error criterion, and an inner loop employing a state-of-the art conjugate gradient solver. The outer loop can also employ double regularized proximal kernels, a fairly recent theoretical development that leads to fully smooth subproblems. We first enhance the existing theory to show that our approach is globally convergent in both the primal and dual spaces when applied to convex problems. We then present an extensive computational evaluation using the CUTE test set, showing that some aspects of our approach are promising, but some are not. These conclusions in turn lead to additional computational experiments suggesting where to next focus our theoretical and computational efforts.

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.

Using ant colonies for solve the multiprocessor task graph scheduling

The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer.In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time.We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space.A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.

Task assignment optimization in SAP Extended WarehouseManagement

Nowadays in the world of mass consumption there is big demand for distributioncenters of bigger size. Managing such a center is a very complex and difficult taskregarding to the different processes and factors in a usual warehouse when we want tominimize the labor costs. Most of the workers’ working time is spent with travelingbetween source and destination points which cause deadheading. Even if a worker knowsthe structure of a warehouse well and because of that he or she can find the shortest pathbetween two points, it is still not guaranteed that there won’t be long traveling timebetween the locations of two consecutive tasks. We need optimal assignments betweentasks and workers.In the scientific literature Generalized Assignment Problem (GAP) is a wellknownproblem which deals with the assignment of m workers to n tasks consideringseveral constraints. The primary purpose of my thesis project was to choose a heuristics(genetic algorithm, tabu search or ant colony optimization) to be implemented into SAPExtended Warehouse Management (SAP EWM) by with task assignment will be moreeffective between tasks and resources.After system analysis I had to realize that due different constraints and businessdemands only 1:1 assingments are allowed in SAP EWM. Because of that I had to use adifferent and simpler approach – instead of the introduced heuristics – which could gainbetter assignments during the test phase in several cases. In the thesis I described indetails what ware the most important questions and problems which emerged during theplanning of my optimized assignment method.

Report on IEA Task-14 activities on solar collector systems conference in Rome, 25-29 Jan. 1993

The memebers of IEA (International Energy Agency) Task 14 (Advaced Active Solar Systems) met in Rome during January 1993. The latest developments in several countries were presented and discussed during this meeting. This report describes briefly the recent work carried out on small scale systems in the Domestic Hot Water (DHW) working group of Task 14, as reported by the representatives from Canada, Denmark, Germany, Holland and Switzerland. Klaus Lorenz, SERC, attended the meeting as observer and presented our work on small-tube heat exchangers. Several participants expressed their interest. A summary of his presentation is included in this report.

Rapport från/Report from IEA Task-14 mötet/meeting on solar heating system, Hameln Tyskland/Germany August 1992

Participation as observer at the meeting of Task 14 of IEA's Solar Heating and Cooling Projects held in Hameln, Germany has led to greater understanding of interesting developments underway in several countries. This will be of use during the development of small scale systems suitable for Swedish conditions. A summary of the work carried out by the working groups within Task 14 is given, with emphasis on the Domestic Hot Water group. Experiences of low-flow systems from several countries are related, and the conclusion is drawn that the maximum theoretical possible increase in performance of 20% has not been achieved due to poor heat exchangers and poor stratification in the storage tanks. Positive developments in connecting tubes and pumps is noted. Further participation as observer in Task 14 meetings is desired, and is looked on favourably by the members of the group. Another conclusion is that SERC should carry on with work on Swedish storage tanks, with emphasis on better stratification and heat exchangers, and possible modelling of system components. Finally a German Do-it-Vourself kit is described and judged in comparison with prefabricated models and Swedish Do-it-Yourself kits.

A reason to believe : beliefs as an influence on students task solving

Upper secondary students’ task solving reasoning was analysed, with a focus on what grounds they had for different strategy choices and conclusions. Beliefs were identified and connected with the reasoning that took place. The results indicate that beliefs have an impact on the central decisions made during task solving. Three themes stand out: safety, expectation and motivation.

Barriers and facilitators in the provision of post-abortion care at district level in central Uganda : a qualitative study focusing on task sharing between physicians and midwives

Background: Abortion is restricted in Uganda, and poor access to contraceptive methods result in unwanted pregnancies. This leaves women no other choice than unsafe abortion, thus placing a great burden on the Ugandan health system and making unsafe abortion one of the major contributors to maternal mortality and morbidity in Uganda. The existing sexual and reproductive health policy in Uganda supports the sharing of tasks in post-abortion care. This task sharing is taking place as a pragmatic response to the increased workload. This study aims to explore physicians' and midwives' perception of post-abortion care with regard to professional competences, methods, contraceptive counselling and task shifting/sharing in post-abortion care. Methods: In-depth interviews (n = 27) with health care providers of post-abortion care were conducted in seven health facilities in the Central Region of Uganda. The data were organized using thematic analysis with an inductive approach. Results: Post-abortion care was perceived as necessary, albeit controversial and sometimes difficult to provide. Together with poor conditions post-abortion care provoked frustration especially among midwives. Task sharing was generally taking place and midwives were identified as the main providers, although they would rarely have the proper training in post-abortion care. Additionally, midwives were sometimes forced to provide services outside their defined task area, due to the absence of doctors. Different uterine evacuation skills were recognized although few providers knew of misoprostol as a method for post-abortion care. An overall need for further training in post-abortion care was identified. Conclusions: Task sharing is taking place, but providers lack the relevant skills for the provision of quality care. For post-abortion care to improve, task sharing needs to be scaled up and in-service training for both doctors and midwives needs to be provided. Post-abortion care should further be included in the educational curricula of nurses and midwives. Scaled-up task sharing in post-abortion care, along with misoprostol use for uterine evacuation would provide a systematic approach to improving the quality of care and accessibility of services, with the aim of reducing abortion-related mortality and morbidity in Uganda.