京都大学 / 新制・課程博士 / 博士(情報学) / 甲第23546号 / 情博第776号 / 新制||情||132(附属図書館) / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 山下 信雄, 教授 太田 快人, 教授 永持 仁 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

CPU cache hierarchies are the central solution in bridging the memory wall. A proper understanding of how to trade-off their high cost against performance can lead to cost-savings without sacrificing performance.Due to the combinatorial nature of the problem, there exist a large number of configurations to investigate, making design space exploration slow and cumbersome. To improve this process, this Thesis develops and evaluates a model for optimally trading-off cost and performance of CPU cache hierarchies, named the Optimal Cache Problem (OCP), in the form of a Non-linear Integer Problem. A second goal of this work is the development of an efficient solver for the OCP, which was found to be a branch & bound algorithm and proven to function correctly. Experiments were conducted to empirically analyse and validate the model and to showcase possible use-cases. There, it was possible to ascribe the model outputs on measurable performance metrics. The model succeeded in formalising the inherent trade-off between cost and performance in a way that allows for an efficient and complete search of the configuration space of possible cache hierarchies. In future work, the model needs to be refined and extended to allow for the simultaneous analysis of multiple programs.

The time/cost trade-off models in project management aim to compress the project completion time by accelerating the activity durations at an expense of additional resources. The budget problem in discrete time/cost trade-off scheduling selects the time/cost mode -among the discrete set of specified modes- for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally, however each solution may have a different total cost value. In this study we aim to find the minimum cost solution among the optimal solutions of the budget problem. We analyze the structure of the problem together with its linear programming relaxation and derive some mechanisms for reducing the problem size. We solve the reduced problem by linear programming relaxation and branch and bound based approximation and optimization algorithms. We find that our branch and bound algorithm finds optimal solutions for medium-sized problem instances in reasonable times and the approximation algorithms produce high quality solutions. We also discuss the way our algorithms could be used to construct the time/cost trade-off curve.

Resource Leveling Problem (RLP) aims to minimize undesired fluctuations in resource distribution curves which cause several practical problems. Many studies conclude that commercial project management software packages can not effectively deal with RLP. In this study a branch and bound algorithm is presented for solving RLP for single and multi resource, small size networks. The algorithm adopts a depth-first strategy and stores start times of non-critical activities in the nodes of the search tree. Optimal resource distributions for 4 different types of resource leveling metrics can be obtained via the developed procedure. To prune more of the search tree and thereby reduce the computation time, several lower bound calculation methods are employed. Experiment results from 20 problems showed that the suggested algorithm can successfully locate optimal solutions for networks with up to 20 activities. The algorithm presented in this study contributes to the literature in two points. First, the new lower bound improvement method (maximum allowable daily resources method) introduced in this study reduces computation time required for achieving the optimal solution for the RLP. Second, optimal solutions of several small sized problems have been obtained by the algorithm for some traditional and recently suggested leveling metrics. Among these metrics, Resource Idle Day (RID) has been utilized in an exact method for the first time. All these solutions may form a basis for performance evaluation of heuristic and metaheuristic procedures for the RLP. Limitations of the developed branch and bound procedure are discussed and possible further improvements are suggested.

Made available in DSpace on 2016-06-02T19:50:17Z (GMT). No. of bitstreams: 1 TeseLKO.pdf: 834201 bytes, checksum: 994d7b70c6b1001f9dec962fafc8b72e (MD5) Previous issue date: 2004-12-13 / Universidade Federal de Sao Carlos / The purpose of this work is to develop exact methods, based on Lagrangean and Surrogate relaxation, with good performance to solve the manufacturer s pallet loading problem. This problem consists of orthogonally arranging the maximum number of rectangles of sizes (l,w) and (w,l) into a larger rectangle (L,W) without overlapping. Such methods involve a tree search procedure of branch and bound type and they use, in each node of the branch and bound tree, bounds derived from Lagrangean and/or Surrogate relaxations of a 0-1 linear programming formulation. Subgradient optimization algorithms are used to optimize such bounds. Problem reduction tests and Lagrangean and Surrogate heuristics are also applied in the subgradient optimization to obtain good feasible solution. Computational experiments were performed with instances from the literature and also real instances obtained from a carrier. The results show that the methods are able to solve these instances, on average, more quickly than other exact methods, including the software GAMS/CPLEX. / O objetivo deste trabalho é desenvolver métodos exatos, baseados em relaxação Lagrangiana e Surrogate, com bom desempenho para resolver o problema de carregamento de paletes do produtor. Tal problema consiste em arranjar ortogonalmente e sem sobreposição o máximo número de retângulos de dimensões ( , ) l w ou ( , ) w l sobre um retângulo maior ( , ) L W . Tais métodos exatos são procedimentos de busca em árvore do tipo branch and bound que, em cada nó, utilizam limitantes derivados de relaxações Lagrangiana e/ou Surrogate de uma formulação de programação linear 0 1 − . Algoritmos de otimização do subgradiente são usados para otimizar estes limitantes. São aplicados ainda testes de redução do problema e heurísticas Lagrangiana e Surrogate na otimização do subgradiente para obter boas soluções factíveis. Testes computacionais foram realizados utilizando exemplos da literatura e exemplos reais, obtidos de uma transportadora. Os resultados mostram que os métodos são capazes de resolvê-los, em média, mais rapidamente do que outros métodos exatos, incluindo o software GAMS/CPLEX.

Orientador: Francisco de Assis Magalhães Gomes Neto / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T19:03:25Z (GMT). No. of bitstreams: 1 Villela_PedroFerraz_D.pdf: 10794575 bytes, checksum: 746b8aebf0db423d557d9c5fe1446592 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, propomos um método exato para obter o conjunto solução de um problema biobjetivo quadrático de otimização de carteiras de investimento, que envolve variáveis binárias. Nosso algoritmo é baseado na junção de três algoritmos específicos. O primeiro encontra uma curva associada ao conjunto solução de problemas biobjetivo contínuos por meio de um método de restrições ativas, o segundo encontra o ótimo de um problema de programação quadrática inteira mista pelo método Branch-and-Bound, e o terceiro encontra a interseção de duas curvas associadas a problemas biobjetivo distintos. Ao longo do texto, algumas heurísticas e métodos adicionais também são introduzidos, com o propósito de acelerar a convergência do algoritmo proposto. Além disso, o nosso método pode ser visto como uma nova contribuição na área, pois ele determina, de forma exata, a curva associada ao conjunto solução do problemas biobjetivo inteiro misto, algo que é incomum na literatura, pois o problema alvo geralmente é abordado via métodos meta-heurísticos. Ademais, ele mostrou ser eficiente do ponto de vista do tempo computacional, pois encontra o conjunto solução do problema em poucos segundos / Abstract: In this work, we propose an exact method to find the solution set of a mixed quadratic bi-objective portfolio optimization problem. Our method is based on the combination of three specific algorithms. The first one obtains a curve associated with the solution set of a continuous bi-objective problem through an active set algorithm, the second one solves a mixed quadratic optimization problem through the Branch-and-Bound method, and the third one searches the intersection of two curves associated with distinct bi-objective problems. Throughout the text, some heuristics are also introduced in order to accelerate the performance of the method. Moreover, our method can be seen as a new contribution to the field, since it finds, in an exact way, the curve related to the solution set of the mixed integer bi-objective problem, something uncommon in the corresponding literature, where the target problem is usually approached by metaheuristic methods. Additionally, it has also shown to be efficient in terms of running time, being capable of finding the problem's solution set within a much faster time frame / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Basés sur les outils théoriques et algorithmiques de la programmation DC et DCA, les travaux de recherche dans cette thèse portent sur les approches locales et globales pour l'optimisation non convexe et l'optimisation globale en variables mixtes entières. La thèse comporte 5 chapitres. Le premier chapitre présente les fondements de la programmation DC et DCA, et techniques de Séparation et Evaluation (B&B) (utilisant la technique de relaxation DC pour le calcul des bornes inférieures de la valeur optimale) pour l'optimisation globale. Y figure aussi des résultats concernant la pénalisation exacte pour la programmation en variables mixtes entières. Le deuxième chapitre est consacré au développement d'une méthode DCA pour la résolution d'une classe NP-difficile des programmes non convexes non linéaires en variables mixtes entières. Ces problèmes d'optimisation non convexe sont tout d'abord reformulées comme des programmes DC via les techniques de pénalisation en programmation DC de manière que les programmes DC résultants soient efficacement résolus par DCA et B&B bien adaptés. Comme première application en optimisation financière, nous avons modélisé le problème de gestion de portefeuille sous le coût de transaction concave et appliqué DCA et B&B à sa résolution. Dans le chapitre suivant nous étudions la modélisation du problème de minimisation du coût de transaction non convexe discontinu en gestion de portefeuille sous deux formes : la première est un programme DC obtenu en approximant la fonction objectif du problème original par une fonction DC polyèdrale et la deuxième est un programme DC mixte 0-1 équivalent. Et nous présentons DCA, B&B, et l'algorithme combiné DCA-B&B pour leur résolution. Le chapitre 4 étudie la résolution exacte du problème multi-objectif en variables mixtes binaires et présente deux applications concrètes de la méthode proposée. Nous nous intéressons dans le dernier chapitre à ces deux problématiques challenging : le problème de moindres carrés linéaires en variables entières bornées et celui de factorisation en matrices non négatives (Nonnegative Matrix Factorization (NMF)). La méthode NMF est particulièrement importante de par ses nombreuses et diverses applications tandis que les applications importantes du premier se trouvent en télécommunication. Les simulations numériques montrent la robustesse, rapidité (donc scalabilité), performance et la globalité de DCA par rapport aux méthodes existantes. / Based on theoretical and algorithmic tools of DC programming and DCA, the research in this thesis focus on the local and global approaches for non convex optimization and global mixed integer optimization. The thesis consists of 5 chapters. The first chapter presents fundamentals of DC programming and DCA, and techniques of Branch and Bound method (B&B) for global optimization (using the DC relaxation technique for calculating lower bounds of the optimal value). It shall include results concerning the exact penalty technique in mixed integer programming. The second chapter is devoted of a DCA method for solving a class of NP-hard nonconvex nonlinear mixed integer programs. These nonconvex problems are firstly reformulated as DC programs via penalty techniques in DC programming so that the resulting DC programs are effectively solved by DCA and B&B well adapted. As a first application in financial optimization, we modeled the problem pf portfolio selection under concave transaction costs and applied DCA and B&B to its solutions. In the next chapter we study the modeling of the problem of minimization of nonconvex discontinuous transaction costs in portfolio selection in two forms: the first is a DC program obtained by approximating the objective function of the original problem by a DC polyhedral function and the second is an equivalent mixed 0-1 DC program. And we present DCA, B&B algorithm, and a combined DCA-B&B algorithm for their solutions. Chapter 4 studied the exact solution for the multi-objective mixed zero-one linear programming problem and presents two practical applications of proposed method. We are interested int the last chapter two challenging problems: the linear integer least squares problem and the Nonnegative Mattrix Factorization problem (NMF). The NMF method is particularly important because of its many various applications of the first are in telecommunications. The numerical simulations show the robustness, speed (thus scalability), performance, and the globality of DCA in comparison to existent methods.