To optimize the beam angle and fluence map in Intensity Modulated Radiation Therapy (IMRT) planning, we apply Benders decomposition as well as develop a two-stage integer programming-based heuristic. Benders decomposition is first implemented in the traditional manner by iteratively solving the restricted master problem, and then identifying and adding the violated Benders cut. We also implemented Benders decomposition using the “lazy constraint” feature included in CPLEX. In contrast, our two-stage heuristic first seeks to find a good solution by iteratively eliminating the least used angles in the linear programming relaxation solution until the size of the formulation is manageable. In the second stage of the heuristic, the solution is improved by applying local branching. The various methods were tested on real patient data in order to investigate their effectiveness and runtime characteristics. The results indicated that implementing Benders using the lazy constraint usually led to better feasible solutions than the traditional approach. Moreover, the LP rounding heuristic was seen to generate high-quality solutions within a short amount of time, with further improvement obtained with the local branching search. / text

O planejamento da produção é uma atividade que avalia decisões para um melhor uso dos recursos disponíveis, visando satisfazer aos objetivos produtivos da empresa ao longo de um horizonte de planejamento. Este trabalho enfoca o problema de dimensionamento de lotes com restrições de capacidade (PDLC), que é uma das tarefas centrais envolvidas no planejamento da produção. O PDLC visa determinar o tamanho dos lotes a serem produzidos em períodos de tempo de um horizonte de planejamento. Os PDLC estudados neste trabalho contemplam duas características importantes: a presença de múltiplos itens e a existência de tempos de preparação para as máquinas. Além disso, são consideradas restrições de capacidade e situações onde o atraso para atender a demanda é permitido (backlogging). Alguns dos modelos estudados permitem que a preparação do ambiente de produção para um dado item possa ser mantida de um período para o seguinte, o que propiciaria a economia de até uma preparação a cada período. Esta característica é chamada de preservação de preparação (carry-over). Também existem situações onde a preparação de uma máquina começa em um período e termina no período seguinte. Na literatura, esta característica é chamada de set-up crossover. Este trabalho tem três metas centrais: a) avaliar diferentes configurações do software comercial ILOG CPLEX 11 para a solução dos PDLC estudados; b) estudar a influência na solução dos PDLC quando se acrescenta a possibilidade de atraso na demanda, de preservação de preparação e de set-up crossover; c) aplicar local branching para resolver os problemas estudados. Para resolver as instâncias propostas, foram utilizados o software comercial ILOG CPLEX 11 e um programa em C++ que foi desenvolvido neste trabalho. Foram utilizados exemplos encontrados na literatura para avaliar as propostas, e bons resultados foram obtidos / The production planning is an activity that evaluates the decision for a better use of the available resources, in order to satisfy the productive objectives of the company over a planning horizon. This work focuses on the capacitated lot-sizing problem (CLSP), which is one of the central tasks involved in production planning. The CLSP means to determine the size of the lots to be produced in time periods of a planning horizon. The CLSP studied in this work contemplate two complicating characteristics: the presence of multiple items and the existence of set-up times for the machines. Besides that, capacity constraints and situations where backlog of the demand is allowed are also considered (backlogging). Some of the studied models allow the set-up of the production environment for a given item to be carried over to the next period, which could result in economy of a set-up in each period (carry-over). There are situations where the set-up of a machine starts in one period and crosses over to the next period (set-up crossover). This work has three main goals: a) evaluate different configurations of the commercial software ILOG CPLEX 11 to solve the different kinds of CLSP studied; b) study the influence of the solution of the CLSP when you consider the possibility of backlogging, set-up carry-over and set-up crossover; c) apply local branching to solve the studied problems. To solve the proposed instances, we used the commercial solver ILOG CPLEX 11 and the program in C++ developed in this work. The examples used to test both programs are found in the literature, and good results were obtained

O planejamento da produção é uma atividade que avalia decisões para um melhor uso dos recursos disponíveis, visando satisfazer aos objetivos produtivos da empresa ao longo de um horizonte de planejamento. Este trabalho enfoca o problema de dimensionamento de lotes com restrições de capacidade (PDLC), que é uma das tarefas centrais envolvidas no planejamento da produção. O PDLC visa determinar o tamanho dos lotes a serem produzidos em períodos de tempo de um horizonte de planejamento. Os PDLC estudados neste trabalho contemplam duas características importantes: a presença de múltiplos itens e a existência de tempos de preparação para as máquinas. Além disso, são consideradas restrições de capacidade e situações onde o atraso para atender a demanda é permitido (backlogging). Alguns dos modelos estudados permitem que a preparação do ambiente de produção para um dado item possa ser mantida de um período para o seguinte, o que propiciaria a economia de até uma preparação a cada período. Esta característica é chamada de preservação de preparação (carry-over). Também existem situações onde a preparação de uma máquina começa em um período e termina no período seguinte. Na literatura, esta característica é chamada de set-up crossover. Este trabalho tem três metas centrais: a) avaliar diferentes configurações do software comercial ILOG CPLEX 11 para a solução dos PDLC estudados; b) estudar a influência na solução dos PDLC quando se acrescenta a possibilidade de atraso na demanda, de preservação de preparação e de set-up crossover; c) aplicar local branching para resolver os problemas estudados. Para resolver as instâncias propostas, foram utilizados o software comercial ILOG CPLEX 11 e um programa em C++ que foi desenvolvido neste trabalho. Foram utilizados exemplos encontrados na literatura para avaliar as propostas, e bons resultados foram obtidos / The production planning is an activity that evaluates the decision for a better use of the available resources, in order to satisfy the productive objectives of the company over a planning horizon. This work focuses on the capacitated lot-sizing problem (CLSP), which is one of the central tasks involved in production planning. The CLSP means to determine the size of the lots to be produced in time periods of a planning horizon. The CLSP studied in this work contemplate two complicating characteristics: the presence of multiple items and the existence of set-up times for the machines. Besides that, capacity constraints and situations where backlog of the demand is allowed are also considered (backlogging). Some of the studied models allow the set-up of the production environment for a given item to be carried over to the next period, which could result in economy of a set-up in each period (carry-over). There are situations where the set-up of a machine starts in one period and crosses over to the next period (set-up crossover). This work has three main goals: a) evaluate different configurations of the commercial software ILOG CPLEX 11 to solve the different kinds of CLSP studied; b) study the influence of the solution of the CLSP when you consider the possibility of backlogging, set-up carry-over and set-up crossover; c) apply local branching to solve the studied problems. To solve the proposed instances, we used the commercial solver ILOG CPLEX 11 and the program in C++ developed in this work. The examples used to test both programs are found in the literature, and good results were obtained

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T14:02:44Z (GMT). No. of bitstreams: 1 Santos_RafaelFranciscodos_M.pdf: 909075 bytes, checksum: b4d466696cb4f640a50eca288dfccd5c (MD5) Previous issue date: 2006 / Resumo: Nesta dissertação propomos um uso mais geral dos Cortes Canônicos (CCs) introduzidos por Balas e Jeroslow ([2]) no método de Ramificação Local (RamLoc) de Fischetti e Lodi ([6]). A ramificação local é uma heurística de propósito geral para Programação Inteira Mista (MIP) que explora vizinhanças definidas através da adição de inequações lineares ao modelo original. Estas inequações determinam subproblemas que são computados mais rapidamente pelos resolvedores de MIP. Uma análise da execução da RamLoc indicou que, em algumas situações, ela acrescenta cortes de ramificação local muito superficiais (i.e.,que descartam poucas soluções) e que estes cortes ocorrem com grande freqüência. Como os cortes de ramificações locais de Fischetti e Lodi são casos especiais dos CCs para programação inteira 0?1, n'os propomos a incorporação de CCs mais profundos (i.e.,que descartam mais soluções) à RamLoc. Executamos o algoritmo resultante sobre 25 das 29 instâncias testadas em [6] e obtivemos melhores resultados do aqueles alcançado pela RamLoc original e pelo resolvedor comercial de MIP XPRESS com seus parâmetros default. Uma outra investigação que empreendemos foi a inclusão dos CCs na heurística para modelos gerais de programação inteira mista RINS ([3]). Esta heurística surgiu durante o desenvolvimento desta dissertação e apresentou um bom desempenho. Realizamos alguns testes com as mesmas instâncias sobre as quais a RamLoc foi executada e obtivemos resultados promissores. Por fim, além da utilização dos CCs em heurísticas, criamos uma estratégia de ramificação que pode ser embutida nos algoritmos de branch-and-cut dos resolvedores de MIP. Denominamos esta estratégia de dive branching e a implementamos no resolvedor XPRESS. Em experimentos conduzidos com o mesmo conjunto de instâncias anteriores, obtivemos resultados de melhor qualidade do que aqueles produzidos pelo XPRESS com seus parâmetros default / Abstract: In this dissertation we propose a broader usage of the Canonical Cuts (CC) introduced by Balas and Jeroslow ([2]) in the Local Branching method (LB) of Fischetti and Lodi ([6]). The LB is a general purpose heuristic for Mixed Integer Programming (MIP) that explores neighborhoods defined by the addition of linear inequalities to the original model. These inequalities determine subproblems that are computed more quickly by MIP solvers. An analysis of the execution of LB indicated that, in some situations, it adds local branching cuts that are too superficial (i.e., chopping off few solutions) and that these cuts happen very often. Since the local branching cuts of Fischetti and Lodi are special cases of CCs for 0?1 integer programming, we propose to incorporate deeper CCs (i.e, chopping of more solutions) to LB. We executed the resulting algorithm on 25 out of the 29 instances tested in [6] and we obtained better results than those attained by the original LB and by the XPRESS commercial MIP solver under default settings. Another research that we carried out was the inclusion of CC to the RINS heuristics for general mixed integer programs ([3]). This heuristic appeared during the development of this dissertation and showed a good performance. We carried out some tests with the same instances on which LB was tested and the results are promising. Finally, besides using the CCs in heuristics, we created a branching strategy that can be embedded to the branch-and-cut algorithms of the MIP solvers. We called it dive branching and implemented it in the XPRESS solver. In experiments with the same set of instances as before, we obtained results of better quality than those produced by XPRESS with default settings / Mestrado / Mestre em Ciência da Computação

Cette thèse se situe à l’intersection de deux domaines de recherche scientifique la Reconnaissance d’Objets Structurels (ROS) et la Recherche Opérationnelle (RO). Le premier consiste à rendre la machine plus intelligente et à reconnaître les objets, en particulier ceux basés sur les graphes. Alors que le second se focalise sur la résolution de problèmes d’optimisation combinatoire difficiles. L’idée principale de cette thèse est de combiner les connaissances de ces deux domaines. Parmi les problèmes difficiles existants en ROS, le problème de la distance d’édition entre graphes (DEG) a été sélectionné comme le cœur de ce travail. Les contributions portent sur la conception de méthodes adoptées du domaine RO pour la résolution du problème de DEG. Explicitement, des nouveaux modèles linéaires en nombre entiers et des matheuristiques ont été développé à cet effet et de très bons résultats ont été obtenus par rapport à des approches existantes. / This thesis is focused on Graph Matching (GM) problems and in particular the Graph Edit Distance (GED) problems. There is a growing interest in these problems due to their numerous applications in different research domains, e.g. biology, chemistry, computer vision, etc. However, these problems are known to be complex and hard to solve, as the GED is a NP-hard problem. The main objectives sought in this thesis, are to develop methods for solving GED problems to optimality and/or heuristically. Operations Research (OR) field offers a wide range of exact and heuristic algorithms that have accomplished very good results when solving optimization problems. So, basically all the contributions presented in thesis are methods inspired from OR field. The exact methods are designed based on deep analysis and understanding of the problem, and are presented as Mixed Integer Linear Program (MILP) formulations. The proposed heuristic approaches are adapted versions of existing MILP-based heuristics (also known as matheuristics), by considering problem-dependent information to improve their performances and accuracy.