A multilevel algorithm for force-directed graph-drawing

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

Multilevel refinement for combinatorial optimisation problems

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.

Multilevel refinement for the vehicle routing problem

Multilevel approaches to computational problems are pervasive across many areas of applied mathematics and scientific computing. The multilevel paradigm uses recursive coarsening to create a hierarchy of approximations to the original problem, then an initial solution is found for the coarsest problem and iteratively refined and improved at each level, coarsest to finest. The solution process is aided by the global perspective (or `global view') imparted to the optimisation by the coarsening. This paper looks at their application to the Vehicle Routing Problem.

Multilevel refinement strategies for the capacity vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL algorithm, which uses a combination of standard VRP heuristics, is developed first to solve instances of the VRP. A ML version, which extends the global view of these heuristics, is then created, using variants of the construction and improvement heuristics at each level. Finally some multilevel enhancements are developed. Experimentation is used to find suitable parameter settings and the final version is tested on two well-known VRP benchmark suites. Results comparing both SL and ML algorithms are presented.

The application of multilevel refinement to the vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL heuristic, termed the combined node-exchange composite heuristic (CNCH), is developed first to solve instances of the VRP. A ML version (the ML-CNCH) is then created, using the construction and improvement heuristics of the CNCH at each level. Experimentation is used to find a suitable combination, which extends the global view of these heuristics. Results comparing both SL and ML are presented.

Multilevel refinement for combinatorial optimisation: boosting metaheuristic performance

The multilevel paradigm as applied to combinatorial optimisation problems is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found, usually at the coarsest level, and then iteratively refined at each level, coarsest to finest, typically by using some kind of heuristic optimisation algorithm (either a problem-specific local search scheme or a metaheuristic). Solution extension (or projection) operators can transfer the solution from one level to another. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (for example multigrid techniques can be viewed as a prime example of the paradigm). Overview papers such as [] attest to its efficacy. However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial problems and in this chapter we discuss recent developments. In this chapter we survey the use of multilevel combinatorial techniques and consider their ability to boost the performance of (meta)heuristic optimisation algorithms.

The use of a mathematical multicriteria decision-making model for selecting the fire origin room

Over the last three decades, the fire safety codes have been changing from a prescriptive approach to a performance-based one. Some countries, such as the USA, Sweden, New Zealand, Australia and the UK, are in an advanced stage of development and implementation of the performance-based codes. However, there are some difficulties in this process. Most of them are due to the uncertainties associated with fire design. For instance, one of the questions that need to be answered is how to select the most probable fire origin room (FOR)? On the other hand, to know where the FOR is located is also an important aspect in terms of forensic issues. Given that, to address this question is an important step for the establishment of fire designs (i.e., pre-fire phases) and also for fire investigations (i.e., post-fire phases). This paper proposes a methodology for selecting the FOR through the use of a mathematical multicriteria decision-making model: the analytical hierarchy process (AHP). The proposed method is then applied to a hypothetical study case. The results are presented and discussed in this paper.

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.

Routine maintenance and sustainability of existing social housing

Presently the UK social housing stock accounts for approximately 18% of the total UK housing with maintenance costs in the region of £1.25 billion per annum. In terms of its impact on the environment, housing is generally responsible for approximately 27% of the UK’s CO2 emissions. The extent to which routine maintenance (planned preventative and responsive) can be used as a vehicle to improve the overall sustainability (social, environmental and economic) of existing social housing is one focus of a 5 year EPSRC funded research programme. This paper reports on the findings of a series of in-depth interviews with social housing providers examining current social housing maintenance practices and attitudes towards sustainability. This paper will report the initial findings of interviews and outline a new performance based multi-criteria maintenance model from which an AHP hierarchy will be presented, integrating the principles of sustainability into maintenance strategies

Bridging the gap with teamwork: collaborative leadership for communities of practice in the learning and skills sector

Collaborative approaches in leadership and management are increasingly acknowledged to play a key role in successful institutions in the learning and skills sector (LSS) (Ofsted, 2004). Such approaches may be important in bridging the potential 'distance' (psychological, cultural, interactional and geographical) (Collinson, 2005) that may exist between 'leaders' and 'followers', fostering more democratic communal solidarity. This paper reports on a 2006-07 research project funded by the Centre for Excellence in Leadership (CEL) that aimed to collect and analyse data on 'collaborative leadership' (CL) in the learning and skills sector. The project investigated collaborative leadership and its potential for benefiting staff through trust and knowledge-sharing in communities of practice (CoPs). The project forms part of longer-term educational research investigating leadership in a collaborative inquiry process (Jameson et al., 2006). The research examined the potential for CL to benefit institutions, analysing respondents' understanding of and resistance to collaborative practices. Quantitative and qualitative data from senior managers and lecturers was analysed using electronic data in SPSS and Tropes Zoom. The project aimed to recommend systems and practices for more inclusive, diverse leadership (Lumby et al., 2005). Collaborative leadership has increasingly gained international prominence as emphasis shifted towards team leadership beyond zero-sum 'leadership'/ 'followership' polarities into more mature conceptions of shared leadership spaces, within which synergistic leadership spaces can be mediated. The relevance of collaboration within the LSS has been highlighted following a spate of recent government-driven policy developments in FE. The promotion of CL addresses concerns about the apparent 'remoteness' of some senior managers, and the 'neo-management' control of professionals which can increase 'distance' between leaders and 'followers' and may de-professionalise staff in an already disempowered sector. Positive benefit from 'collaborative advantage' tends to be assumed in idealistic interpretations of CL, but potential 'collaborative inertia' may be problematic in a sector characterised by rapid top-down policy changes and continuous external audit and surveillance. Constant pressure for achievement against goals leaves little time for democratic group negotiations, despite the desires of leaders to create a more collaborative ethos. Yet prior models of intentional communities of practice potentially offer promise for CL practice to improve group performance despite multiple constraints. The CAMEL CoP model (JISC infoNet, 2006) was linked to the project, providing one practical way of implementing CL within situated professional networks.The project found that a good understanding of CL was demonstrated by most respondents, who thought it could enable staff to share power and work in partnership to build trust and conjoin skills, abilities and experience to achieve common goals for the good of the sector. However, although most respondents expressed agreement with the concept and ideals of CL, many thought this was currently an idealistically democratic, unachievable pipe dream in the LSS. Many respondents expressed concerns with the 'audit culture' and authoritarian management structures in FE. While there was a strong desire to see greater levels of implementation of CL, and 'collaborative advantage' from the 'knowledge sharing benefit potential' of team leadership, respondents also strongly advised against the pitfalls of 'collaborative inertia'. A 'distance' between senior leadership views and those of staff lower down the hierarchy regarding aspects of leadership performance in the sector was reported. Finally, the project found that more research is needed to investigate CL and develop innovative methods of practical implementation within autonomous communities of professional practice.