Rozprawy doktorskie na temat „Constrained cutting”

The main focus of this thesis will be on the constrained two dimensional guillotine-cut cuffing stock (C2DGC) problem. Stock cutting involves the process of cutting certain small demand items from a larger object. During this process, waste material is generated, which is called trim loss. The cutting stock problem presents itself in many industrial processes where the cutting of material is concerned, for instance the cutting of wood in the furniture industry, the cutting of glass and plastic sheets in the glass industry, the cutting of paper in the cardboard industry and the cutting of steel bars in metallurgy, to name but a few. The cutting stock problem aims to find one or more solutions to a cutting problem so that the optimal amount of the stock sheet is utilized. This, in turn, implies that the trim loss (waste) will be kept to a minimum. Artificial intelligence search methods as well as existing exact C2DGC problem solution methods are investigated and evaluated critically. Different artificial intelligence search methods are then combined with the existing C2DGC problem solution methods, forming feasible algorithms to solve C2DGC problems. Existing C2DGC problem solution methods are also enhanced using innovative ideas. Numerical tests are then conducted to test the effectiveness and efficiency of each original and enhanced algorithm.
Thesis (Ph.D. (Computer Science))--North-West University, Potchefstroom Campus, 2004.

Le placement de production (UC pour unit commitment) est une famille de problèmes d'optimisation qui déterminent l’état et la puissance de consigne des groupes de production pour satisfaire la demande électrique à moindre coût. Traditionnellement, une contrainte de sûreté détermine un certain volume de capacité raccordée disponible, appelé la réserve, destinée à gérer l'incertitude. Néanmoins, dans les petits systèmes la contrainte de réserve fixe peut entraîner dans certains cas une violation du critère N-1 bien que le volume de réserve minimale soit respecté. Plus récemment, la part croissante de production variable à partir de sources renouvelables (ENR) peut conduire à des programmes d’appel qui ne garantissent plus la sûreté même dans les grands systèmes.Pour y faire face, différentes techniques d'atténuation des impacts ont été proposées telle que la révision des modèles de placement de la production pour inclure une meilleure représentation de la dynamique du système. Cette sous-famille des problèmes UC est formellement définie dans ces travaux comme le problème FCUC (frequency constrained unit commitment). Elle vise à maintenir la fréquence au-dessus d'un certain seuil, et éviter ainsi le délestage par sous-fréquence (DSF).La première partie de ces travaux identifie les défis dans la formulation du problème FCUC. D’une part, la contrainte de fréquence est fortement non-linéaire par rapport aux variables de décision du problème UC. D’autre part, elle est difficile à approcher par des fonctions analytiques. La simulation séquentielle d'un modèle UC classique et d’un modèle de réponse primaire de la fréquence est alors proposée. L’intérêt d’une formulation plus fidèle de la contrainte de sûreté est donc révélé. La deuxième partie de ces travaux étudie l'impact des ENR sur la réponse primaire de la fréquence. Le besoin de formuler des modèles de FCUC plus précis est mis en avant.La troisième partie des travaux examine le coût, les bénéfices et les limitations des modèles FCUC, basés sur des contraintes indirectes sur certains paramètres dynamiques des unités de production. Il est montré que, bien que l'application de contraintes de sécurité indirectes assure la sûreté dans certains pas horaires, l'effet inverse peut apparaître à un autre instant. Ainsi, l’efficacité des leviers dépend fortement du point de fonctionnement du système. Il en est de même pour le coût de la solution. Cette étude met en évidence la nécessité de nouvelles méthodes pour traiter correctement la contrainte sur le creux de fréquence afin d'assurer l'optimalité et efficacité de la solution.Finalement, la quatrième partie des travaux offre une nouvelle formulation du problème FCUC suivant une approche de décomposition de Bender. La décomposition de Bender sépare un problème d'optimisation avec une certaine structure en deux parties : le problème maître et le problème esclave. Dans le cas du FCUC, le problème maître propose des plans de production candidats (états des groupes) et le problème esclave assure le respect des contraintes de fréquence par le biais d'un modèle de plans sécants. Les résultats de simulation montrent que la représentation plus précise du creux de fréquence au niveau du problème esclave réduit le risque de DSF et le coût de la sécurité par rapport à d'autres modèles de FCUC
The Unit Commitment problem (UC) is a family of optimisation models for determining the optimal short-term generation schedule to supply electric power demand with a defined risk level. The UC objective function is given by the operational costs over the optimisation horizon. The constraints include, among others, technical, operational and security limits. Traditionally, the security constraints are given by the requirement of a certain volume of on-line spare capacity, which is called the reserve and is meant to handle uncertainty, while preventing the interruption of power supply. It is commonly specified following a static reliability criterion, such as the N-1 rule.Nevertheless, in small systems the fixed, and a priori defined, reserve constraint could entail a violation of the N-1 criterion, although the reserve constraint was met. More recently, the increasing share of variable generation from renewable sources (V-RES), such as wind and solar, may lead to UC solutions that no longer ensure system security. Therefore, different impact mitigation techniques have been proposed in literature, which include the revision of UC models to provide a better representation of the system dynamics. This subfamily of UC models is formally defined in this work as the frequency constrained UC problem (FCUC), and aims to keep the frequency above a certain threshold, following pre-defined contingencies, by adding enhanced security constraints. In this work this topic is addressed in four parts.The first part identifies the main challenge of formulating the FCUC problem. Indeed, the frequency minimum, also called the frequency nadir, constraint is strongly non-linear on the decision variables of the UC model. Moreover, the behaviour of the frequency nadir regarding the binary decision variables is hard to approximate by analytical functions. Thus, a sequential simulation approach is proposed, based on a classic UC model and a reduced order model of the primary frequency response. The potential benefits of a smarter allocation of the primary reserve is revealed.The second part of this work investigates the impact of V-RES sources on the primary frequency response. The underlying processes that lead to the increase of the Under-Frequency Load Shedding (UFLS) risk are thoroughly discussed. The need of formulating more accurate FCUC models is highlighted.The third part of this work examines the cost/benefit and limitation of FCUC models based on indirect constraints over certain dynamic parameters of the generating units. A methodology is proposed that assesses the effectiveness and optimality of some existing V-RES impact mitigation techniques, such as the increase of the primary reserve requirement, the prescription of an inertia requirement, the authorisation of V-RES dispatch-down or the consideration of fast non-synchronous providers of frequency regulation services. This study showed the need for new methods to properly handle the frequency nadir constraint in order to ensure optimality, without compromising the optimisation problem’s tractability.The fourth part of this work offers a new formulation of the FCUC problem following a Bender’s decomposition approach. This method is based on the decomposition of an optimisation problem into two stages: the master and the slave problems. Here, the master problem deals with the generating unit states and the slave problem handles the frequency nadir constraints through a cutting plane model. Simulation results showed that the more accurate representation of the frequency nadir in the slave problem reduces the risk of UFLS and the security cost, with respect to other FCUC models, such as those based on inertia constraints. In addition, the optimality of the global solution is guaranteed; although the convergence of the master problem is slow, due to the well-known tailing off effect of cutting plane methods

My dissertation considers solving of linear programming problems with p-order conic constraints that are related to a class of stochastic optimization models with risk objective or constraints that involve higher moments of loss distributions. The general proposed approach is based on construction of polyhedral approximations for p-order cones, thereby approximating the non-linear convex p-order conic programming problems using linear programming models. It is shown that the resulting LP problems possess a special structure that makes them amenable to efficient decomposition techniques. The developed algorithms are tested on the example of portfolio optimization problem with higher moment coherent risk measures that reduces to a p-order conic programming problem. The conducted case studies on real financial data demonstrate that the proposed computational techniques compare favorably against a number of benchmark methods, including second-order conic programming methods.

Master of Science
Department of Industrial and Manufacturing Systems Engineering
Todd Easton
Integer Programming is used to solve numerous optimization problems. This class of mathematical models aims to maximize or minimize a cost function restricted to some constraints and the solution must be integer. One class of widely studied Integer Program (IP) is the Multiple Knapsack Problem (MKP). Unfortunately, both IPs and MKPs are NP-hard, potentially requiring an exponential time to solve these problems. Utilization of cutting planes is one common method to improve the solution time of IPs. A cutting plane is a valid inequality that cuts off a portion of the linear relaxation space. This thesis presents a new class of cutting planes referred to as merged knapsack cover inequalities (MKCI). These valid inequalities combine information from a cover inequality with a knapsack constraint to generate stronger inequalities. Merged knapsack cover inequalities are generated by the Merging Knapsack Cover Algorithm (MKCA), which runs in linear time. These inequalities may be improved by the Exact Improvement Through Dynamic Programming Algorithm (EITDPA) in order to make them stronger inequalities. Theoretical results have demonstrated that this new class of cutting planes may cut off some space of the linear relaxation region. A computational study was performed to determine whether implementation of merged knapsack cover inequalities is computationally effective. Results demonstrated that MKCIs decrease solution time an average of 8% and decrease the number of ticks in CPLEX, a commercial IP solver, approximately 4% when implemented in appropriate instances.

Le problème de tournées de véhicules (Vehicle Routing Problem - VRP) est un problème d'optimisation combinatoire utilisé généralement pour modéliser et résoudre des différents problèmes rencontrés dans les systèmes logistiques et de transport. Dans cette thèse, nous nous sommes intéressés à l'étude et la résolution d'une classe de problèmes du VRP appelée les problèmes de courses d'orientation (Team Orienteering Problem - TOP). Dans cette catégorie de problèmes, il est a priori impossible de visiter tous les clients en raison de ressources limitées. On associe plutôt un profit à chaque client qui représente sa valeur. Ce profit est collecté lorsque le client est visité par l'un des véhicules disponibles. L'objectif est donc de sélectionner un sous ensemble de clients à servir tout en maximisant le profit total collecté. Dans un premier temps, nous avons introduit une nouvelle généralisation pour le TOP que nous avons appelé le Clustered TOP ou CluTOP. Dans cette variante, les clients sont regroupés en sous-ensembles appelés clusters auxquels nous associons des profits. Pour résoudre cette variante, nous avons proposé un schéma exact basé sur l'approche des plans sécants avec des inégalités valides supplémentaires et des pré-traitements. Nous avons également conçu une méthode heuristique basée sur l'approche order first-cluster second. Cette heuristique hybride combine une heuristique de type Adaptive Large Neighborhood Search qui explore l'espace des solutions et une procédure de découpage qui explore l'espace de recherche des tours géants. De plus, la procédure de découpage est renforcée par une recherche locale afin de mieux explorer l'espace de recherche. Le deuxième problème traité dans ce travail s'appelle le Synchronized Team Orienteering Problem with Time Windows (STOPTW). Cette variante avait été initialement proposée afin de modéliser des scénarios liés à la protection des infrastructures stratégiques menacées par l'avancée des feux de forêts. En plus des contraintes de fenêtres de temps et des visites synchronisées, cette variante considère le cas d'une flotte de véhicules hétérogène. Pour résoudre ce problème, nous avons proposé une méthode heuristique basée sur l'approche GRASP×ILS qui est parvenue à dominer la seule approche existante dans la littérature. La dernière variante du TOP abordée dans cette thèse s'appelle le Set Orienteering Problem (SOP). Les clients dans cette variante sont regroupés en sous-ensembles appelés clusters. Un profit est associé à chaque groupe qui n'est obtenu que si au moins un client est desservi par le véhicule disponible. Nous avons proposé une méthode de coupes avec deux procédures de séparation pour séparer les contraintes d'élimination des sous-tours. Nous avons également proposé un algorithme Mémétique avec une procédure de découpage optimale calculée à l'aide de la programmation dynamique
The Vehicle Routing Problem (VRP) is a family of Combinatorial Optimization Problems generally used to solve different issues related to transportation systems and logistics. In this thesis, we focused our attention on a variant of the VRP called the Team Orienteering Problem (TOP). In this family of problems, it is a priory impossible to visit all the customers due to travel time limitation on vehicles. Instead, a profit is associated with each customer to represent its value and it is collected once the customer is visited by one of the available vehicles. The objective function is then to maximize the total collected profit with respect to the maximum travel time. Firstly, we introduced a new generalization for the TOP that we called the Clustered TOP (CluTOP). In this variant, the customers are grouped into subsets called clusters to which we associate profits. To solve this variant, we proposed an exact scheme based on the cutting plane approach with additional valid inequalities and pre-processing techniques. We also designed a heuristic method based on the order first-cluster second approach for the CluTOP. This Hybrid Heuristic combines between an ANLS heuristic that explores the solutions space and a splitting procedure that explores the giant tours search space. In addition, the splitting procedure is enhanced by local search procedure in order to enhance its coverage of search space. The second problem treated in this work is called the Synchronized Team Orienteering Problem with Time Windows (STOPTW). This variant was initially proposed in order to model scenarios related to asset protection during escaped wildfires. It considers the case of a heterogeneous fleet of vehicles along with time windows and synchronized visits. To solve this problem, we proposed a heuristic method based on the GRASP×ILS approach that led to a very outstanding results compared to the literature. The last variant of the TOP tackled in this thesis called the Set Orienteering Problem (SOP). Customers in this variant are grouped into subsets called clusters. Each cluster is associated with a profit which is gained if at least one customer is served by the single available vehicle. We proposed a Branch-and-Cut with two separation procedures to separate subtours elimination constraints. We also proposed a Memetic Algorithm with an optimal splitting procedure based on dynamic programming

Orientador: Marcos Valerio Ribeiro
Resumo: Ambientes industriais são altamente competitivos. Fatores como a agilidade, a flexibilidade, a prestação de serviços, a qualidade e preços são as vantagens competitivas procuradas pelas organizações. Neste cenário, as otimizações propostas que abordam tais fatores são de particular interesse para o planejamento de processos. O procedimento proposto tratado é o resultado líquido direto e o aumento da competitividade no mercado de uma determinada empresa, visando que sua estrutura financeira seja a mais saudável possível. Este trabalho tem como objetivo auxiliar e desenvolver um procedimento padrão de verificação do nível de rentabilidade de uma empresa e ainda, se esta empresa tem a probabilidade de tornar-se mais rentável. Tal procedimento visa atingir um segundo objetivo no sentido de maximizar os recursos já existentes na própria organização. O aspecto chave desta pesquisa diz respeito à utilização de máquina com tempos ociosos e plena utilização de todos os sistemas disponíveis de fábrica. Quando a ociosidade destas máquinas utilizadas em pleno processo produtivo, é possível concluir como resultado das aplicações realizadas, uma maximização dos recursos propiciando o melhor resultado da organização. Esta ociosidade quando não apurada com a devida acurácia é lançada indevidamente nos custos dos produtos, fazendo com que a empresa possa perder competitividade
Abstract: Industrial environments are highly competitive. Factors such as agility, flexibility, service delivery, quality and prices are the competitive advantages sought by organizations. In this scenario, the proposed optimizations that address such factors are of particular interest for process planning. The proposed procedure is the direct net result and the increase of the competitiveness in the market of a certain company, aiming that its financial structure is as healthy as possible. This work aims to assist and develop a standard procedure for verifying the level of profitability of a company and still, if this company has the probability of becoming more profitable. This procedure aims to achieve a second objective in order to maximize resources already existing in the organization itself. The key aspect of this research concerns the use of idling machines and full utilization of all the systems available from the factory. When the idleness of these machines used in full productive process, it is possible to conclude as a result of the applications made, a maximization of the resources propitiating the best result of the organization. This idleness when not verified with the correct accuracy is improperly thrown into the costs of the products, causing the company to lose competitiveness
Doutor

This thesis investigates the second-best toll pricing and capacity expansion problems when stated as mathematical programs with equilibrium constraints (MPEC). Three main questions are rised: First, whether conventional descent methods give sufficiently good solutions, or whether global solution methods are to prefer. Second, how the performance of the considered solution methods scale with network size. Third, how a discretized stochastic mathematical program with equilibrium constraints (SMPEC) formulation of a stochastic network design problem can be practically solved. An attempt to answer these questions is done through a series ofnumerical experiments.

The traffic system is modeled using the Wardrop’s principle for user behavior, separable cost functions of BPR- and TU71-type. Also elastic demand is considered for some problem instances.

Two already developed method approaches are considered: implicit programming and a cutting constraint algorithm. For the implicit programming approach, several methods—both local and global—are applied and for the traffic assignment problem an implementation of the disaggregate simplicial decomposition (DSD) method is used. Regarding the first question concerning local and global methods, our results don’t give a clear answer.

The results from numerical experiments of both approaches on networks of different sizes shows that the implicit programming approach has potential to solve large-scale problems, while the cutting constraint algorithm scales worse with network size.

Also for the stochastic extension of the network design problem, the numerical experiments indicate that implicit programming is a good approach to the problem.

Further, a number of theorems providing sufficient conditions for strong regularity of the traffic assignment solution mapping for OD connectors and BPR cost functions are given.

No presente trabalho estudamos duas variações do problema de empacotamento de itens retangulares idênticos, permitindo rotações de 90 graus, em um poliedro. Uma variação consiste em encontrar a maior quantidade de itens retangulares idênticos que podem ser empacotados em um poliedro. A outra consiste em encontrar o poliedro de um determinado tipo com menor área para empacotar uma quantidade fixa de itens retangulares idênticos. Desenvolvemos restrições de eliminação de simetrias para estes problemas, o que tornou a resolução dos mesmos mais eficiente, por métodos do tipo branch-&-bound. Estudamos também o problema de corte no qual há uma determinada demanda (de itens) a ser cortada e um conjunto de objetos disponíveis. Desejamos satisfazer a demanda minimizando o custo dos objetos utilizados e, dentre as diferentes possibilidades de se fazer isso, desejamos aquela que maximize as sobras aproveitáveis. De forma geral, sobras aproveitáveis podem ser entendidas como regiões retangulares de um objeto que possuem altura e largura iguais ou superiores a de um item de referência e representam sobras do processo de corte que podem se tornar objetos e serem reaproveitadas em um novo procedimento de corte. Apresentamos modelos de otimização em dois níveis para duas variações do problema de corte com sobras aproveitáveis a saber: o problema de corte de itens retangulares em dois estágios e o problema de corte de itens retangulares não guilhotinado. Como formas de resolver os modelos propostos, apresentamos reformulações destes modelos de programação em dois níveis em modelos de programação inteira mista. Lidamos também com uma variação do problema de corte com sobras aproveitáveis considerando a minimização da quantidade de sobras. Aplicamos restrições de eliminação de simetrias aos modelos desenvolvidos para o problema de corte de itens retangulares com sobras aproveitáveis, a fim de resolver instâncias maiores, e desenvolvemos uma estratégia de solução alternativa para os modelos. Os modelos desenvolvidos foram implementados computacionalmente e fomos capazes de resolver instâncias pequenas dos problemas em questão.
In this work we study two variations of the packing problem where identical rectangular items must be packed into a polyhedron. One of the variations consists in finding the largest amount of rectangular items that can fit in a polyhedron. The other one consists in finding a minimal area polyhedron of a certain type that packs a set of rectangular identical items. We present some symmetry-breaking constraints that reduce the computational effort in solving those problems through a branch-&-bound method. We also studied the cutting stock problem where there are some items to be cut from a set of rectangular objects and we need to satisfy the demand of items to be cut minimizing the cost of the used objects and, among the different ways of doing this, we want that which maximize the usable leftovers. Loosely speaking,usable leftovers can be understood as rectangular regions in an object that has the width and the height greater than or equal to the ones of a reference item. These leftovers can be seen as leftovers from a cutting process that will become items in a new cutting process. We present bilevel programming models to two variations of this problem with usable leftovers: the two-stage cutting stock problem of rectangular items and the non-guillotine cutting stock problem of rectangular items. In order to solve the proposed models we present also MIP reformulations of these bilevel programming problem models. We also developed some symmetry breaking constraints in order to accelerate the solving process of those models. The developed models were computationally programmed and we were able to solve small instances of the proposed problems

Orientador: Flávio Keidi Miyazawa
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-19T18:16:55Z (GMT). No. of bitstreams: 1 Hokama_PedroHenriqueDelBianco_M.pdf: 1340789 bytes, checksum: b5cc3f26e41b90afabdfac5c7a33bf05 (MD5) Previous issue date: 2011
Resumo: Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática
Abstract: We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem, and the Three- Dimensional Packing Problem With Loading Constraints. In this problem, a vehicle must be loaded at the depot and deliver boxes to the customers. Every customer has a set of boxes that should receive and our goal is to minimize the travel cost of the vehicle. Unloading is done through a single side of the container and items from an unloading customer must not be blocked by items to be delivered later. We propose exact and heuristic branch-and-cut algorithm to find a minimum cost route. Adaptations of algorithms from the literature and a Constraint Programming formulation is presented to find a packing that consider unloading contraints. We performed computational tests on instances randomly generated and compared results with the algorithms adapted from literature. The results were quite satisfactory resolving several instances in reasonable computational time
Mestrado
Ciência da Computação
Mestre em Ciência da Computação

NP-hard problems of higher-dimensional orthogonal packing are considered. We look closer at their logical structure and show that they can be decomposed into problems of a smaller dimension with a special contiguous structure. This decomposition influences the modeling of the packing process, which results in three new solution approaches. Keeping this decomposition in mind, we model the smaller-dimensional problems in a single position-indexed formulation with non-overlapping inequalities serving as binding constraints. Thus, we come up with a new integer linear programming model, which we subject to polyhedral analysis. Furthermore, we establish general non-overlapping and density inequalities and prove under appropriate assumptions their facet-defining property for the convex hull of the integer solutions. Based on the proposed model and the strong inequalities, we develop a new branch-and-cut algorithm. Being a relaxation of the higher-dimensional problem, each of the smaller-dimensional problems is also relevant for different areas, e.g. for scheduling. To tackle any of these smaller-dimensional problems, we use a Gilmore-Gomory model, which is a Dantzig-Wolfe decomposition of the position-indexed formulation. In order to obtain a contiguous structure for the optimal solution, its basis matrix must have a consecutive 1's property. For construction of such matrices, we develop new branch-and-price algorithms which are distinguished by various strategies for the enumeration of partial solutions. We also prove some characteristics of partial solutions, which tighten the slave problem of column generation. For a nonlinear modeling of the higher-dimensional packing problems, we investigate state-of-the-art constraint programming approaches, modify them, and propose new dichotomy and intersection branching strategies. To tighten the constraint propagation, we introduce new pruning rules. For that, we apply 1D relaxation with intervals and forbidden pairs, an advanced bar relaxation, 2D slice relaxation, and 1D slice-bar relaxation with forbidden pairs. The new rules are based on the relaxation by the smaller-dimensional problems which, in turn, are replaced by a linear programming relaxation of the Gilmore-Gomory model. We conclude with a discussion of implementation issues and numerical studies of all proposed approaches
Es werden NP-schwere höherdimensionale orthogonale Packungsprobleme betrachtet. Wir untersuchen ihre logische Struktur genauer und zeigen, dass sie sich in Probleme kleinerer Dimension mit einer speziellen Nachbarschaftsstruktur zerlegen lassen. Dies beeinflusst die Modellierung des Packungsprozesses, die ihreseits zu drei neuen Lösungsansätzen führt. Unter Beachtung dieser Zerlegung modellieren wir die Probleme kleinerer Dimension in einer einzigen positionsindizierten Formulierung mit Nichtüberlappungsungleichungen, die als Bindungsbedingungen dienen. Damit entwickeln wir ein neues Modell der ganzzahligen linearen Optimierung und unterziehen dies einer Polyederanalyse. Weiterhin geben wir allgemeine Nichtüberlappungs- und Dichtheitsungleichungen an und beweisen unter geeigneten Annahmen ihre facettendefinierende Eigenschaft für die konvexe Hülle der ganzzahligen Lösungen. Basierend auf dem vorgeschlagenen Modell und den starken Ungleichungen entwickeln wir einen neuen Branch-and-Cut-Algorithmus. Jedes Problem kleinerer Dimension ist eine Relaxation des höherdimensionalen Problems. Darüber hinaus besitzt es Anwendungen in verschiedenen Bereichen, wie zum Beispiel im Scheduling. Für die Behandlung der Probleme kleinerer Dimension setzen wir das Gilmore-Gomory-Modell ein, das eine Dantzig-Wolfe-Dekomposition der positionsindizierten Formulierung ist. Um eine Nachbarschaftsstruktur zu erhalten, muss die Basismatrix der optimalen Lösung die consecutive-1’s-Eigenschaft erfüllen. Für die Konstruktion solcher Matrizen entwickeln wir neue Branch-and-Price-Algorithmen, die sich durch Strategien zur Enumeration von partiellen Lösungen unterscheiden. Wir beweisen auch einige Charakteristiken von partiellen Lösungen, die das Hilfsproblem der Spaltengenerierung verschärfen. Für die nichtlineare Modellierung der höherdimensionalen Packungsprobleme untersuchen wir moderne Ansätze des Constraint Programming, modifizieren diese und schlagen neue Dichotomie- und Überschneidungsstrategien für die Verzweigung vor. Für die Verstärkung der Constraint Propagation stellen wir neue Ablehnungskriterien vor. Wir nutzen dabei 1D Relaxationen mit Intervallen und verbotenen Paaren, erweiterte Streifen-Relaxation, 2D Scheiben-Relaxation und 1D Scheiben-Streifen-Relaxation mit verbotenen Paaren. Alle vorgestellten Kriterien basieren auf Relaxationen durch Probleme kleinerer Dimension, die wir weiter durch die LP-Relaxation des Gilmore-Gomory-Modells abschwächen. Wir schließen mit Umsetzungsfragen und numerischen Experimenten aller vorgeschlagenen Ansätze

Submitted by GISLAINE MARA MELEGA null (gis_laine_m@hotmail.com) on 2017-03-27T18:20:11Z No. of bitstreams: 1 TESE_Gislaine Melega_Matemática.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5)
Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-03-29T19:23:05Z (GMT) No. of bitstreams: 1 melega_gm_dr_sjrp.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5)
Made available in DSpace on 2017-03-29T19:23:05Z (GMT). No. of bitstreams: 1 melega_gm_dr_sjrp.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5) Previous issue date: 2017-02-21
Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
Nesta tese, estamos interessados em tratar de maneira integrada dois conhecidos problemas da literatura. Esta integração é referida na literatura como problema integrado de dimensionamento de lotes e corte de estoque. A ideia consiste em considerar simultaneamente, as decisões relacionadas com ambos os problemas, de modo a capturar a interdependência entre estas decisões e, assim, obter uma melhor solução global. Propõe-se um modelo matemático geral para o problema integrado de dimensionamento de lotes e corte de estoque (GILSCS), que considera vários níveis de integração e nos permite classificar a literatura, em termos de modelos matemáticos, dos problemas integrados. A classificação é organizada a partir de dois principais aspectos de integração que são: a integração através dos períodos de tempo e a integração entre os níveis de produção. Em um horizonte de planejamento que considera vários períodos, o estoque fornece uma ligação entre os períodos. Esta integração, por períodos de tempo, constitui o primeiro tipo de integração. O problema geral também considera a produção em diferentes níveis: objetos são fabricados ou comprados e então são cortados para produzir peças menores e estas, por sua vez, constituem componentes para a produção dos produtos finais. A integração entre os diferentes níveis de produção consiste no segundo tipo de integração. A revisão da literatura também possibilita direcionar interessantes áreas para pesquisas futuras. O comportamento da solução para este tipo de problema, com três níveis e vários períodos, é estudado a partir do desenvolvimento de métodos de solução considerando abordagens que superam as dificuldades do problema, que consistem no alto número de padrões de corte, estruturas em vários níveis (multiestágios) e variáveis binárias de preparo. Os métodos de solução propostos para o problema GILSCS são baseados em duas abordagens conhecidas da literatura, usadas com sucesso para resolver os problemas separadamente, que são o procedimento de geração de colunas e heurísticas de decomposição do tipo relax-and-fix. Estas estratégias e suas variações são combinadas à um pacote de otimização em um estudo computacional com dados gerados aleatoriamente. Uma revisão da literatura, em termos de métodos de solução, para o problema integrado também é apresentada. Outras contribuições desta tese consistem em propor diferentes modelos matemáticos para o problema integrado, combinando modelos alternativos para cada um dos problemas separadamente. Neste estudo, o objetivo é comparar e avaliar, com um extensivo estudo computacional, a qualidade e o impacto das diferentes formulações. O outro trabalho trata de uma aplicação do problema integrado em um indústria de móveis de pequeno porte, em que restrições específicas do ambiente industrial são abordadas, como estoque de segurança e ciclos da serra. A solução obtida pelo modelo proposto é comparada com uma simulação da prática da empresa.
In this thesis, the subject of interest is in treating, in an integrated way, two wellknown problems in the literature. This integration is referred in the literature as the integrated lot-sizing and cutting stock problem. The basic idea is to consider, simultaneously, the decisions related to both problems so as to capture the interdependency between these decisions in order to obtain a better global solution. We propose a mathematical model for a general integrated lot-sizing and cutting stock (GILSCS) problem. This model considers multiple dimensions of integration and enables us to classify the current literature, in terms of mathematical models, in this field. The main classification of the literature is organized around two types of integration. In a planning horizon which consists of multiple periods, the inventory provides a link between the periods. This integration across time periods constitutes the first type of integration. The general problem also considers the production in different levels: objects are fabricated or purchased and then, they are cut to produce the pieces which are then assembled as components in the production of final products. The integration between these production levels constitutes the second type of integration. The literature review also enables us to point out interesting areas for future research. The behavior of a solution to this type of problem, with three levels of production and several time periods, is studied considering the development of solution approaches that overcome the difficulties of the problem, which are the high number of cutting patterns, multi-level structures and the binary values of the setup variables. The solution methods proposed to the GILSCS problem are based on two known strategies from the literature which are used successfully to solve the problems separately, which are the column generation procedure and decomposition heuristics based on relax-and-fix procedure. These strategies and their variations are combined into an optimization package in a computational study with randomly generated data. A literature review, in terms of solution methods, to the integrated problem, is also presented. Other contributions of this thesis consist of proposing different mathematical models for the integrated problem combining alternative models for each one of the problems separately. In this study, the aim is to compare and evaluate, with an extensive computational study, the quality and the impact of these dfifferent formulations. Another study is an application of the integrated problem in a small furniture factory, in which specific constraints related to the industrial environment are addressed, such as, safety stock level constraints and saw cycles constraints. The solution obtained from the proposed model is compared to a simulation of the common practice in the company.
FAPESP: 2012/20631-2

碩士
明志科技大學
工業工程與管理研究所
99
The two-dimensional cutting stock problem consists of cutting a rectangular plate into specified smaller rectangular pieces, so that the objective function is optimized. This problem is also classified as NP-hard. In practical, raw material utilization has always been an important factor for the cutting industry, therefore, efficient use of the minimum quantity of raw plate in cutting while meet the requirements of the smaller pieces has become more important. In this research, we have developed an integer nonlinear programming formulation for optimizing the layout of the smaller pieces on the raw plate while the required quantity for the raw plate is minimized. Test problems have been optimally solved by a branch and bound method in LINGO solver. The results show that our formulation outperformed others in getting the optimal solution, also can provide the exact coordinates for the smaller pieces on the raw plates in order to cut the plates with ease.

Cutting is an important deformation process encountered during many instances in the engineering of infrastructure, such as trawling, trenching, and excavation. This thesis presents the results of an experimental program on the orthogonal cutting of granular materials, performed under plane strain conditions. The kinematics of granular materials, when subjected to large deformations, is understood through direct imaging and concomitant image analysis. Three suites of experiments were performed to understand the effects of boundary conditions, material systems, and other constraints on the mechanics of cutting. In the first suite of experiments, we perform cutting on two sets of granular materials, spherical glass beads and angular Cauvery delta sand. We vary the three main parameters of the orthogonal cutting problem, the rake angle/ angle of attack of the tool, the initial depth of cut with respect to the free surface of the granular ensemble, and the cutting speed. The overall deformation of the material reaches a steady state after an initial transient phase, which can be observed from the angle of the repose of the pile that forms in-front of the tool. Instantaneous velocity fields show a bifurcation of flow occurring at the tool tip which results in a velocity jump across planes whose direction coincides with the Coulomb failure surfaces. These velocity jumps manifest as regions of intense shear emanating from the tool tip and has a ``band" like appearance when the effective strain rate contours are plotted. The velocity profiles across the shear band assume a sigmoidal shape which can be fit using an error function and allows us to extract the length scale associated with this velocity jump. We observe that the normalized width of the shear band decreases as particle size increases. The width of the shear band for both granular materials was observed to be insensitive to changes in the rake angle, cutting speed, and also the initial depth of cut and hence is a material constant for a given system size. In some cases, we also observe multiple shear bands forming in the system which run parallel to one another and have similar thickness. The measured volumetric strain rate within the shear bands is much lower than the shear rate. The dilation angle measured is always less than the friction angle suggesting that plastic flow occurring within the shear bands is in a non-associative state. We further observe a dead zone of granular material at the tool interface. In the second suite of experiments, we use a suite of granular materials such as cylindrical steel beads, rice grains, clay aggregates, polystyrene beads, and smaller glass beads. At the ensemble level, we find that the volume of material removed during cutting increases linearly in time for all granular materials. At the meso-scale, we once again observe similar sigmoidal velocity profiles across the shear band and is further used to determine the shear band width of each granular material. We find the normalized width of the shear bands is a function of particle size. Upon re-scaling the velocity profiles for different granular materials by their corresponding shear band widths, they all collapse onto a single master curve given by the scaled error function. Thus, we witness a remarkable universality in the kinematics of granular materials at multiple length scales during orthogonal cutting. We further measure the temperature within the shear bands and observe a power-law relationship between the temperature and shear rate, with an exponent ~ 0.55, a significant deviation from the predictions of kinetic theory. In-order to further probe the origin of this inherent length scale at the meso-level, we measure the mean squared displacements of the particles in the shear bands and observe that the particles are not diffusive and hence conclude that the length scale corresponding to the shear bands does not have its origin in a diffusion like process. In the third suite of experiments, a series of constrained cutting experiments were carried out wherein we force the cut granular material to flow through narrow channels by placing a rigid constraint across the cutting tool. We study the formation and evolution of shear bands under such circumstances. By the addition of a constraint, we pin the shear bands between the tool tip and the constraint corner. The separation distance between the tool and the constraint has a direct consequence on the characteristics of the shear bands generated within the ensemble. As the separation between the tool and plate increases, we recover the behavior of unconstrained cutting. Within the channel, the flow fields are very similar to what is observed in vertical hoppers, though the motion of particles is directed against gravity. Like in hopper flows, we observe dead zones along the length of tool and constraint boundaries. We further measure the thickness of this boundary layer using the same error function fit and find that the thickness of the boundary layer is constant across the channel height and nearly symmetric at the two boundaries for small channel widths. As the channel width increases, the boundary layer thickness also increases and becomes asymmetric at the two boundaries. We also present the results of cutting carried out on a constrained granular ensemble, i.e. two granular chains with different numbers of beads. This addition of a constraint to the granular ensemble suppresses the formation of localized shear bands within the ensemble and the deformation is diffuse and homogeneous. The deformation also propagates to regions faraway from the tool. Lastly, we provide a numerical underpinning to the cutting experiments using contact dynamics simulations. As in the case of the experiments, we vary the rake angle, initial depth of cut, and cutting speed in simulation. We compare the simulation results with analytical solutions provided by a 2-D model of cutting. We compare the deformation fields obtained from the simulations with our experimental results and deduce the forces on the tool and along the shear band.
IISc, DBT

碩士
國立臺灣科技大學
營建工程系
97
For many years, the construction industry has been regarded as one of the main developed industries in Taiwan. Since the construction market has been under recession in recent years, many construction companies face a decrease in profit due to not well-planned cost control. Therefore, contractors have seen the cost control as an important task. As the technology changes day by day, it is desired that the cost control may be improved using advanced optimization techniques. The purpose of this research is to minimize the total cost of cutting steel bar, in other words, to increase the return value of used and unused raw steel bar, and reduce the cost by cutting frequency reduction. For existing of the past algorithms , a cutting plan that violates the constraints was often encountered, and this resulted in waste of calculation resources. An improved Genetic Algorithm was firstly presented in this research so as to minimize the number of constraints. In order to handle infeasible solutions properly, the coded system of chromosome of steel bar cutting will be changed, and two models of solutions of cutting steel bar will also be brought up in this research. One model is to continuously search until the feasible solutions are found, and the other one is to apply the penalty strategy to handle the non-feasible solutions. Both models adopted the theory of tournament selection. As to verify the quality and efficiency of the solutions, the proposed models were tested in practical cases, and the results indicated that they are able to produce good cutting plans correctly and efficiently. Moreover, the models are also able to meet the requirements of construction operations because they generate the best solutions within the time constraints, and then retrench the human resource and upgrade the construction quality.

The present thesis is an attempt to identify possible win:win solutions to the apparent and widely reported conflict between aesthetics and the practice of timber harvesting in British Columbia (BC). The approach used is to review the literature on silvicultural systems, Visual Resource Management (VRM) as practiced in BC, public perceptions of various harvesting practices, the relationship between aesthetics and timber harvest levels, and on long term timber supply implications of proposed solutions in order to provide for a more complete picture. A series of short-term modelling exercises has been undertaken to assess the potential of using certain visually effective partial cutting techniques (termed dispersed retention cuttings here) as a possible solution to the conflict. This includes a description and comparison of the results obtained with similar independent modelling exercises. Key findings from the reviews and modelling analysis include the following: 1) Confusion still exists regarding "partial cutting". The term "dispersed retention cutting" is put forward in this thesis to reduce this confusion when discussing more visually acceptable forms of partial cutting. 2) There is a failure to consider the broader landscape-level context in BC, which has significant implications for the management of visual resources. 3) People prefer dispersed retention cutting to clearcutting for a given level of timber removal and some kinds of dispersed retention cutting can virtually eliminate VQOs as a constraint both in the short and long term. The perception that VQOs are a major constraint on timber harvesting appears to be an artefact of the reliance on clearcutting. 4) More research is needed on the feasibility of dispersed retention cutting techniques in different forest types. There is a difference of opinion among practitioners as to the extent to which dispersed retention cutting can be realistically undertaken. 5) Further analysis of the sensitivity of timber supply calculations to the harvesting practices (clearcutting or others) used in visually sensitive areas is needed. 6) More research is needed to find and validate key visual quality thresholds (e.g. at which level of removal is a dispersed retention cut perceived as a clearcut by the public?) and to develop landscape models that can handle dispersed retention cutting techniques over time and over large areas. Key Words: visual resource management, visual quality, public perceptions, partial cutting, forest, landscape, timber supply, timber availability, visual quality intensity index.

碩士
國立成功大學
工業與資訊管理學系
103
We address a two-echelon spare parts repairable inventory system consisting of a central repair warehouse and some regional depots. The objective is to determine an (S-1, S) pair that minimizes a cost function, defined only in terms of holding costs, subject to the constraint that the average response time to each customer is below a threshold level. To avoid the mistakes resulting from the approximation and implausible assumptions in traditional methods, we propose an algorithm based on simulation instead of queueing theory. The R＆S procedure can be used to solve simulation optimization problems for which the number of feasible solution is small, and thus we propose a simulation algorithm which combines the cutting plane method, the feasible check procedure and the feasible direction approach.

We consider a single-part, two-echelon supply chain problem for spare parts. The network consists of a single manufacturing plant, a set of service centers (SCs) and a set of customers. Both echelons keep spare parts using the base-stock replenishment policy. The plant behaves as an M/M/1 queueing system and has limited production and storage capacity. Demand faced by each SC follows an independent Poisson process. The problem is to determine optimal location-allocation and optimal base-stock levels at both echelons while satisfying the target service levels and customer preferences of SCs. We develop a mixed integer non-linear programming model and use cutting-plane method to optimize the inventory-location decisions. We present an exact solution procedure for the inventory stocking problem and demonstrate the limitations of using traditional inventory models like METRIC-like and Approximate in case of high utilization rates. We show the effectiveness of our proposed cutting-plane algorithm and provide important managerial insights for spare parts management.

NP-hard problems of higher-dimensional orthogonal packing are considered. We look closer at their logical structure and show that they can be decomposed into problems of a smaller dimension with a special contiguous structure. This decomposition influences the modeling of the packing process, which results in three new solution approaches. Keeping this decomposition in mind, we model the smaller-dimensional problems in a single position-indexed formulation with non-overlapping inequalities serving as binding constraints. Thus, we come up with a new integer linear programming model, which we subject to polyhedral analysis. Furthermore, we establish general non-overlapping and density inequalities and prove under appropriate assumptions their facet-defining property for the convex hull of the integer solutions. Based on the proposed model and the strong inequalities, we develop a new branch-and-cut algorithm. Being a relaxation of the higher-dimensional problem, each of the smaller-dimensional problems is also relevant for different areas, e.g. for scheduling. To tackle any of these smaller-dimensional problems, we use a Gilmore-Gomory model, which is a Dantzig-Wolfe decomposition of the position-indexed formulation. In order to obtain a contiguous structure for the optimal solution, its basis matrix must have a consecutive 1's property. For construction of such matrices, we develop new branch-and-price algorithms which are distinguished by various strategies for the enumeration of partial solutions. We also prove some characteristics of partial solutions, which tighten the slave problem of column generation. For a nonlinear modeling of the higher-dimensional packing problems, we investigate state-of-the-art constraint programming approaches, modify them, and propose new dichotomy and intersection branching strategies. To tighten the constraint propagation, we introduce new pruning rules. For that, we apply 1D relaxation with intervals and forbidden pairs, an advanced bar relaxation, 2D slice relaxation, and 1D slice-bar relaxation with forbidden pairs. The new rules are based on the relaxation by the smaller-dimensional problems which, in turn, are replaced by a linear programming relaxation of the Gilmore-Gomory model. We conclude with a discussion of implementation issues and numerical studies of all proposed approaches.
Es werden NP-schwere höherdimensionale orthogonale Packungsprobleme betrachtet. Wir untersuchen ihre logische Struktur genauer und zeigen, dass sie sich in Probleme kleinerer Dimension mit einer speziellen Nachbarschaftsstruktur zerlegen lassen. Dies beeinflusst die Modellierung des Packungsprozesses, die ihreseits zu drei neuen Lösungsansätzen führt. Unter Beachtung dieser Zerlegung modellieren wir die Probleme kleinerer Dimension in einer einzigen positionsindizierten Formulierung mit Nichtüberlappungsungleichungen, die als Bindungsbedingungen dienen. Damit entwickeln wir ein neues Modell der ganzzahligen linearen Optimierung und unterziehen dies einer Polyederanalyse. Weiterhin geben wir allgemeine Nichtüberlappungs- und Dichtheitsungleichungen an und beweisen unter geeigneten Annahmen ihre facettendefinierende Eigenschaft für die konvexe Hülle der ganzzahligen Lösungen. Basierend auf dem vorgeschlagenen Modell und den starken Ungleichungen entwickeln wir einen neuen Branch-and-Cut-Algorithmus. Jedes Problem kleinerer Dimension ist eine Relaxation des höherdimensionalen Problems. Darüber hinaus besitzt es Anwendungen in verschiedenen Bereichen, wie zum Beispiel im Scheduling. Für die Behandlung der Probleme kleinerer Dimension setzen wir das Gilmore-Gomory-Modell ein, das eine Dantzig-Wolfe-Dekomposition der positionsindizierten Formulierung ist. Um eine Nachbarschaftsstruktur zu erhalten, muss die Basismatrix der optimalen Lösung die consecutive-1’s-Eigenschaft erfüllen. Für die Konstruktion solcher Matrizen entwickeln wir neue Branch-and-Price-Algorithmen, die sich durch Strategien zur Enumeration von partiellen Lösungen unterscheiden. Wir beweisen auch einige Charakteristiken von partiellen Lösungen, die das Hilfsproblem der Spaltengenerierung verschärfen. Für die nichtlineare Modellierung der höherdimensionalen Packungsprobleme untersuchen wir moderne Ansätze des Constraint Programming, modifizieren diese und schlagen neue Dichotomie- und Überschneidungsstrategien für die Verzweigung vor. Für die Verstärkung der Constraint Propagation stellen wir neue Ablehnungskriterien vor. Wir nutzen dabei 1D Relaxationen mit Intervallen und verbotenen Paaren, erweiterte Streifen-Relaxation, 2D Scheiben-Relaxation und 1D Scheiben-Streifen-Relaxation mit verbotenen Paaren. Alle vorgestellten Kriterien basieren auf Relaxationen durch Probleme kleinerer Dimension, die wir weiter durch die LP-Relaxation des Gilmore-Gomory-Modells abschwächen. Wir schließen mit Umsetzungsfragen und numerischen Experimenten aller vorgeschlagenen Ansätze.