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.

Contributions to the theory of maximum entropy estimation for ill-posed models

As técnicas estatísticas são fundamentais em ciência e a análise de regressão linear é, quiçá, uma das metodologias mais usadas. É bem conhecido da literatura que, sob determinadas condições, a regressão linear é uma ferramenta estatística poderosíssima. Infelizmente, na prática, algumas dessas condições raramente são satisfeitas e os modelos de regressão tornam-se mal-postos, inviabilizando, assim, a aplicação dos tradicionais métodos de estimação. Este trabalho apresenta algumas contribuições para a teoria de máxima entropia na estimação de modelos mal-postos, em particular na estimação de modelos de regressão linear com pequenas amostras, afetados por colinearidade e outliers. A investigação é desenvolvida em três vertentes, nomeadamente na estimação de eficiência técnica com fronteiras de produção condicionadas a estados contingentes, na estimação do parâmetro ridge em regressão ridge e, por último, em novos desenvolvimentos na estimação com máxima entropia. Na estimação de eficiência técnica com fronteiras de produção condicionadas a estados contingentes, o trabalho desenvolvido evidencia um melhor desempenho dos estimadores de máxima entropia em relação ao estimador de máxima verosimilhança. Este bom desempenho é notório em modelos com poucas observações por estado e em modelos com um grande número de estados, os quais são comummente afetados por colinearidade. Espera-se que a utilização de estimadores de máxima entropia contribua para o tão desejado aumento de trabalho empírico com estas fronteiras de produção. Em regressão ridge o maior desafio é a estimação do parâmetro ridge. Embora existam inúmeros procedimentos disponíveis na literatura, a verdade é que não existe nenhum que supere todos os outros. Neste trabalho é proposto um novo estimador do parâmetro ridge, que combina a análise do traço ridge e a estimação com máxima entropia. Os resultados obtidos nos estudos de simulação sugerem que este novo estimador é um dos melhores procedimentos existentes na literatura para a estimação do parâmetro ridge. O estimador de máxima entropia de Leuven é baseado no método dos mínimos quadrados, na entropia de Shannon e em conceitos da eletrodinâmica quântica. Este estimador suplanta a principal crítica apontada ao estimador de máxima entropia generalizada, uma vez que prescinde dos suportes para os parâmetros e erros do modelo de regressão. Neste trabalho são apresentadas novas contribuições para a teoria de máxima entropia na estimação de modelos mal-postos, tendo por base o estimador de máxima entropia de Leuven, a teoria da informação e a regressão robusta. Os estimadores desenvolvidos revelam um bom desempenho em modelos de regressão linear com pequenas amostras, afetados por colinearidade e outliers. Por último, são apresentados alguns códigos computacionais para estimação com máxima entropia, contribuindo, deste modo, para um aumento dos escassos recursos computacionais atualmente disponíveis.

Biovalorização de soro de queijo por processos anaeróbios/aeróbios

Este trabalho abordou a valorização de um subproduto da indústria de lacticínios (soro de queijo) através da alteração do funcionamento de processos habitualmente utilizados no contexto do tratamento biológico. Foi avaliada a fermentação acidogénica deste subproduto para maximizar a conversão do seu elevado teor de matéria orgânica em ácidos orgânicos voláteis (AOV) que actualmente são produtos com elevada procura, nomeadamente para produção de polihidroxialcanoatos (PHA). Em ensaios descontínuos e semi-contínuos foi caracterizada a produção e composição de AOV a partir de soro de queijo variando a razão food-to-microorganism (F/M) e a concentração de alcalinidade. Recorrendo à modelação dos resultados através de superfícies de resposta, demonstrou-se que condições de F/M = 4 gCQO g-1SSV combinadas com uma adição elevada de alcalinidade (8 g L-1 expresso como CaCO3) resultaram na conversão de 72% da CQO alimentada em AOV. O acetato e o butirato foram os AOV predominantes (60%), mas elevadas razões F/M combinadas com elevadas alcalinidades promoveram o alongamento da cadeia carboxílica, tendo sido produzidos AOV de maior massa molecular (iso-valerato e n-caproato). O processo de fermentação acidogénica foi posteriormente desenvolvido em modo contínuo num reactor MBBR acidogénico operado a longo prazo. Cargas orgânicas entre 30 e 50 gCQO L-1d-1 permitiram obter um grau de acidificação máximo de 68% no efluente fermentado. Foi ainda demonstrado que uma adição dinâmica de alcalinidade (0 – 4,8 g CaCO3 L-1) nestas condições estimulou a produção de AOV de cadeia ímpar (propionato e n-valerato) até 42%. O efluente acidificado no processo anaeróbio foi usado como substrato em reactores SBR operados para selecção de culturas microbianas mistas acumuladoras de PHA, nos quais foi aplicado um regime de alimentação dinâmica em condições aeróbias (“fartura-fome”). Estes sistemas operaram também a longo prazo, e demonstraram ser capazes de remover mais de 96% da CQO alimentada e simultaneamente convertê-la em PHA, até 36% do peso celular seco. A velocidade de remoção de substrato (valor máximo de 1,33 gCQO g-1SSV h-1) foi proporcional ao teor de polímero acumulado, evidenciando o estabelecimento de uma fase de “fome” prolongada que estimulou a selecção de microrganismos com elevada capacidade de acumulação de PHA. Além disso, o teor molar de hidroxivalerato (HV) no copolímero produzido [P(HB-co-HV)] foi directamente proporcional ao teor de AOV de cadeia ímpar (propionato e n-valerato) presente no soro fermentado que serviu de substrato. Uma estratégia de operação do reactor SBR com variação da carga orgânica, aliada ao regime “fartura-fome” estabelecido, permitiu ainda simular a realidade dos processos de tratamento biológico de efluentes, nos quais a composição e concentração inicial de matéria orgânica variam frequentemente. Este modo de operação do sistema estimulou notavelmente o processo de selecção de culturas acumuladoras de PHA tendo resultado num aumento da acumulação de PHA de 7% para 36%. Os resultados demonstraram com sucesso a possibilidade de valorização do soro de queijo através de eco-biotecnologia, contribuindo para uma mudança de paradigma no tratamento convencional de efluentes: ao invés de serem eliminados enquanto poluentes, os componentes orgânicos presentes neste subproduto industrial podem assim ser convertidos em materiais de valor acrescentado.