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.

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.

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.

Contratos de autonomia nas escolas públicas : um estudo de caso múltiplo em duas organizações educativas portuguesas

A autonomia para as escolas públicas do Ensino Básico e Secundário em Portugal, prevista desde 1989, tem sido sistematicamente adiada enquanto a retórica do discurso político a vai alimentando, sem contudo, proceder à sua implementação. Em 2007, a coberto do DL n.º 115-A/98, de 4 de maio, avançou-se para a assinatura de 22 contratos de autonomia (CA) com escolas e agrupamentos pelo que, este trabalho de investigação se propõe avaliar alguns dos efeitos e resultados desta medida de política educativa. Este estudo no âmbito do doutoramento em Didática e Formação – Ramo Avaliação, comporta uma primeira avaliação exploratória ao desenvolvimento dos 22 CA a que se segue uma avaliação ao desenvolvimento do CA numa escola secundária e num agrupamento de escolas, numa abordagem de caso duplo. Neste projeto de investigação, construímos um dispositivo de avaliação com o qual procuramos identificar evidências dos efeitos da autonomia contratualizada. Na fase exploratória, analisando CA e as respostas a questionário enviado aos diretores com CA, efetuamos uma aproximação global à problemática. Na segunda fase, efetuamos entrevistas a dirigentes intermédios e de topo de uma Escola Secundária e de um Agrupamento de Escolas com CA e analisamos documentos. Com o referencial construído estabelecemos categorias de análise obtendo resultados que nos permitem compreender alguns efeitos da assinatura do CA ao nível das Organizações participantes. Os resultados obtidos indicam, o cumprimento dos objetivos da contratualização gerando-se novas dinâmicas. São notórias as diferenças no cumprimento de critérios, daí que a sustentabilidade da autonomia se perspetive diferente para cada Organização face a diferentes pontos de partida. Pode afirmar-se, face aos resultados, que os efeitos da contratualização são positivos e que esta contribuiu para a melhoria da qualidade na prestação do serviço público de educação. Contudo, existem debilidades no que diz respeito à intervenção dos parceiros educativos e a mecanismos de avaliação para que deixamos sugestões de melhoria no âmbito da continuação da autonomia contratualizada. Para futura investigação deixamos também sugestão de estudo de eventuais aprofundamentos da autonomia bem como da sua sustentabilidade.