Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Unraveling networked learning initiatives: an analytic framework

Networked learning happens naturally within the social systems of which we are all part. However, in certain circumstances individuals may want to actively take initiative to initiate interaction with others they are not yet regularly in exchange with. This may be the case when external influences and societal changes require innovation of existing practices. This paper proposes a framework with relevant dimensions providing insight into precipitated characteristics of designed as well as ‘fostered or grown’ networked learning initiatives. Networked learning initiatives are characterized as “goal-directed, interest-, or needs based activities of a group of (at least three) individuals that initiate interaction across the boundaries of their regular social systems”. The proposed framework is based on two existing research traditions, namely 'networked learning' and 'learning networks', comparing, integrating and building upon knowledge from both perspectives. We uncover some interesting differences between definitions, but also similarities in the way they describe what ‘networked’ means and how learning is conceptualized. We think it is productive to combine both research perspectives, since they both study the process of learning in networks extensively, albeit from different points of view, and their combination can provide valuable insights in networked learning initiatives. We uncover important features of networked learning initiatives, characterize actors and connections of which they are comprised and conditions which facilitate and support them. The resulting framework could be used both for analytic purposes and (partly) as a design framework. In this framework it is acknowledged that not all successful networks have the same characteristics: there is no standard ‘constellation’ of people, roles, rules, tools and artefacts, although there are indications that some network structures work better than others. Interactions of individuals can only be designed and fostered till a certain degree: the type of network and its ‘growth’ (e.g. in terms of the quantity of people involved, or the quality and relevance of co-created concepts, ideas, artefacts and solutions to its ‘inhabitants’) is in the hand of the people involved. Therefore, the framework consists of dimensions on a sliding scale. It introduces a structured and analytic way to look at the precipitation of networked learning initiatives: learning networks. Successive research on the application of this framework and feedback from the networked learning community is needed to further validate it’s usability and value to both research as well as practice.

Physical internet-enabled hyperconnected distribution assessment

L’Internet Physique (IP) est une initiative qui identifie plusieurs symptômes d’inefficacité et non-durabilité des systèmes logistiques et les traite en proposant un nouveau paradigme appelé logistique hyperconnectée. Semblable à l’Internet Digital, qui relie des milliers de réseaux d’ordinateurs personnels et locaux, IP permettra de relier les systèmes logistiques fragmentés actuels. Le but principal étant d’améliorer la performance des systèmes logistiques des points de vue économique, environnemental et social. Se concentrant spécifiquement sur les systèmes de distribution, cette thèse remet en question l’ordre de magnitude du gain de performances en exploitant la distribution hyperconnectée habilitée par IP. Elle concerne également la caractérisation de la planification de la distribution hyperconnectée. Pour répondre à la première question, une approche de la recherche exploratoire basée sur la modélisation de l’optimisation est appliquée, où les systèmes de distribution actuels et potentiels sont modélisés. Ensuite, un ensemble d’échantillons d’affaires réalistes sont créé, et leurs performances économique et environnementale sont évaluées en ciblant de multiples performances sociales. Un cadre conceptuel de planification, incluant la modélisation mathématique est proposé pour l’aide à la prise de décision dans des systèmes de distribution hyperconnectée. Partant des résultats obtenus par notre étude, nous avons démontré qu’un gain substantiel peut être obtenu en migrant vers la distribution hyperconnectée. Nous avons également démontré que l’ampleur du gain varie en fonction des caractéristiques des activités et des performances sociales ciblées. Puisque l’Internet physique est un sujet nouveau, le Chapitre 1 présente brièvement l’IP et hyper connectivité. Le Chapitre 2 discute les fondements, l’objectif et la méthodologie de la recherche. Les défis relevés au cours de cette recherche sont décrits et le type de contributions visés est mis en évidence. Le Chapitre 3 présente les modèles d’optimisation. Influencés par les caractéristiques des systèmes de distribution actuels et potentiels, trois modèles fondés sur le système de distribution sont développés. Chapitre 4 traite la caractérisation des échantillons d’affaires ainsi que la modélisation et le calibrage des paramètres employés dans les modèles. Les résultats de la recherche exploratoire sont présentés au Chapitre 5. Le Chapitre 6 décrit le cadre conceptuel de planification de la distribution hyperconnectée. Le chapitre 7 résume le contenu de la thèse et met en évidence les contributions principales. En outre, il identifie les limites de la recherche et les avenues potentielles de recherches futures.

GRASP and statistical bounds for heuristic solutions to combinatorial problems

The quality of a heuristic solution to a NP-hard combinatorial problem is hard to assess. A few studies have advocated and tested statistical bounds as a method for assessment. These studies indicate that statistical bounds are superior to the more widely known and used deterministic bounds. However, the previous studies have been limited to a few metaheuristics and combinatorial problems and, hence, the general performance of statistical bounds in combinatorial optimization remains an open question. This work complements the existing literature on statistical bounds by testing them on the metaheuristic Greedy Randomized Adaptive Search Procedures (GRASP) and four combinatorial problems. Our findings confirm previous results that statistical bounds are reliable for the p-median problem, while we note that they also seem reliable for the set covering problem. For the quadratic assignment problem, the statistical bounds has previously been found reliable when obtained from the Genetic algorithm whereas in this work they found less reliable. Finally, we provide statistical bounds to four 2-path network design problem instances for which the optimum is currently unknown.

Evaluating conservation and fisheries management strategies by linking spatial prioritization software and ecosystem and fisheries modelling tools

Well-designed marine protected area (MPA) networks can deliver a range of ecological, economic and social benefits, and so a great deal of research has focused on developing spatial conservation prioritization tools to help identify important areas. However, whilst these software tools are designed to identify MPA networks that both represent biodiversity and minimize impacts on stakeholders, they do not consider complex ecological processes. Thus, it is difficult to determine the impacts that proposed MPAs could have on marine ecosystem health, fisheries and fisheries sustainability. Using the eastern English Channel as a case study, this paper explores an approach to address these issues by identifying a series of MPA networks using the Marxan and Marxan with Zones conservation planning software and linking them with a spatially explicit ecosystem model developed in Ecopath with Ecosim. We then use these to investigate potential trade-offs associated with adopting different MPA management strategies. Limited-take MPAs, which restrict the use of some fishing gears, could have positive benefits for conservation and fisheries in the eastern English Channel, even though they generally receive far less attention in research on MPA network design. Our findings, however, also clearly indicate that no-take MPAs should form an integral component of proposed MPA networks in the eastern English Channel, as they not only result in substantial increases in ecosystem biomass, fisheries catches and the biomass of commercially valuable target species, but are fundamental to maintaining the sustainability of the fisheries. Synthesis and applications. Using the existing software tools Marxan with Zones and Ecopath with Ecosim in combination provides a powerful policy-screening approach. This could help inform marine spatial planning by identifying potential conflicts and by designing new regulations that better balance conservation objectives and stakeholder interests. In addition, it highlights that appropriate combinations of no-take and limited-take marine protected areas might be the most effective when making trade-offs between long-term ecological benefits and short-term political acceptability.

Considering climate change in the development of marine protected areas

Marine ecosystems are facing a diverse range of threats, including climate change, prompting international efforts to safeguard marine biodiversity through the use of spatial management measures. Marine Protected Areas (MPAs) have been implemented as a conservation tool throughout the world, but their usefulness and effectiveness is strongly related to climate change. However, few MPA programmes have directly considered climate change in the design, management or monitoring of an MPA network. Under international obligations, EU, UK and national targets, Scotland has developed an MPA network that aims to protect marine biodiversity and contribute to the vision of a clean, healthy and productive marine environment. This is the first study to critically analyse the Scottish MPA process and highlight areas which may be improved upon in further iterations of the network in the context of climate change. Initially, a critical review of the Scottish MPA process considered how ecological principles for MPA network design were incorporated into the process, how stakeholder perceptions were considered and crucially what consideration was given to the influence of climate change on the eventual effectiveness of the network. The results indicated that to make a meaningful contribution to marine biodiversity protection for Europe the Scottish MPA network should: i) fully adopt best practice ecological principles ii) ensure effective protection and iii) explicitly consider climate change in the management, monitoring and future iterations of the network. However, this review also highlighted the difficulties of incorporating considerations of climate change into an already complex process. A series of international case studies from British Columbia, Canada; central California, USA; the Great Barrier Reef, Australia and the Hauraki Gulf, New Zealand, were then conducted to investigate perceptions of how climate change has been considered in the design, implementation, management and monitoring of MPAs. The key lessons from this study included: i) strictly protected marine reserves are considered essential for climate change resilience and will be necessary as scientific reference sites to understand climate change effects ii) adaptive management of MPA networks is important but hard to implement iii) strictly protected reserves managed as ecosystems are the best option for an uncertain future. This work provides new insights into the policy and practical challenges MPA managers face under climate change scenarios. Based on the Scottish and international studies, the need to facilitate clear communication between academics, policy makers and stakeholders was recognised in order to progress MPA policy delivery and to ensure decisions were jointly formed and acceptable. A Delphi technique was used to develop a series of recommendations for considering climate change in Scotland’s MPA process. The Delphi participant panel was selected for their knowledge of the Scottish MPA process and included stakeholders, policy makers and academics with expertise in MPA research. The results from the first round of the Delphi technique suggested that differing views of success would likely influence opinions regarding required management of MPAs, and in turn, the data requirements to support management action decisions. The second round of the Delphi technique explored this further and indicated that there was a fundamental dichotomy in panellists’ views of a successful MPA network depending upon whether they believed the MPAs should be strictly protected or allow for sustainable use. A third, focus group round of the Delphi Technique developed a feature-based management scenario matrix to aid in deciding upon management actions in light of changes occurring in the MPA network. This thesis highlights that if the Scottish MPA network is to fulfil objectives of conservation and restoration, the implications of climate change for the design, management and monitoring of the network must be considered. In particular, there needs to be a greater focus on: i) incorporating ecological principles that directly address climate change ii) effective protection that builds resilience of the marine and linked social environment iii) developing a focused, strong and adaptable monitoring framework iv) ensuring mechanisms for adaptive management.

Using ICT Energy consumption for monitoring ICT architecture

Energy efficient policies are being applied to network protocols, devices and classical network management systems. Researchers have already studied in depth each of those fields, including for instance a long monitoring processes of various number of individual ICT equipment from where power models are constructed. With the development of smart meters and emerging protocols such as SNMP and NETCONF, currently there is an open field to couple the power models, translated to the expected behavior, with the realtime energy measurements. The goal is to derive a comparison on the power data between both of the processes in the direction of detection for possible deviations on the expected results. The logical assumption is that a fault in the usage of a particular device will not only increase its own energy usage, but also may cause additional consumption on the other devices part of the network. A platform is developed to monitor and analyze the retrieved power data of a simulated enterprise ICT infrastructure. Moreover, smart algorithms are developed which are aware of the different states that are occurring on each device during their typical use phase, as well as to detect and isolate possible anomalies. The produced results are obtained and validated with the use of Cisco switches and routers, Dell Precision stations and Raritan PDU as part of the monitored infrastructure.

Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

JOINT ENERGY BEAMFORMING AND TIME ASSIGNMENT FOR COOPERATIVE WIRELESS POWERED NETWORKS

Wireless power transfer (WPT) and radio frequency (RF)-based energy har- vesting arouses a new wireless network paradigm termed as wireless powered com- munication network (WPCN), where some energy-constrained nodes are enabled to harvest energy from the RF signals transferred by other energy-sufficient nodes to support the communication operations in the network, which brings a promising approach for future energy-constrained wireless network design. In this paper, we focus on the optimal WPCN design. We consider a net- work composed of two communication groups, where the first group has sufficient power supply but no available bandwidth, and the second group has licensed band- width but very limited power to perform required information transmission. For such a system, we introduce the power and bandwidth cooperation between the two groups so that both group can accomplish their expected information delivering tasks. Multiple antennas are employed at the hybrid access point (H-AP) to en- hance both energy and information transfer efficiency and the cooperative relaying is employed to help the power-limited group to enhance its information transmission throughput. Compared with existing works, cooperative relaying, time assignment, power allocation, and energy beamforming are jointly designed in a single system. Firstly, we propose a cooperative transmission protocol for the considered system, where group 1 transmits some power to group 2 to help group 2 with information transmission and then group 2 gives some bandwidth to group 1 in return. Sec- ondly, to explore the information transmission performance limit of the system, we formulate two optimization problems to maximize the system weighted sum rate by jointly optimizing the time assignment, power allocation, and energy beamforming under two different power constraints, i.e., the fixed power constraint and the aver- age power constraint, respectively. In order to make the cooperation between the two groups meaningful and guarantee the quality of service (QoS) requirements of both groups, the minimal required data rates of the two groups are considered as constraints for the optimal system design. As both problems are non-convex and have no known solutions, we solve it by using proper variable substitutions and the semi-definite relaxation (SDR). We theoretically prove that our proposed solution method can guarantee to find the global optimal solution. Thirdly, consider that the WPCN has promising application potentials in future energy-constrained net- works, e.g., wireless sensor network (WSN), wireless body area network (WBAN) and Internet of Things (IoT), where the power consumption is very critical. We investigate the minimal power consumption optimal design for the considered co- operation WPCN. For this, we formulate an optimization problem to minimize the total consumed power by jointly optimizing the time assignment, power allocation, and energy beamforming under required data rate constraints. As the problem is also non-convex and has no known solutions, we solve it by using some variable substitutions and the SDR method. We also theoretically prove that our proposed solution method for the minimal power consumption design guarantees the global optimal solution. Extensive experimental results are provided to discuss the system performance behaviors, which provide some useful insights for future WPCN design. It shows that the average power constrained system achieves higher weighted sum rate than the fixed power constrained system. Besides, it also shows that in such a WPCN, relay should be placed closer to the multi-antenna H-AP to achieve higher weighted sum rate and consume lower total power.

Estudio y optimización de las infraestructuras de los carriles para bicicletas

La necesidad cotidiana de los ciudadanos de desplazarse para realizar diferentes actividades, sea cual fuere su naturaleza, se ha visto afectada en gran medida por los cambios producidos. Las ventajas generadas por la inclusión de la bicicleta como modo de transporte y la proliferación de su uso entre la ciudadanía son innumerables y se extienden tanto en el ámbito de la movilidad urbana como del desarrollo sostenible. En la actualidad, hay multitud de programas para la implantación, fomento o aumento de la participación ciudadana relacionado con la bicicleta en las ciudades. Pero en definitiva, todos y cada uno de estas iniciativas tienen la misma finalidad, crear una malla de vías cicladles eficaz y útil. Capaces de permitir el uso de la bicicleta en vías preferentes con unas garantías de seguridad altas, incorporando la bicicleta en el modelo de intermodalidad del transporte urbano. Con la progresiva implantación del carril bici, muchas personas han empezado a utilizarlas para moverse por la ciudad. Pero todo lo nuevo necesita un periodo de adaptación. Y, la realidad es que la red de viales destinados para estos vehículos está repleta de obstáculos para el ciclista. La actual situación ha llevado a cuestionar qué cantidad de kilómetros de carriles bici son necesarios para abastecer la demanda existente de este modo de transporte y, si las obras ejecutadas y proyectadas son las correctas y suficientes. En este trabajo se presenta una herramienta, basada en un modelo de programación matemática, para el diseño óptimo de una red destinada a los ciclistas. En concreto, el sistema determina una infraestructura para la bicicleta adaptada a las características de la red de carreteras existentes, con base en criterios de teoría de grafos ponderados. Como una aplicación del modelo propuesto, se ofrece el resultado de estos experimentos, obteniéndose un número de conclusiones útiles para la planificación y el diseño de redes de carriles bici desde una perspectiva social. Se realiza una aplicación de la metodología desarrollada para el caso real del municipio de Málaga (España). Por último se produce la validación del modelo de optimización presentado y la repercusión que tiene éste sobre el resultado final y la importancia o el peso del total de variables capaces de condicionar el resultado final de la red ciclista. Se obtiene, por tanto, una herramienta destinada a la mejora de la planificación, diseño y gestión de las diferentes infraestructuras para la bicicleta, con capacidad de interactuar con el modelo de red vial actual y con el resto de los modos de transportes existentes en el entramado urbano de las ciudades.

Cipher cities : effective user interface design for building a digital social network around location-based gaming

In this paper we explore what is required of a User Interface (UI) design in order to encourage participation around playing and creating Location-Based Games (LBGs). To base our research in practice, we present Cipher Cities, a web based system. Through the design of this system, we investigate how UI design can provide tools for complex content creation to compliment and encourage the use of mobile phones for designing, distributing, and playing LBGs. Furthermore we discuss how UI design can promote and support socialisation around LBGs through the design of functional interface components and services such as groups, user profiles, and player status listings.

Reflective learning through social network sites in design education

Reflective learning is vital for successful practice-led education such as animation, multimedia design and graphic design, and social network sites can accommodate various learning styles for effective reflective learning. In this paper, the researcher studies reflective learning through social network sites with two animation units. These units aim to provide students with an understanding of the tasks and workflows involved in the production of style sheets, character sheets and motion graphics for use in 3D productions for film and television and game design. In particular, an assessment in these units requires students to complete their online reflective journals throughout the semester. The reflective learning has been integrated within the unit design and students are encouraged to reflect weekly learning processes and outcomes. A survey evaluating for students’ learning experience was conducted, and its outcomes indicate that social network site based reflective learning will not be effective without considering students’ learning circumstances and designing peer-to-peer interactions.

The design and evaluation of a mobile sensor/actuator network for autonomous animal control

This paper investigates a mobile, wireless sensor/actuator network application for use in the cattle breeding industry. Our goal is to prevent fighting between bulls in on-farm breeding paddocks by autonomously applying appropriate stimuli when one bull approaches another bull. This is an important application because fighting between high-value animals such as bulls during breeding seasons causes significant financial loss to producers. Furthermore, there are significant challenges in this type of application because it requires dynamic animal state estimation, real-time actuation and efficient mobile wireless transmissions. We designed and implemented an animal state estimation algorithm based on a state-machine mechanism for each animal. Autonomous actuation is performed based on the estimated states of an animal relative to other animals. A simple, yet effective, wireless communication model has been proposed and implemented to achieve high delivery rates in mobile environments. We evaluated the performance of our design by both simulations and field experiments, which demonstrated the effectiveness of our autonomous animal control system.

Single network adaptive critic design for power system stabilisers

The recently developed single network adaptive critic (SNAC) design has been used in this study to design a power system stabiliser (PSS) for enhancing the small-signal stability of power systems over a wide range of operating conditions. PSS design is formulated as a discrete non-linear quadratic regulator problem. SNAC is then used to solve the resulting discrete-time optimal control problem. SNAC uses only a single critic neural network instead of the action-critic dual network architecture of typical adaptive critic designs. SNAC eliminates the iterative training loops between the action and critic networks and greatly simplifies the training procedure. The performance of the proposed PSS has been tested on a single machine infinite bus test system for various system and loading conditions. The proposed stabiliser, which is relatively easier to synthesise, consistently outperformed stabilisers based on conventional lead-lag and linear quadratic regulator designs.

Power Optimal Network-on-Chip Interconnect Design

A large part of today's multi-core chips is interconnect. Increasing communication complexity has made essential new strategies for interconnects, such as Network on Chip. Power dissipation in interconnects has become a substantial part of the total power dissipation. Techniques to reduce interconnect power have thus become a necessity. In this paper, we present a design methodology that gives values of bus width for interconnect links, frequency of operation for routers, in Network on Chip scenario that satisfy required throughput and dissipate minimal switching power. We develop closed form analytical expressions for the power dissipation, with bus width and frequency as variables and then use Lagrange multiplier method to arrive at the optimal values. We present a 4 port router in 90 nm technology library as case study. The results obtained from analysis are discussed.