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.

Estudo da maquinabilidade das ligas Ti-6Al-4V e Co-28Cr-6Mo na fresagem de dispositivos biomédicos

Os estudos de maquinabilidade de biomateriais e outros materiais aplicados na área médica são extensos. Todavia, muitos destes estudos recorrem a modelos de geometria regular e operações elementares de maquinagem. Relativamente a estas, os estudos académicos atualmente disponíveis mostram que a tecnologia preferencial é o torneamento, opção que se fundamenta na simplicidade de análise (corte ortogonal). Saliente-se ainda que, neste contexto, a liga de titânio Ti-6Al-4V constitui o biomaterial mais utilizado. Numa perspetiva complementar, refira-se que as publicações científicas evidenciam que a informação disponível sobre a fresagem Ti-6Al-4V não é muito extensa e a do Co-28Cr-6Mo é quase inexistente. A presente dissertação enquadra-se neste domínio e representa mais uma contribuição para o estudo da maquinabilidade das ligas de Titânio e de crómio-cobalto. A aplicação de operações de maquinagem complexas, através do recurso a programas informáticos de fabrico assistido por computador (CAM), em geometrias complexas, como é o caso das próteses femorais anatómicas, e o estudo comparativo da maquinabilidade das ligas Co-28Cr-6Mo e Ti-6Al-4V, constituem os objetivos fundamentais deste trabalho de doutoramento. Neste trabalho aborda-se a problemática da maquinabilidade das ligas metálicas usadas nos implantes ortopédicos, nomeadamente as ligas de titânio, de crómiocobalto e os aços Inoxidáveis. Efetua-se ainda um estudo da maquinagem de uma prótese femoral com uma forma geométrica complexa, onde as operações de corte foram geradas recorrendo às tecnologias de fabrico assistido por computador (CAD/CAM). Posteriormente, procedeu-se ao estudo da maquinabilidade das duas ligas usadas neste trabalho, dando uma atenção particular à determinação das forças de corte para diferentes velocidades de corte. Para além da monitorização da evolução da força de corte, o desgaste das ferramentas, a dureza e a rugosidade foram avaliadas, em função da velocidade de corte imposta. Por fim, com base nas estratégias de maquinagem adotadas, analisa-se a maquinabilidade e selecionam-se os parâmetros de corte mais favoráveis para as ligas de Titânio e Crómio-cobalto. Os resultados obtidos mostram que a liga de crómio-cobalto induz maior valor de força de corte do que a liga de titânio. Observa-se um aumento progressivo das forças de corte quando a velocidade de corte aumenta, até atingir o valor máximo para a velocidade de corte de 80m/min, após a qual, a força de corte tende a diminuir. Apesar do fabricante das ferramentas recomendar a velocidade de corte de 50 m/min para ambos os materiais, conclui-se que a velocidade de corte de 65 m/min induz o mesmo desgaste na ferramenta de corte no caso da liga de titânio, e menor desgaste no caso da liga de crómio-cobalto.