Search Space Reduction in QoS Routing

To provide real-time service or engineer constrained-based paths, networks require the underlying routing algorithm to be able to find low-cost paths that satisfy given Quality-of-Service (QoS) constraints. However, the problem of constrained shortest (least-cost) path routing is known to be NP-hard, and some heuristics have been proposed to find a near-optimal solution. However, these heuristics either impose relationships among the link metrics to reduce the complexity of the problem which may limit the general applicability of the heuristic, or are too costly in terms of execution time to be applicable to large networks. In this paper, we focus on solving the delay-constrained minimum-cost path problem, and present a fast algorithm to find a near-optimal solution. This algorithm, called DCCR (for Delay-Cost-Constrained Routing), is a variant of the k-shortest path algorithm. DCCR uses a new adaptive path weight function together with an additional constraint imposed on the path cost, to restrict the search space. Thus, DCCR can return a near-optimal solution in a very short time. Furthermore, we use the method proposed by Blokh and Gutin to further reduce the search space by using a tighter bound on path cost. This makes our algorithm more accurate and even faster. We call this improved algorithm SSR+DCCR (for Search Space Reduction+DCCR). Through extensive simulations, we confirm that SSR+DCCR performs very well compared to the optimal but very expensive solution.

Constraint-based Mining of Frequent Arrangements of Temporal Intervals

The problem of discovering frequent arrangements of temporal intervals is studied. It is assumed that the database consists of sequences of events, where an event occurs during a time-interval. The goal is to mine temporal arrangements of event intervals that appear frequently in the database. The motivation of this work is the observation that in practice most events are not instantaneous but occur over a period of time and different events may occur concurrently. Thus, there are many practical applications that require mining such temporal correlations between intervals including the linguistic analysis of annotated data from American Sign Language as well as network and biological data. Two efficient methods to find frequent arrangements of temporal intervals are described; the first one is tree-based and uses depth first search to mine the set of frequent arrangements, whereas the second one is prefix-based. The above methods apply efficient pruning techniques that include a set of constraints consisting of regular expressions and gap constraints that add user-controlled focus into the mining process. Moreover, based on the extracted patterns a standard method for mining association rules is employed that applies different interestingness measures to evaluate the significance of the discovered patterns and rules. The performance of the proposed algorithms is evaluated and compared with other approaches on real (American Sign Language annotations and network data) and large synthetic datasets.

Computing explanations for interactive constraint-based systems

Constraint programming has emerged as a successful paradigm for modelling combinatorial problems arising from practical situations. In many of those situations, we are not provided with an immutable set of constraints. Instead, a user will modify his requirements, in an interactive fashion, until he is satisfied with a solution. Examples of such applications include, amongst others, model-based diagnosis, expert systems, product configurators. The system he interacts with must be able to assist him by showing the consequences of his requirements. Explanations are the ideal tool for providing this assistance. However, existing notions of explanations fail to provide sufficient information. We define new forms of explanations that aim to be more informative. Even if explanation generation is a very hard task, in the applications we consider, we must manage to provide a satisfactory level of interactivity and, therefore, we cannot afford long computational times. We introduce the concept of representative sets of relaxations, a compact set of relaxations that shows the user at least one way to satisfy each of his requirements and at least one way to relax them, and present an algorithm that efficiently computes such sets. We introduce the concept of most soluble relaxations, maximising the number of products they allow. We present algorithms to compute such relaxations in times compatible with interactivity, achieving this by indifferently making use of different types of compiled representations. We propose to generalise the concept of prime implicates to constraint problems with the concept of domain consequences, and suggest to generate them as a compilation strategy. This sets a new approach in compilation, and allows to address explanation-related queries in an efficient way. We define ordered automata to compactly represent large sets of domain consequences, in an orthogonal way from existing compilation techniques that represent large sets of solutions.

Finding optimal alternatives based on efficient comparative preference inference

Choosing the right or the best option is often a demanding and challenging task for the user (e.g., a customer in an online retailer) when there are many available alternatives. In fact, the user rarely knows which offering will provide the highest value. To reduce the complexity of the choice process, automated recommender systems generate personalized recommendations. These recommendations take into account the preferences collected from the user in an explicit (e.g., letting users express their opinion about items) or implicit (e.g., studying some behavioral features) way. Such systems are widespread; research indicates that they increase the customers' satisfaction and lead to higher sales. Preference handling is one of the core issues in the design of every recommender system. This kind of system often aims at guiding users in a personalized way to interesting or useful options in a large space of possible options. Therefore, it is important for them to catch and model the user's preferences as accurately as possible. In this thesis, we develop a comparative preference-based user model to represent the user's preferences in conversational recommender systems. This type of user model allows the recommender system to capture several preference nuances from the user's feedback. We show that, when applied to conversational recommender systems, the comparative preference-based model is able to guide the user towards the best option while the system is interacting with her. We empirically test and validate the suitability and the practical computational aspects of the comparative preference-based user model and the related preference relations by comparing them to a sum of weights-based user model and the related preference relations. Product configuration, scheduling a meeting and the construction of autonomous agents are among several artificial intelligence tasks that involve a process of constrained optimization, that is, optimization of behavior or options subject to given constraints with regards to a set of preferences. When solving a constrained optimization problem, pruning techniques, such as the branch and bound technique, point at directing the search towards the best assignments, thus allowing the bounding functions to prune more branches in the search tree. Several constrained optimization problems may exhibit dominance relations. These dominance relations can be particularly useful in constrained optimization problems as they can instigate new ways (rules) of pruning non optimal solutions. Such pruning methods can achieve dramatic reductions in the search space while looking for optimal solutions. A number of constrained optimization problems can model the user's preferences using the comparative preferences. In this thesis, we develop a set of pruning rules used in the branch and bound technique to efficiently solve this kind of optimization problem. More specifically, we show how to generate newly defined pruning rules from a dominance algorithm that refers to a set of comparative preferences. These rules include pruning approaches (and combinations of them) which can drastically prune the search space. They mainly reduce the number of (expensive) pairwise comparisons performed during the search while guiding constrained optimization algorithms to find optimal solutions. Our experimental results show that the pruning rules that we have developed and their different combinations have varying impact on the performance of the branch and bound technique.

Changes in landing mechanics in patients following anterior cruciate ligament reconstruction when wearing an extension constraint knee brace.

BACKGROUND: Anterior cruciate ligament (ACL) reconstruction is associated with a high incidence of second tears (graft tears and contralateral ACL tears). These secondary tears have been attributed to asymmetrical lower extremity mechanics. Knee bracing is one potential intervention that can be used during rehabilitation that has the potential to normalize lower extremity asymmetry; however, little is known about the effect of bracing on movement asymmetry in patients following ACL reconstruction. HYPOTHESIS: Wearing a knee brace would increase knee joint flexion and joint symmetry. It was also expected that the joint mechanics would become more symmetrical in the braced condition. OBJECTIVE: To examine how knee bracing affects knee joint function and symmetry over the course of rehabilitation in patients 6 months following ACL reconstruction. STUDY DESIGN: Controlled laboratory study. LEVEL OF EVIDENCE: Level 3. METHODS: Twenty-three adolescent patients rehabilitating from ACL reconstruction surgery were recruited for the study. The subjects all underwent a motion analysis assessment during a stop-jump activity with and without a functional knee brace on the surgical side that resisted extension for 6 months following the ACL reconstruction surgery. Statistical analysis utilized a 2 × 2 (limb × brace) analysis of variance with a significant alpha level of 0.05. RESULTS: Subjects had increased knee flexion on the surgical side when they were braced. The brace condition increased knee flexion velocity, decreased the initial knee flexion angle, and increased the ground reaction force and knee extension moment on both limbs. Side-to-side asymmetry was present across conditions for the vertical ground reaction force and knee extension moment. CONCLUSION: Wearing a knee brace appears to increase lower extremity compliance and promotes normalized loading on the surgical side. CLINICAL RELEVANCE: Knee extension constraint bracing in postoperative ACL patients may improve symmetry of lower extremity mechanics, which is potentially beneficial in progressing rehabilitation and reducing the incidence of second ACL tears.

Coupled 3-D finite difference time domain and finite volume methods for solving microwave heating in porous media

Computational results for the microwave heating of a porous material are presented in this paper. Combined finite difference time domain and finite volume methods were used to solve equations that describe the electromagnetic field and heat and mass transfer in porous media. The coupling between the two schemes is through a change in dielectric properties which were assumed to be dependent both on temperature and moisture content. The model was able to reflect the evolution of temperature and moisture fields as the moisture in the porous medium evaporates. Moisture movement results from internal pressure gradients produced by the internal heating and phase change.

Two-machine open shop scheduling with an availability constraint

We study a two-machine open shop scheduling problem, in which one machine is not available for processing during a given time interval. The objective is to minimize the makespan. We show that the problem is NP-hard and present an approximation algorithm with a worst-case ratio of 4/3.

Pre-emptive scheduling problems with controllable processing times

We consider a range of single machine and identical parallel machine pre-emptive scheduling models with controllable processing times. For each model we study a single criterion problem to minimize the compression cost of the processing times subject to the constraint that all due dates should be met. We demonstrate that each single criterion problem can be formulated in terms of minimizing a linear function over a polymatroid, and this justifies the greedy approach to its solution. A unified technique allows us to develop fast algorithms for solving both single criterion problems and bicriteria counterparts.

Characterizing the most general temporal constraint

This paper introduces a characterization of the so-called most general temporal constraint (GTC), which guarantees the common-sense assertion that "the beginning of the effect cannot precede the beginning of the cause". The formalism is based on general time theory which takes both points and intervals as primitive. It is shown that there are in fact 8 possible causal relationships which satisfy GTC, including cases where, on the one hand, effects start simultaneously with, during, immediately after, or some time after their causes, and on the other hand, events end before, simultaneously with, or after their causes. These causal relationships are versatile enough to subsume those representatives in the literature.

Preemptive scheduling on uniform parallel machines with controllable job processing times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.

A price worth paying?: Women and work – choice, constraint or satisficing

Purpose – Are women held back or holding back? Do women choose their jobs/careers or are they structurally or normatively constrained? The purpose of this paper is to shed fresh light on these questions and contribute to an on-going debate that has essentially focused on the extent to which part-time work is women’s choice, the role of structural and organisational constraints and the role of men in excluding women. Design/methodology/approach – The paper uses data from interviews with 80 working women – both full-time and part-time – performing diverse work roles in a range of organisations in the south east of England. Findings – It was found that many women do not make strategic job choices, rather they often ‘‘fall into’’ jobs that happen to be available to them. Some would not have aspired to their present jobs without male encouragement; many report incidents of male exclusion; and virtually all either know or suspect that they are paid less than comparable men. Those working reduced hours enjoy that facility, yet they are aware that reduced hours and senior roles are seen as incompatible. In short, they recognise both the positive and negative aspects of their jobs, whether they work full or part-time, whether they work in male-dominated or female-dominated occupations, and whatever their position in the organisational hierarchy. Accordingly, the paper argues that the concept of ‘‘satisficing’’, i.e. a decision which is good enough but not optimal, is a more appropriate way to view women’s working lives than are either choice or constraint theories. Originality/value – There is an ongoing, and often polarised, debate between those who maintain that women choose whether to give preference to work or home/family and others who maintain that women, far from being self-determining actors, are constrained structurally and normatively. Rather than supporting these choice or constraint theories, this paper argues that ‘‘satisficing’’ is a more appropriate and nuanced concept to explain women’s working lives.

Using the interact system model to analyze computer mediated communication during a small group problem-solving task

The Interact System Model (ISM) developed by Fisher and Hawes (1971) for the analysis of face-to-face communication during small-group problem solving activities was used to study online communication. This tool proved to be of value in the analysis, but the conversation patterns reported by Fisher (1980) did not fully appear in the online environment. Participants displayed a habit of "being too polite" and not fully voicing their disagreements with ideas posed by others. Thus progress towards task completion was slow and incomplete.

Math-Towers: Online Interactive Collaborative Mathematics Explorations & Problem-Solving for Students Ages 11 to 15 years (Grades 6 to 10)

Math-Towers (www.math-towers.ca) is an online resource for students in grades 6 to 10 that supports collaborative problem-solving and investigations. This paper presents the philosophical position motivating the development of Math-Towers and describes how the site presents and motivates the mathematical challenges and supports participants' exploration and collaboration.