Orientador: Márcio Ricardo Alves Gouveia / Resumo: O presente trabalho trata de conceitos relacionados com a medida generalizada de Hausdorff, onde o principal objetivo consiste na obtenção de conjuntos cuja dimensão seja um número positivo não inteiro. Ele começa com uma definição sobre as propriedades que uma função de conjunto deve satisfazer para ser considerada uma medida de Carathéodory, suas implicações e consequências. Após a explicação destes conceitos iniciais, dá-se alguns exemplos de funções de conjunto contínuas e monótonas com a apresentação da função de escala logarítmica, que é peça chave para o desenvolvimento de conjuntos de medidas positivas não inteiras, além da introdução da medida de Hausdorff com seus desdobramentos. Algumas hipóteses sobre funções côncavas são apresentadas juntamente com fórmulas deduzidas com bases nestas hipóteses e na concavidade da função. Utiliza-se a função de escala logarítima para a determinação da dimensão de vários conjuntos, inclusive o conjunto de Cantor. Posteriormente, há uma adaptação dos conceitos trabalhados para o tratamento de dimensões relacionadas à números diádicos irracionais. Por fim, os conceitos tratados sobre a reta real são estendidos para produtos cartesianos, com especial enfoque para conjuntos planares. / Abstract: The present work deals with concepts related to the generalized Hausdorff measure, where the main objective is to obtain sets whose dimension is a positive non integer number. It begins with a definition of the properties that a set function must satisfy to be considered a Carathéodory measure, their implications and consequences. Following the explanation of these initial concepts, some examples of continuous and monotonous set functions are given with the presentation of the logarithmic scale function, which is key to the development of non-integer positive measure sets, in addition to the introduction of the Hausdorff measure with its developments. Some assumptions about concave functions are presented together with formulas derived from these assumptions and the concavity of the function. The logarithmic scale function is used to determine the dimension of various sets, including the Cantor set. Later, there is an adaptation of the concepts worked for the treatment of dimensions related to irrational dyadic numbers. Finally, the concepts treated on the real line are extended to Cartesian products, with special focus on planar sets. / Mestre

[pt] O presente trabalho representa um estudo realizado sobre a gestão da produção e operações, tendo em vista o planejamento da produção de um conjunto de itens independentes num horizonte de curto prazo de uma empresa de varejo do setor eletrônico, via minimização de custos. O estudo iniciou-se a partir da necessidade de uma interface entre o setor de produção e o de vendas, e é focado na otimização da produção de luminárias da empresa Energia, a qual abastece o mercado de emissoras de televisão e produtores cinematográficos, em sua maioria. Para o planejamento, é necessário conhecer a série histórica da demanda dos itens dos últimos períodos. Porém, somente os dados históricos disponíveis – os dados de vendas dos itens - foram manipulados no software de previsão Forecast Pro, com o intuito de simular a previsão de demanda desses produtos no horizonte de planejamento de curto prazo. Em seguida, a modelagem matemática do problema de planejamento da produção desagregado – o modelo MPS para itens acabados - foi realizada a partir de entrevistas com responsáveis por setores distintos na empresa estudada. Por fim, utilizou-se o software de otimização AIMMS 3.10, capaz de solucionar problemas difíceis, para encontrar o plano ótimo de produção desagregado. Os resultados obtidos pelo software para o planejamento de curto prazo são as quantidades de luminárias a serem produzidas e estocadas em cada período, assim como decisões de produzir ou não em cada período. Esses resultados foram usados como base para analisar novos cenários, gerando informações suficientes para auxiliar a tomada de decisão por parte dos gerentes da empresa, como por exemplo, expandir os recursos produtivos. / [en] This work represents a study on the production and operations management, in order to plan the production of a set of independent items in a short-term horizon of a retail company of the electronics industry, by minimizing costs. As a necessity of understanding between sales and production the study is focused on optimizing production of lamps of the company Energia, which supplies to mostly the market for television and film producers. For planning, it is necessary to know the historical series of product demands of the items in recent past periods. However, the only available data – the product sales data -were handled in prediction Forecast Pro software to simulate the demand sales of the items for the short-term planning horizon. Then, the mathematical modeling of disaggregate production planning problem - the MPS model for finished items - was built, from interviews with managers of different sectors of the studied company. Finally, the optimization software AIMMS 3.10, capable of solving complex problems, was used to find the optimal production plan. The obtained results for short-term planning are the quantities of items to be produced and to be stocked in each period, as well as the decision to produce or not in each period. These results were used as the basis to analyze new scenarios, generating sufficient information to assist decision makers of the company, as for example, expand the productive resources.

[pt] Desde a sua origem, as abordagens a problemas de Otimização Combinatória polarizam-se entre métodos exatos e heurísticos. Recentemente, porém, estratégias que combinam ambos os métodos têm sido propostas para os mais variados problemas, apresentando resultados promissores. Nesse contexto, destacam-se os conceitos de vizinhaças de bola e elipsoidal, que realizam buscas em relação a uma ou mais soluções de referência. Este trabalho estuda a aplicação de tais vizinhanças para o Problema de Roteamento de Veículos com Restrição de Capacidade (CVRP), sobre o algoritmo de Branch-and-Cut-and-Price Robusto. Experimentos foram realizados e seus resultados analisados. / [en] Since its inception, approaches to Combinatorial Optimization were polarized between exact and heuristic methods. Recently, however, strategies that combine both methods have been proposed for various problems, showing promising results. In this context, the concepts of ball and ellipsoidal neighborhood appear, which perform a search regarding one or more reference solutions. This work studies the application of such neighborhoods for the Capacitated Vehicle Routing Problem (CVRP), using the Robust Branchand- Cut-and-Price algorithm. Experiments were made and its results were analyzed.

本論文研究股票分類與否對投資組合報酬有無差別，因此以目標規畫方式提出兩個混合整數線性規劃模型建立投資組合。在考量市場風險上，兩模型的差別在於一個是單股比重的限制，另一個是類股數目的限制。兩模型中均考慮交易數量為整數與實務中的交易成本，且採用了0-1決策變數，決定股票及類股的選取與否。並以台灣股票市場作為實證研究對象，探討兩模型投資組合在市場不同走勢下的表現，同時也觀察股票分類後，探討選幾個類股數會有較佳的績效，並分析投資組合建立後多久應該進行調整。 / This thesis studies the effect of return of a portfolio while restricting the number of asset category. Two mixed-integer linear programming models are proposed by using the goal programming technique. In consideration of the risk, the difference between these two models is that one focuses on a single stock restriction, and the other is on the asset category restriction. The integer restriction and transaction cost are included in the model while using binary decision variable to indicate the selection of an asset and the selection a category. Finally, an empirical study will be presented by applying to Taiwan’s stock market. The performances of these two models are discussed. Moreover, the best number of category in the portfolio and the best timing of rebalance are also investigated.

<p>The main topic of this thesis is integer quadratic programming with applications to problems arising in the areas of automatic control and communication. One of the most widespread modern control principles is the discrete-time method Model Predictive Control (MPC). The main advantage with MPC, compared to most other control principles, is that constraints on control signals and states can easily be handled. In each time step, MPC requires the solution of a Quadratic Programming (QP) problem. To be able to use MPC for large systems, and at high sampling rates, optimization routines tailored for MPC are used. In recent years, the range of application of MPC has been extended from constrained linear systems to so-called hybrid systems. Hybrid systems are systems where continuous dynamics interact with logic. When this extension is made, binary variables are introduced in the problem. As a consequence, the QP problem has to be replaced by a far more challenging Mixed Integer Quadratic Programming (MIQP) problem. Generally, for this type of optimization problems, the computational complexity is exponential in the number of binary optimization variables. In modern communication systems, multiple users share a so-called multi-access channel, where the information sent by different users is separated by using almost orthogonal codes. Since the codes are not completely orthogonal, the decoded information at the receiver is slightly correlated between different users. Further, noise is added during the transmission. To estimate the information originally sent, a maximum likelihood problem involving binary variables is solved. The process of simultaneously estimating the information sent by multiple users is called multiuser detection. In this thesis, the problem to efficiently solve MIQP problems originating from MPC is addressed. Two different algorithms are presented. First, a polynomial complexity preprocessing algorithm for binary quadratic programming problems is presented. By using the algorithm, some, or all, binary variables can be computed efficiently already in the preprocessing phase. In simulations, the algorithm is applied to unconstrained MPC problems with a mixture of real and binary control signals. It has also been applied to the multiuser detection problem, where simulations have shown that the bit error rate can be significantly reduced by using the proposed algorithm as compared to using common suboptimal algorithms. Second, an MIQP algorithm tailored for MPC is presented. The algorithm uses a branch and bound method where the relaxed node problems are solved by a dual active set QP algorithm. In this QP algorithm, the KKT-systems are solved using Riccati recursions in order to decrease the computational complexity. Simulation results show that both the QP solver and the MIQP solver proposed have lower computational complexity than corresponding generic solvers.</p> / Report code: LiU-TEK-LIC-2005:71.

<p>In this thesis we address the problem of optimal code generation for irregular architectures such as Digital Signal Processors (DSPs).</p><p>Code generation consists mainly of three interrelated optimization tasks: instruction selection (with resource allocation), instruction scheduling and register allocation. These tasks have been discovered to be NP-hard for most architectures and most situations. A common approach to code generation consists in solving each task separately, i.e. in a decoupled manner, which is easier from a software engineering point of view. Phase-decoupled compilers produce good code quality for regular architectures, but if applied to DSPs the resulting code is of significantly lower performance due to strong interdependences between the different tasks.</p><p>We developed a novel method for fully integrated code generation at the basic block level, based on dynamic programming. It handles the most important tasks of code generation in a single optimization step and produces an optimal code sequence. Our dynamic programming algorithm is applicable to small, yet not trivial problem instances with up to 50 instructions per basic block if data locality is not an issue, and up to 20 instructions if we take data locality with optimal scheduling of data transfers on irregular processor architectures into account. For larger problem instances we have developed heuristic relaxations.</p><p>In order to obtain a retargetable framework we developed a structured architecture specification language, xADML, which is based on XML. We implemented such a framework, called OPTIMIST that is parameterized by an xADML architecture specification.</p><p>The thesis further provides an Integer Linear Programming formulation of fully integrated optimal code generation for VLIW architectures with a homogeneous register file. Where it terminates successfully, the ILP-based optimizer mostly works faster than the dynamic programming approach; on the other hand, it fails for several larger examples where dynamic programming still provides a solution. Hence, the two approaches complement each other. In particular, we show how the dynamic programming approach can be used to precondition the ILP formulation.</p><p>As far as we know from the literature, this is for the first time that the main tasks of code generation are solved optimally in a single and fully integrated optimization step that additionally considers data placement in register sets and optimal scheduling of data transfers between different registers sets.</p>

This thesis presents a hybrid decision aid approach for supply networks redesign and planning int the context of multi-site enterprises. This approach is iterative and integrates a mixed integer programming model and a simulation model being at different decisional levels : the mathematical model is a strategic/tactical model and the simulation model is a tactical/operational model. These two models are based on the same modelling of the supply network. First, we describe the elements constituting the decision aid approach. We present two generic mixed integer programming models, multi-product, multi-echelon and multi-period, which search to maximize the profit of the multi-site enterprise. We propose a heuristic approach to solve one of these programs. We describe the developed simulation model. It reproduces the behaviour of the whole supply chain and takes into account the management policies. then, we present the adopted integration methodology. For a problem based on industrial cases, we show that the two models have their role in the decision aid approach and that they contribute both in the search of a good quality network design.

In this thesis we address the problem of optimal code generation for irregular architectures such as Digital Signal Processors (DSPs). Code generation consists mainly of three interrelated optimization tasks: instruction selection (with resource allocation), instruction scheduling and register allocation. These tasks have been discovered to be NP-hard for most architectures and most situations. A common approach to code generation consists in solving each task separately, i.e. in a decoupled manner, which is easier from a software engineering point of view. Phase-decoupled compilers produce good code quality for regular architectures, but if applied to DSPs the resulting code is of significantly lower performance due to strong interdependences between the different tasks. We developed a novel method for fully integrated code generation at the basic block level, based on dynamic programming. It handles the most important tasks of code generation in a single optimization step and produces an optimal code sequence. Our dynamic programming algorithm is applicable to small, yet not trivial problem instances with up to 50 instructions per basic block if data locality is not an issue, and up to 20 instructions if we take data locality with optimal scheduling of data transfers on irregular processor architectures into account. For larger problem instances we have developed heuristic relaxations. In order to obtain a retargetable framework we developed a structured architecture specification language, xADML, which is based on XML. We implemented such a framework, called OPTIMIST that is parameterized by an xADML architecture specification. The thesis further provides an Integer Linear Programming formulation of fully integrated optimal code generation for VLIW architectures with a homogeneous register file. Where it terminates successfully, the ILP-based optimizer mostly works faster than the dynamic programming approach; on the other hand, it fails for several larger examples where dynamic programming still provides a solution. Hence, the two approaches complement each other. In particular, we show how the dynamic programming approach can be used to precondition the ILP formulation. As far as we know from the literature, this is for the first time that the main tasks of code generation are solved optimally in a single and fully integrated optimization step that additionally considers data placement in register sets and optimal scheduling of data transfers between different registers sets.

The scope of this thesis is modelling and solving large-scale planning problems in the supply chain within the forest industry. Five research papers are included, the first three of which focus on the modelling, and the last two on the solution methods. All problems included are tactical multi-commodity problems expressed as mixed integer programming (MIP) models. The work has been done in collaboration with two Swedish companies within the forest industry. In Paper I, a problem concerning the supply chain of forest fuel for Sydved Energileveranser AB is modelled and solved. We study the problem of deciding when and where forest residues are to be converted into wood chips, and how the residues and chips are to be transported and stored in order to satisfy energy demand at heating plants. The company has long-term contracts with forest owners and saw mills. Decisions in the model include whether or not additional harvest areas and saw mills are to be contracted and which terminals to use. The planning horizon is one year and monthly time periods are used. Papers II--V are based on planning problems at Södra Cell AB. The planning horizon is normally one year. Papers II--III consider only one time period. In Paper II the supply chain from pulp mills to customers is modelled and the combined problem of deciding terminal locations and which ship routes to use is studied. Shipping vessels chartered on short or long term are used to transport products to terminals in Europe. From each terminal, the products are transported to customers by truck, train, or a combination of both. In addition, trains and trucks can be used for transports directly to customers from mills. In Paper III the entire supply chain, from harvest areas to customers, is considered. Decisions included are transportation of raw materials, production mix, the distribution of pulp products, and the selection of potential orders and their quantities at customers. The ship routes are considered as flow links. In Papers IV--V the problems in Papers II--III are combined into one model and several time periods are used. Lagrangian heuristics based on Lagrangian decomposition are used as solution methods in both papers. In Paper IV, the approach leads to subproblems for each time period, whereas in Paper V, another approach that results in subproblems for different parts of the supply chain is developed. All models are based on real data from the companies. The models are detailed and describe the problems accurately. The solution methods are developed such that the solution time is kept within practical limits. Results from Papers II--III have been used by Södra Cell AB to support the change of the terminal structure as well as in budget planning. / Denna avhandling presenterar matematiska modeller och lösningsmetoder för optimering av olika logistikproblem inom skogsindustrin. Vi studerar försörjningskedjor för skogsbränsle och massaproduker, och beaktar den årliga planeringen i syfte att optimera flödet. Det första problemet behandlar skogsbränsle och är ett samarbete med Sydved Energileveranser AB. Råmaterial i form av grenar och toppar från avverkningsplatser ska flisas och transporteras till värmeverk, eventuellt via terminaler. Det finns möjlighet att flisa både i skogen och på terminaler. Biprodukter från sågverk kan också användas som råmaterial. Vid behov kan utbudet av råmaterial utökas genom att fler avverkningsplatser och sågverk kontrakteras. Värmeverken har en efterfrågan, angiven i kWh per månad, som ska uppfyllas. Exempel på beslut som ska tas är var flisning ska ske, om nya avverkningsplatser ska kontrakteras, var lagring ska ske, samt hur och när skogsbränslet ska transporteras. Nästföljande problem behandlar massaprodukter och är ett samarbete med Södra Cell AB. Olika sorters massaved från skogen och biprodukter från sågverk utgör råmaterial för produktion av massaprodukter. Råmaterialet transporteras till massabruk för tillverkning enligt specificerade recept. De färdiga produkterna transporteras sedan med fartyg till terminaler i Europa. Från terminalerna transporteras produkterna vidare till pappersbruk, vilka är företagets slutkunder. Massaprodukterna transporteras i vissa fall med lastbil eller tåg direkt från massabruken till kunderna. Efterfrågan är angiven inom vissa gränser i olika order. Vissa order är fasta, vilket innebär att dess efterfrågan måste uppfyllas, medan andra order är fria. Exempel på beslut som ska tas är vilka bruk olika produkter ska produceras på, hur många och vilka terminaler som ska användas, samt hur transporterna ska utföras för att ge bästa resultat. Utifrån ovanstående beskrivningar har matematiska modeller formulerats. Ge-nom att lösa dessa kan vi få svar på logistik- och transportfrågorna och ett optimalt flöde kan hittas. För att lösa modellerna har kommersiell programvara använts. Heuristiker och mer avancerade optimeringsmetoder har också utvecklats i syfte att producera bra lösningar snabbare. / Article 4 was a manuscript entitled "Solving a multi-period supply chain problem for a pulp industry using Lagrangian heuristics based on time periods" at the time of the thesis defence.

This thesis concerns the interdisciplinary field of combinatorial auctions, combining the fields of computer science, optimization and economics. A combinatorial auction is an auction where many items are sold simultaneously and where bidders may submit indivisible combinatorial bids on groups of items. It is commonly believed that good solutions to the allocation problem can be achieved by allowing combinatorial bidding. Determining who wins in a combinatorial auction is fundamentally different from a traditional single-item auction because we are faced with a hard and potentially intractable optimization problem. Also, unless we are limited to truthful mechanisms, game theoretic analysis of the strategic behavior of bidders is still an open problem. We have chosen primarily to study the first-price combinatorial auction, a natural auction widely used in practice. Theoretical analysis of this type of auction is difficult and little has been done previously. In this thesis we investigate and discuss three fundamental questions with significant practical implications for combinatorial auctions. First, because the number of possible bids grows exponentially with the number of items, limitations on the number of bids are typically required. This gives rise to a problem since bidders are unlikely to choose the "correct" bids that make up the globally optimal solution. We provide evidence that an expressive and compact bidding language can be more important than finding the optimal solution. Second, given a first-price (sealed-bid) combinatorial auction, the question of equilibrium bidding strategies remains an open problem. We propose a heuristic for finding such strategies and also present feasible strategies. And finally, is a first-price combinatorial auction worth pursuing compared to the simpler simultaneous (single-item) auction? We prove, through a model capturing many fundamental properties of multiple items scenarios with synergies, that the first-price combinatorial auction produces higher revenue than simultaneous single-item auctions. We provide bounds on revenue, given a significantly more general model, in contrast to previous work.