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.

Dificuldades de síntese na escrita de alunos do ensino superior politécnico

O presente estudo teve como objectivo analisar o desempenho de alunos de primeiro ano dos cursos de Engenharia e de Ecoturismo da Escola Superior Agrária (ESAC) do Instituto Politécnico de Coimbra (IPC) no que respeita à realização de uma síntese da informação escrita a partir de várias fontes. O estudo compreendeu duas partes, constituídas em dois estudos de caso: no primeiro, realizado no ano lectivo de 2003/2004, participaram 123 alunos; no segundo, realizado no ano lectivo de 2006/2007, participaram 60 alunos, constituindo estes a totalidade de alunos de primeiro ano que estudaram a língua nacional sob as orientações do novo “Programa de Língua Portuguesa” vigente no Ensino Secundário a partir de 2003. Em ambos os estudos de caso, procurou-se conhecer o que pensavam os alunos sobre a sua relação com a escrita em contexto escolar e sobre os seus procedimentos e dificuldades relativos à selecção e síntese da informação. Foram analisados os seus procedimentos preliminares à produção de um texto a partir de várias fontes através de eventuais sublinhados, apontamentos e rascunhos e, em seguida, através do trabalho de revisão e qualidade do texto final, que pressupunha o domínio ao nível da explicitação do conhecimento. A análise comparativa a partir dos estudos e os resultados finais revelaram dificuldades de selecção, organização e conexão da informação, bem como dificuldades relativas a uma construção discursiva própria a partir da situação de comunicação proposta, tanto ao nível da superfície do texto quanto ao nível da sua estrutura profunda. Assim, considerando que os participantes no estudo apresentaram dificuldades ao nível da explicitação do conhecimento, considerando a pouca ou nenhuma abordagem do assunto no Ensino Secundário em Portugal, considerando ainda que, em contexto académico, a competência de escrita a partir de várias fontes com vista à explicitação do conhecimento é uma condição básica e necessária para uma escrita de transformação do conhecimento e consequente literacia crítica, torna-se imperativo reflectir sobre o problema para buscar soluções. A inclusão de uma disciplina no primeiro ano do Ensino Superior (cujos conteúdos básicos são aqui sugeridos) - que contemple o ensino explícito da escrita para o desenvolvimento das competências de explicitação e transformação do conhecimento - poderá ser uma interessante solução para promover a melhoria do desempenho escritural dos alunos na difícil transição do Ensino Secundário para o Superior, tornando-os mais auto-confiantes, afastando-os da prática do plágio e contribuindo para o seu sucesso escolar.

Problems of optimal transportation on the circle and their mechanical applications

We consider a mechanical problem concerning a 2D axisymmetric body moving forward on the plane and making slow turns of fixed magnitude about its axis of symmetry. The body moves through a medium of non-interacting particles at rest, and collisions of particles with the body's boundary are perfectly elastic (billiard-like). The body has a blunt nose: a line segment orthogonal to the symmetry axis. It is required to make small cavities with special shape on the nose so as to minimize its aerodynamic resistance. This problem of optimizing the shape of the cavities amounts to a special case of the optimal mass transfer problem on the circle with the transportation cost being the squared Euclidean distance. We find the exact solution for this problem when the amplitude of rotation is smaller than a fixed critical value, and give a numerical solution otherwise. As a by-product, we get explicit description of the solution for a class of optimal transfer problems on the circle.