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.

Avaliação do ciclo de vida de um pavimento flutuante de cortiça

A consciencialização ambiental vem assumindo um papel preponderante na construção civil. Nesse sentido, o desenvolvimento de materiais sustentáveis e ecológicos é essencial para a satisfação de fabricantes e consumidores, respeitando diversos requisitos: níveis reduzidos de poluição e toxicidade, durabilidade dos materiais, possibilidade de reutilização e/ou reciclagem, a proveniência das matérias-primas e a possibilidade de contaminação do ar no interior dos edifícios. As declarações ambientais de produto (DAP) permitem informar o consumidor do desempenho ambiental dos materiais dos produtos. Assim, ao longo de todo o processo de fabrico são registados os consumos de recursos e emissões ambientais e, através da metodologia de avaliação de ciclo de vida, é quantificada a contribuição resultante para impactes ambientais. Esta dissertação visa analisar os possíveis impactes ambientais no decurso do processo de produção de um pavimento flutuante de cortiça, constituído por cortiça, High Density Fibreboard (HDF) e acabamento de superfície, denominado Artcomfort Floating NPC e elaborar de um relatório de suporte, que servirá de base para a DAP do pavimento Artcomfort Floating NPC do sistema do Institut Bauen und Umwelt (IBU). Esta dissertação inclui um relatório de fundo, para a avaliação do ciclo de vida do pavimento flutuante Artcomfort Floating NPC da empresa Amorim Revestimentos, que servirá de base para a elaboração da declaração ambiental de produto (DAP) do mesmo. Para tal, recorreu-se ao software SimaPro para análise dos impactes ambientais das várias fases do processo de fabrico do pavimento em estudo, sendo as fases consideradas, a produção da camada base de cortiça aglomerada, camada backing de cortiça aglomerada, montagem da sanduiche, placa pintada, placa acabada e corte e embalagem. A fase que tem maior contribuição para os impactes ambientais do processo de fabrico do produto, em todas as categorias de impacte analisadas, com exceção da depleção dos recursos abióticos sem combustíveis fósseis, foi a fase de montagem da sanduiche.