Polyhedral study of mixed integer sets arising from inventory problems

“Branch-and-cut” algorithm is one of the most efficient exact approaches to solve mixed integer programs. This algorithm combines the advantages of a pure branch-and-bound approach and cutting planes scheme. Branch-and-cut algorithm computes the linear programming relaxation of the problem at each node of the search tree which is improved by the use of cuts, i.e. by the inclusion of valid inequalities. It should be taken into account that selection of strongest cuts is crucial for their effective use in branch-and-cut algorithm. In this thesis, we focus on the derivation and use of cutting planes to solve general mixed integer problems, and in particular inventory problems combined with other problems such as distribution, supplier selection, vehicle routing, etc. In order to achieve this goal, we first consider substructures (relaxations) of such problems which are obtained by the coherent loss of information. The polyhedral structure of those simpler mixed integer sets is studied to derive strong valid inequalities. Finally those strong inequalities are included in the cutting plane algorithms to solve the general mixed integer problems. We study three mixed integer sets in this dissertation. The first two mixed integer sets arise as a subproblem of the lot-sizing with supplier selection, the network design and the vendor-managed inventory routing problems. These sets are variants of the well-known single node fixed-charge network set where a binary or integer variable is associated with the node. The third set occurs as a subproblem of mixed integer sets where incompatibility between binary variables is considered. We generate families of valid inequalities for those sets, identify classes of facet-defining inequalities, and discuss the separation problems associated with the inequalities. Then cutting plane frameworks are implemented to solve some mixed integer programs. Preliminary computational experiments are presented in this direction.

On the application of optimal control techniques in lossy fieldbuses

The performance of real-time networks is under continuous improvement as a result of several trends in the digital world. However, these tendencies not only cause improvements, but also exacerbates a series of unideal aspects of real-time networks such as communication latency, jitter of the latency and packet drop rate. This Thesis focuses on the communication errors that appear on such realtime networks, from the point-of-view of automatic control. Specifically, it investigates the effects of packet drops in automatic control over fieldbuses, as well as the architectures and optimal techniques for their compensation. Firstly, a new approach to address the problems that rise in virtue of such packet drops, is proposed. This novel approach is based on the simultaneous transmission of several values in a single message. Such messages can be from sensor to controller, in which case they are comprised of several past sensor readings, or from controller to actuator in which case they are comprised of estimates of several future control values. A series of tests reveal the advantages of this approach. The above-explained approach is then expanded as to accommodate the techniques of contemporary optimal control. However, unlike the aforementioned approach, that deliberately does not send certain messages in order to make a more efficient use of network resources; in the second case, the techniques are used to reduce the effects of packet losses. After these two approaches that are based on data aggregation, it is also studied the optimal control in packet dropping fieldbuses, using generalized actuator output functions. This study ends with the development of a new optimal controller, as well as the function, among the generalized functions that dictate the actuator’s behaviour in the absence of a new control message, that leads to the optimal performance. The Thesis also presents a different line of research, related with the output oscillations that take place as a consequence of the use of classic co-design techniques of networked control. The proposed algorithm has the goal of allowing the execution of such classical co-design algorithms without causing an output oscillation that increases the value of the cost function. Such increases may, under certain circumstances, negate the advantages of the application of the classical co-design techniques. A yet another line of research, investigated algorithms, more efficient than contemporary ones, to generate task execution sequences that guarantee that at least a given number of activated jobs will be executed out of every set composed by a predetermined number of contiguous activations. This algorithm may, in the future, be applied to the generation of message transmission patterns in the above-mentioned techniques for the efficient use of network resources. The proposed task generation algorithm is better than its predecessors in the sense that it is capable of scheduling systems that cannot be scheduled by its predecessor algorithms. The Thesis also presents a mechanism that allows to perform multi-path routing in wireless sensor networks, while ensuring that no value will be counted in duplicate. Thereby, this technique improves the performance of wireless sensor networks, rendering them more suitable for control applications. As mentioned before, this Thesis is centered around techniques for the improvement of performance of distributed control systems in which several elements are connected through a fieldbus that may be subject to packet drops. The first three approaches are directly related to this topic, with the first two approaching the problem from an architectural standpoint, whereas the third one does so from more theoretical grounds. The fourth approach ensures that the approaches to this and similar problems that can be found in the literature that try to achieve goals similar to objectives of this Thesis, can do so without causing other problems that may invalidate the solutions in question. Then, the thesis presents an approach to the problem dealt with in it, which is centered in the efficient generation of the transmission patterns that are used in the aforementioned approaches.

Avaliação da gestão curricular da matemática : cursos profissionais III

No mundo do trabalho, designadamente na indústria, acentua-se o défice de competências matemáticas nos profissionais da indústria, particularmente a Modelação Matemática, facto que constitui uma preocupação crescente à escala mundial e, obviamente, do sistema educativo português e da comunidade matemática nacional. Este défice é justificado pela falta de formação dos professores em contexto industrial e, de acordo com a National Council of Teachers of Mathematics, pela incapacidade que muitos docentes têm em apresentar a Matemática aplicada a situações laborais. Face à relevância social, económica e política da problemática descrita, centrou-se o presente estudo na Avaliação da Gestão Curricular da Matemática nos Cursos Profissionais de nível III do ensino secundário em Portugal, com enfoque na Modelação Matemática que, segundo os referentes internacionais, é simultaneamente uma competência e uma metodologia de ensino promotora do desenvolvimento de competências matemáticas nos profissionais da indústria. No contexto da gestão do currículo da Matemática para os cursos profissionais de nível III em escolas secundárias portuguesas, desenvolveu-se o presente estudo para se responder à questão de investigação: Em que medida a gestão curricular da Matemática, instituída, intencional e implementada nos cursos profissionais de nível III contempla situações-problema, suscetíveis de promover o desenvolvimento de competências no aluno, relevantes para o seu desempenho profissional? Construiu-se um referencial de avaliação, centrado na dimensão ecológica, segundo o modelo teórico Enfoque Ontosemiótico, abarcando um conjunto de sub-dimensões sobre as quais foram definidos critérios e respetivos indicadores. De realçar, ainda, que o referencial, além de ter servido de instrumento de avaliação da gestão curricular da Matemática nos cursos profissionais de nível III do ensino secundário, serviu, também, como guia orientador no desenho das sete situações-problema de natureza de Modelação Matemática no estudo de funções. O enquadramento metodológico do presente estudo assentou no método Estudo de Caso. Para analisar o caso, selecionaram-se sete unidades integradas de análise, a saber: a gestão curricular da Matemática de cada um dos seis professores participantes e a gestão curricular da Matemática instituída pelos normativos oficiais (programa da componente de formação científica da disciplina de Matemática para os cursos profissionais). Para a análise dos dados empíricos, respeitantes à gestão instituída, recorreuse à análise de conteúdo e teve essencialmente como propósito avaliar em que medida as orientações curriculares, emanadas no Programa da componente de formação científica disciplina de Matemática para os cursos profissionais de nível III, estão em conformidade com os referenciais teóricos. Sequencialmente, a operacionalização da avaliação intencional consubstanciou-se nos planos das aulas cedidos previamente a cada observação. A análise de conteúdo, como técnica de tratamento dos dados empíricos, foi a forma de se aceder às intenções de cada professor participante no estudo. A observação de aulas sucedeu à avaliação do plano de aula, constituindo a forma de avaliar in loco a gestão curricular da Matemática implementada, permitindo avaliar a coerência das observações com as intenções expressas nas planificações. Os registos das observações foram concretizados sob a forma de notas de campo que incluem uma componente descritiva e outra reflexiva que se dirigem para a análise dos dados empíricos recolhidos. Em termos de resultados, a avaliação da gestão curricular instituída foi reveladora de que o postulado pelos referentes para o desenvolvimento de competências tem a sua representação nas orientações curriculares expressas no Programa da componente de formação científica da disciplina de Matemática para os cursos profissionais de nível III. Contrariamente, a gestão curricular da Matemática pelos professores participantes revelou-se muito condicionada ao cumprimento dos conteúdos propostos pelo programa da disciplina. Por conseguinte, a gestão curricular da Matemática por competências, enfatizada no Programa (gestão instituída), encontrou, neste estudo, pouca tradução na gestão curricular intencional e implementada dos professores participantes, na medida em que a mesma não refletiu uma articulação com a componente de formação técnica do curso, visando uma metodologia proactiva no desenho de situações-problema promotoras de desenvolver, nos alunos, competências profícuas para a sua profissão, nomeadamente a Modelação Matemática. De salientar, ainda, que uma percentagem muito significativa de situações-problema propostas pelos professores não são, no geral, pertinentes para os respetivos cursos, não sendo, neste sentido, promotoras do estabelecimento de ligação com a futura performance profissional dos alunos. Tal lacuna parece ter resultado da ausência de trabalho colaborativo entre os professores de Matemática e os restantes docentes que constituem a equipa formativa do curso, lacuna que dificulta a articulação e coordenação em prol de um ensino contextualizado, ou ainda pela ausência de formação contínua pelos professores, no âmbito de temáticas inerentes à gestão curricular a cursos profissionais.

A convergência dos vídeos musicais na web social: conceptualização e análise

A investigação tem por objetivo a elaboração de um modelo de análise da convergência dos vídeos musicais na Web Social que pressupõe a proposta prévia de uma abordagem epistemológica que promova os vídeos musicais a objeto de estudo nos novos paradigmas de informação e comunicação em plataformas digitais, através de uma abordagem transdisciplinar entre os Web Studies e os Estudos Literários. O corolário da investigação consistirá na elaboração de um modelo conceptual da difusão dos vídeos musicais na Web Social, que será entendida como um processo dinâmico enquadrado no paradigma da convergência digital que envolve o potencial de difusão da Web Social enquanto nuvem rizomática, a fruição participativa dos utilizadores enquanto agentes de difusão, a sistematização dos conteúdos difundidos através da transtextualidade videomusical. O trabalho de investigação foi operacionalizado através de uma triangulação de métodos que se enquadram num desenho qualitativo de investigação. O objetivo dos dois primeiros métodos (aplicação da teoria fundamentada em dados ao método etnográfico) consiste na elaboração de um modelo de análise da convergência e de um modelo conceptual da difusão dos vídeos musicais na Web Social; o do terceiro (casos de estudo) a afinação e demonstração da aplicabilidade dos referidos modelos. O corpus epistémico da investigação consiste na fruição participativa da comunidade de fãs Antville de junho de 2006 a junho de 2011.

The player and video game interplay in the gameplay experience construct

Among the many discussions and studies related to video games, one of the most recurrent, widely debated and important relates to the experience of playing video games. The gameplay experience – as appropriated in this study – is the result of the interplay between two essential elements: a video game and a player. Existing studies have explored the resulting experience of video game playing from the perspective of the video game or the player, but none appear to equally balance both of these elements. The study presented here contributes to the ongoing debate with a gameplay experience model. The proposed model, which looks to equally balance the video game and the player elements, considers the gameplay experience to be both an interactive experience (related to the process of playing the video game) and an emotional experience (related to the outcome of playing the video game). The mutual influence of these two experiences during video game play ultimately defines the gameplay experience. To this gameplay experience contributes several dimensions, related to both the video game and player: the video game includes a mechanics, interface and narrative dimension; the player includes a motivations, expectations and background dimension. Also, the gameplay experience is initially defined by a gameplay situation, conditioned by an ambient in which gameplay takes place and a platform on which the video game is played. In order to initially validate the proposed model and attempt to show a relationship among the multiple model dimensions, a multi-case study was carried out using two different video games and player samples. In one study, results show significant correlations between multiple model dimensions, and evidence that video game related changes influence player motivations as well as player visual behavior. In specific player related analysis, results show that while players may be different in terms of background and expectations regarding the game, their motivation to play are not necessarily different, even if their performance in the game is weak. While further validation is necessary, this model not only contributes to the gameplay experience debate, but also demonstrates in a given context how player and video game dimensions evolve during video game play.

O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.

Padrões territoriais das dificuldades manifestadas pela população com 65 ou mais anos

Objetivos: Numa sociedade caracterizada pelo envelhecimento populacional é de suma importância a identificação de padrões territoriais que permitam o desenho de políticas de bem-estar mais adequadas para cada território. Para tal, é necessário analisar a heterogeneidade da perceção das dificuldades nas diversas regiões. Este estudo pretende analisar as dificuldades das pessoas com 65 ou mais anos com vista a encontrar algumas diferenças territoriais com base no grupo etário, no tipo e grau de dificuldade, nos rendimentos e nas habilitações. Metodologia: Trata-se de um estudo exploratório que analisa as dificuldades percecionadas pelas pessoas com 65 ou mais anos, tendo por base os dados disponibilizados pelo INE sobre o recenseamento populacional de 2011. Recorre-se à análise multivariada (análise fatorial de componentes principais e análise de clusters) e à análise bivariada de forma a obter os resultados da investigação. Resultados: Os principais resultados apontam para: i) existência de diferenças quanto à distribuição no território da perceção das dificuldades; ii) a perceção das dificuldades, da incapacidade e da dimensão das dificuldades por parte do grupo etário dos 65 ou mais anos segue um padrão territorial distinto da população em geral; iii) a perceção das dificuldades e a perceção da incapacidade no grupo etário dos 65 ou mais anos apresentam uma mancha no território diferente do padrão do envelhecimento; iv) a incapacidade auditiva e a incapacidade visual embora com um padrão territorial diferente, agregam no mesmo fator a população geral e o grupo etário dos 65 ou mais anos; v) do ponto de vista territorial é possível distinguir cinco clusters quanto à perceção das dificuldades da população portuguesa; vi) os rendimentos e as habilitações contribuem para a diferenciação dos clusters identificados. Discussão: Os resultados apresentados apoiam a necessidade de reflexão e de pesquisa no âmbito do mapeamento das dificuldades, na medida em que são um importante mecanismo de conhecimento da realidade intra-regional, permitindo a tomada de decisão.