Gotowa bibliografia 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.<br>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<br>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<br>Department of Industrial and Manufacturing Systems Engineering<br>Todd Easton<br>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<br>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<br>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<br>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<br>Doutor

<p>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.</p><p>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.</p><p>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.</p><p>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.</p><p>Also for the stochastic extension of the network design problem, the numerical experiments indicate that implicit programming is a good approach to the problem.</p><p>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.</p>

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.<br>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<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação<br>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<br>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<br>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<br>Mestrado<br>Ciência da Computação<br>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<br>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