Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.

Performance analysis of 4G wireless networks using system level simulator

In the last decade, mobile wireless communications have witnessed an explosive growth in the user’s penetration rate and their widespread deployment around the globe. In particular, a research topic of particular relevance in telecommunications nowadays is related to the design and implementation of mobile communication systems of 4th generation (4G). 4G networks will be characterized by the support of multiple radio access technologies in a core network fully compliant with the Internet Protocol (all IP paradigms). Such networks will sustain the stringent quality of service (QoS) requirements and the expected high data rates from the type of multimedia applications (i.e. YouTube and Skype) to be available in the near future. Therefore, 4G wireless communications system will be of paramount importance on the development of the information society in the near future. As 4G wireless services will continue to increase, this will put more and more pressure on the spectrum availability. There is a worldwide recognition that methods of spectrum managements have reached their limit and are no longer optimal, therefore new paradigms must be sought. Studies show that most of the assigned spectrum is under-utilized, thus the problem in most cases is inefficient spectrum management rather spectrum shortage. There are currently trends towards a more liberalized approach of spectrum management, which are tightly linked to what is commonly termed as Cognitive Radio (CR). Furthermore, conventional deployment of 4G wireless systems (one BS in cell and mobile deploy around it) are known to have problems in providing fairness (users closer to the BS are more benefited relatively to the cell edge users) and in covering some zones affected by shadowing, therefore the use of relays has been proposed as a solution. To evaluate and analyse the performances of 4G wireless systems software tools are normally used. Software tools have become more and more mature in recent years and their need to provide a high level evaluation of proposed algorithms and protocols is now more important. The system level simulation (SLS) tools provide a fundamental and flexible way to test all the envisioned algorithms and protocols under realistic conditions, without the need to deal with the problems of live networks or reduced scope prototypes. Furthermore, the tools allow network designers a rapid collection of a wide range of performance metrics that are useful for the analysis and optimization of different algorithms. This dissertation proposes the design and implementation of conventional system level simulator (SLS), which afterwards enhances for the 4G wireless technologies namely cognitive Radios (IEEE802.22) and Relays (IEEE802.16j). SLS is then used for the analysis of proposed algorithms and protocols.

Implicit optimality criterion for convex SIP problem with box constrained index set

We consider a convex problem of Semi-Infinite Programming (SIP) with multidimensional index set. In study of this problem we apply the approach suggested in [20] for convex SIP problems with one-dimensional index sets and based on the notions of immobile indices and their immobility orders. For the problem under consideration we formulate optimality conditions that are explicit and have the form of criterion. We compare this criterion with other known optimality conditions for SIP and show its efficiency in the convex case.

Biotecnologia: concepção e validação de trabalhos práticos

É hoje geralmente aceite que a educação em ciências, além da aprendizagem de conhecimento conceptual e procedimental, deve promover nos alunos o desenvolvimento de competências investigativas, ou seja, competências para identificar, formular e resolver problemas. Porém, o desenvolvimento de actividades práticas de natureza investigativa é difícil, pela carência, ou mesmo ausência, de vivências dos professores em investigações, sobretudo em projectos aplicáveis nas práticas lectivas. A frequente falta de formação inicial e contínua dos professores de ciências, relativamente ao desenvolvimento de competências indispensáveis à implementação desta perspectiva de trabalho prático, constitui um obstáculo à concretização de inovações educativas preconizadas para a educação em ciências, referidas em documentos aprovados e publicados pelo Ministério da Educação, em particular, orientações curriculares e programas disciplinares. A abordagem de temáticas em biotecnologia configura-se como uma necessidade das sociedades actuais, de modo que, atendendo aos avanços que se têm vindo a verificar nesta área, deverá integrar-se em educação científica formal, relacionando-a com a vida quotidiana dos cidadãos. Além de componentes científicas inovadoras, os seus desenvolvimentos têm diversas implicações, designadamente éticas, políticas, económicas e sociais. A investigação apresentada nesta dissertação insere-se neste quadro, a qual se baseou no seguinte problema: “Partindo de temáticas em biotecnologia, como estimular o desenvolvimento de trabalho prático numa perspectiva investigativa por professores de Biologia e/ou Geologia?”. Definiram-se dois objectivos gerais: 1) testar, conceber e optimizar actividades laboratoriais e experimentais em biotecnologia, transponíveis para contextos educativos dos ensinos básico e secundário, desmistificando a complexidade associada ao trabalho prático nesta área; 2) conceber, implementar e avaliar uma acção de formação para professores de Biologia e/ou Geologia, na modalidade de Oficina de Formação, visando em contextos escolares e em temáticas de biotecnologia, desenvolver percursos investigativos. A acção de formação “Desenvolvimento de actividades práticas em biotecnologia numa perspectiva investigativa: um contributo na (re)orientação de ensino e aprendizagem de ciências” estimulou os professores-formandos a participarem activamente num programa que integrava abordagens inovadoras de trabalho prático, e criou condições para, com orientação e apoio, desenvolverem percursos investigativos a partir de situações-problema em temáticas de biotecnologia. Na generalidade, as reflexões dos professores-formandos sobre os percursos investigativos planeados e implementados, e os ganhos a nível profissional e/ou pessoal, além de referências elogiosas à estrutura e sequência das actividades propostas na formação, realçaram os seguintes aspectos positivos: a) o enriquecimento de conhecimentos científico-tecnológicos em biotecnologia; b) a oportunidade de reflexão sobre as suas práticas e a necessidade de uma nova forma de olhar para o trabalho laboratorial e experimental e para o seu papel nas aulas de ciências; c) as potencialidades de trabalho prático numa perspectiva investigativa em termos de mobilização de competências de natureza conceptual e processual; d) o desenvolvimento de competências técnicas e processuais necessárias à implementação de percursos investigativos com recurso a procedimentos em biotecnologia. Do presente estudo decorrem implicações educacionais que se esperam pertinentes para a formação de professores de ciências e elaboração de recursos didácticos, designadamente manuais escolares, assim como, para a gestão dos programas disciplinares. Este estudo permitiu, ainda, apresentar propostas para futuras investigações.

Optimization models for a short sea fuel oil distribution problem

O transporte marítimo e o principal meio de transporte de mercadorias em todo o mundo. Combustíveis e produtos petrolíferos representam grande parte das mercadorias transportadas por via marítima. Sendo Cabo Verde um arquipelago o transporte por mar desempenha um papel de grande relevância na economia do país. Consideramos o problema da distribuicao de combustíveis em Cabo Verde, onde uma companhia e responsavel por coordenar a distribuicao de produtos petrolíferos com a gestão dos respetivos níveis armazenados em cada porto, de modo a satisfazer a procura dos varios produtos. O objetivo consiste em determinar políticas de distribuicão de combustíveis que minimizam o custo total de distribuiçao (transporte e operacões) enquanto os n íveis de armazenamento sao mantidos nos n íveis desejados. Por conveniencia, de acordo com o planeamento temporal, o prob¬lema e divido em dois sub-problemas interligados. Um de curto prazo e outro de medio prazo. Para o problema de curto prazo sao discutidos modelos matemáticos de programacao inteira mista, que consideram simultaneamente uma medicao temporal cont ínua e uma discreta de modo a modelar multiplas janelas temporais e taxas de consumo que variam diariamente. Os modelos sao fortalecidos com a inclusão de desigualdades validas. O problema e então resolvido usando um "software" comercial. Para o problema de medio prazo sao inicialmente discutidos e comparados varios modelos de programacao inteira mista para um horizonte temporal curto assumindo agora uma taxa de consumo constante, e sao introduzidas novas desigualdades validas. Com base no modelo escolhido sao compara¬das estrategias heurísticas que combinam três heur ísticas bem conhecidas: "Rolling Horizon", "Feasibility Pump" e "Local Branching", de modo a gerar boas soluçoes admissíveis para planeamentos com horizontes temporais de varios meses. Finalmente, de modo a lidar com situaçoes imprevistas, mas impor¬tantes no transporte marítimo, como as mas condicões meteorológicas e congestionamento dos portos, apresentamos um modelo estocastico para um problema de curto prazo, onde os tempos de viagens e os tempos de espera nos portos sao aleatórios. O problema e formulado como um modelo em duas etapas, onde na primeira etapa sao tomadas as decisões relativas as rotas do navio e quantidades a carregar e descarregar e na segunda etapa (designada por sub-problema) sao consideradas as decisoes (com recurso) relativas ao escalonamento das operacões. O problema e resolvido por um metodo de decomposto que usa um algoritmo eficiente para separar as desigualdades violadas no sub-problema.