Search

We study a primal-dual interior point method specialized to clustered low-rank semidefinite programs requiring high precision numerics, which arise from certain multivariate polynomial (matrix) programs through sums-of-squares characterizations and sampling. We consider the interplay of sampling and symmetry reduction as well as a greedy method to obtain numerically good bases and sample points. We apply this to the computation of three-point bounds for the kissing number problem, for which we show a significant speedup. This allows for the computation of improved kissing number bounds in dimensions 11 through 23. The approach performs well for problems with bad numerical conditioning, which we show through new computations for the binary sphere packing problem. [ABSTRACT FROM AUTHOR]

We study three problems introduced by Bang-Jensen and Yeo (2015) and by Bang-Jensen et al. (2016) about finding disjoint "balanced" spanning rooted substructures in graphs and digraphs, which generalize classic packing problems such as detecting the existence of multiple arc-disjoint spanning arborescences. Namely, given a positive integer k , a digraph D = (V , A) , and a root r ∈ V , we first consider the problem of finding two arc-disjoint k -safe spanning r -arborescences, meaning arborescences rooted at a vertex r such that deleting any arc r v and every vertex in the sub-arborescence rooted at v leaves at least k vertices. Then, we consider the problem of finding two arc-disjoint (r , k) -flow branchings meaning arc sets admitting a flow that distributes one unit from r to every other vertex while respecting a capacity limit of n − k on every arc. We show that both these problems are FPT with parameter k , improving on existing XP algorithms. The latter of these results answers a question of Bang-Jensen et al. (2016). Further, given a positive integer k , a graph G = (V , E) , and r ∈ V , we consider the problem of finding two edge-disjoint (r , k) -safe spanning trees meaning spanning trees such that the component containing r has size at least k when deleting any vertex different from r. We show that this problem is also FPT with parameter k , again improving on a previous XP algorithm. Our main technical contribution is to prove that the existence of such spanning substructures is equivalent to the existence of substructures with size and maximum (out-)degree both bounded by a (linear or quadratic) function of k , which may be of independent interest. [ABSTRACT FROM AUTHOR]

The current air cargo loading plan handles the Air Cargo Palletization Problem (ACPP) and the Aircraft Weight and Balance Problem (WBP) separately, which has an impact on the optimization of the payload and the aircraft's center of gravity (CG). Thanks to improvements in computer processing power, the joint combinatorial optimization of ACPP and WBP is now feasible. Three integer linear programming models are proposed: a Bi-objective Optimization Model (BOM), a Combinatorial Optimization Model (COM), and an Improved Combinatorial Optimization Model (IOM). The objectives of the models are the maximum loading capacity and the lowest CG deviation from a specified target CG. The models also consider a wide range of restrictions in the actual packing and stowage procedures, such as volume, weight, loading position, aircraft balance, and other aspects of aircraft and unit load devices. Four scenarios with various conditional metrics for three models are solved for the B777F aircraft using Gurobi. The results of the computations demonstrate that the BOM has the fastest solution speed, but the CG deviation is the largest, and in several cases the CG deviation results are unacceptable. The COM has the longest solution time, which is difficult to tolerate in practice. Despite taking a little longer to solve computationally than the BOM, the IOM offers the best optimization solution. [ABSTRACT FROM AUTHOR]

With most Additive Manufacturing (AM) technology variants, build processes take place inside an internal enclosed build container, referred to as a 'build volume'. It has been demonstrated that the effectiveness with which this volume is filled with product geometries forms an important determinant of overall process efficiency in AM. For effective operations management, it is important to understand not only the problem faced, but also which methods have proved effective (or ineffective) for problems with these characteristics in the past. This research aims to facilitate this increased understanding. The build volume packing task can be formulated as a three-dimensional irregular packing (3DIP) problem, which is a combinatorial optimisation problem requiring the configuration of a set of arbitrary volumetric items. This paper reviews existing general cutting and packing taxonomies and provides a new specification which is more appropriate for classifying the problems encountered in AM. This comprises a clear-cut problem definition, a set of precise categorisation criteria for objectives and problem instances, and a simple notation. Furthermore, the paper establishes an improved terminology with terms that are familiar to, but not limited to, researchers and practitioners in the field of AM. Finally, this paper describes a new dataset to be used in the evaluation of existing and proposed computational solution methods for 3DIP problems encountered in AM and discusses the importance of this research for further underpinning work. [ABSTRACT FROM AUTHOR]

The current air cargo loading plan handles the Air Cargo Palletization Problem (ACPP) and the Aircraft Weight and Balance Problem (WBP) separately, which has an impact on the optimization of the payload and the aircraft’s center of gravity (CG). Thanks to improvements in computer processing power, the joint combinatorial optimization of ACPP and WBP is now feasible. Three integer linear programming models are proposed: a Bi-objective Optimization Model (BOM), a Combinatorial Optimization Model (COM), and an Improved Combinatorial Optimization Model (IOM). The objectives of the models are the maximum loading capacity and the lowest CG deviation from a specified target CG. The models also consider a wide range of restrictions in the actual packing and stowage procedures, such as volume, weight, loading position, aircraft balance, and other aspects of aircraft and unit load devices. Four scenarios with various conditional metrics for three models are solved for the B777F aircraft using Gurobi. The results of the computations demonstrate that the BOM has the fastest solution speed, but the CG deviation is the largest, and in several cases the CG deviation results are unacceptable. The COM has the longest solution time, which is difficult to tolerate in practice. Despite taking a little longer to solve computationally than the BOM, the IOM offers the best optimization solution.

Finding the conditions under which packing algorithms succeed or fail with respect to a set of test instances is crucial for understanding their strengths and weaknesses, and for automated packing algorithm selection. This paper tackles the important task of objective packing algorithm selection. A framework for understanding the relationship between critical features of packing problem instances and the performance of packing algorithms is proposed. The framework can be used to predict algorithm performance on previously unseen instances with high accuracy and can be applied to find predictions in other instances of cutting and packing problems. It can also be applied to determine the relative strengths and weaknesses of each algorithm within the instance space. The effectiveness of the framework is demonstrated using the two-dimensional strip packing problem as a case study. [ABSTRACT FROM AUTHOR]

This paper deals with the two-dimensional satellite module polygon packing problem. Based on the duality of material and space, it regards the polygon packing problem as a space allocation problem, which involves allocating the container space to the given polygons reasonably and efficiently. Ant colony’s labour division is essentially a kind of task allocation. Using this task allocation to achieve the space allocation in polygon packing problems, a flexible labour division approach (FLD) is proposed based on the response threshold model. According to the characteristics of space allocation in polygon packing problems, FLD designs three actions for polygons to occupy the container space. With the interaction between environmental stimulus and response threshold, each polygon takes an appropriate action to complete the space allocation and a layout that meets the requirements of satellite module layout is obtained. The results of standard test instances demonstrate the effectiveness of FLD when compared with self-organisation emergence algorithm. Moreover, experiments on the general polygon packing problem also show that FLD is competitive with other existing algorithms. [ABSTRACT FROM PUBLISHER]

Developing realistic three‐dimensional growth models for quasicrystals is a fundamental requirement. The present work employs classical molecular dynamics simulations to investigate the adsorption of Al on a close‐packed Al layer containing atomic vacancies. Simulation results show that the adsorbed Al atoms are located preferentially above and below the atomic vacancies in the close‐packed layer, and the results obtained from a one‐component system of atoms interacting via an interatomic pair potential for Al–Al appropriately reproduce the stacking motif seen in complex alloys such as the μ‐Al4Mn phase. The simulations also reveal the formation of a deformed icosahedron. These results provide new insights into the growth mechanism and origin of complex alloys and quasicrystals. [ABSTRACT FROM AUTHOR]

We study a general family of facility location problems defined on planar graphs and on the two-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the n O(k) time brute force algorithm of selecting k objects can be improved to n O(√ k) time. The algorithm is based on an idea that was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. We focus on the Voronoi diagram of a hypothetical solution of k objects, guess a balanced separator cycle of this Voronoi diagram to obtain a set that separates the solution in a balanced way, and then recurse on the resulting subproblems. [ABSTRACT FROM AUTHOR]

Green packaging is playing an increasingly important role in greening the supply chain. However, the issues that companies face when developing green packaging solutions for the transportation of products within supply chains are poorly understood. A case study of an automotive component manufacturer is presented that explores the complexity of the decisions that surround the decision of inter-organisational packaging design. Drawing upon the literature, legislation and the expert evaluation provided by the case organisation, it identifies the important criteria that influence packaging design and comprise customer requirements, legislation, operational and environmental concerns. This research finds that even though the company makes significant efforts to improve its environmental performance, operational concerns are most influential factors in the design of packaging. Initiatives that aim to improve the environmental performance of packaging are also constrained by external influences in the supply chain, such as customer pressure to adopt branded packaging systems and the inability to influence the design of incoming goods and material packaging. [ABSTRACT FROM PUBLISHER]

The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set. We develop a randomized (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 (Kesselheim et al. in SIAM J Comput 47(5):1939–1964, 2018). Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1/8.06 (Kesselheim et al. in SIAM J Comput 47(5):1939–1964, 2018). [ABSTRACT FROM AUTHOR]

In this paper we give an algorithm to round the floating point output of a semidefinite programming solver to a solution over the rationals or a quadratic extension of the rationals. This algorithm does not require the solution to be strictly feasible and works for large problems. We apply this to get sharp bounds for packing problems, and we use these sharp bounds to prove that certain optimal packing configurations are unique up to rotations. In particular, we show that the configuration coming from the E8 root lattice is the unique optimal code with minimal angular distance π/3 on the hemisphere in ℝ8, and we prove that the three-point bound for the (3, 8, ϑ)- spherical code, where ϑ is such that cos ϑ = (2√2 - 1)/7, is sharp by rounding to Q [ϑ2]. We also use our machinery to compute sharp upper bounds on the number of spheres that can be packed into a larger sphere. [ABSTRACT FROM AUTHOR]

Packing is one of the well-known problems in operation research, especially in production planning. The main objective of studying the packing problem is to reduce the wastes of cutting through optimization of packing of pieces. Packing is a kind of NP-hard problem that the precise methods are not able to solve it. In this paper, in order to achieve an optimal packing of Non-guillotine cutting problems, the meta-heuristic emerging Imperialist Competitive Algorithm was used and the results were compared with the output of the genetic algorithm, which is the typical algorithm in solving packing problems. To achieve better solutions, the parameters of all meta-heuristics were calibrated with Taguchi experiment method. The efficacy of the proposed approach was tested on a set of instances, taken from the literature, and the results of the proposed algorithm were tested statistically by ANOVA. The results of this study showed that the meta-heuristic emerging Imperialist Competitive algorithm is more efficient and faster in solving packing problems. Introduction: Packing problems are problems which are difficult or sometimes impossible to solve exactly. Researchers have provided many different solutions based on heuristic and meta-heuristic to approximately solve these problems. Materials and Methods: Imperialist Competitive Algorithm is a new evolutionaryoptimization method which is inspired by imperialisticcompetition Atashpaz-Gargari (2007). Like other evolutionary algorithms, it startswith an initial population which is called country and isdivided into two types of colonies and imperialists which,together, form empires. Imperialistic competition among theseempires forms the proposed evolutionary algorithm. Duringthis competition, weak empires collapse and powerful onestake possession of their colonies. Imperialistic competitionconverges to a state in which there exists only one empire andcolonies have the same cost function value as the imperialist.The pseudo code of Imperialist competitive algorithm is asfollows: 1) Select some random points on the function and initializethe empires. 2) Move the colonies toward their relevant imperialist (Assimilation). 3) Randomly change the position of some colonies (Revolution). 4) If there is a colony in an empire which has lower costthan the imperialist, exchange the positions of thatcolony and the imperialist. 5) Unite the similar empires. 6) Compute the total cost of all empires. 7) Pick the weakest colony (colonies) from the weakestempires and give it (them) to one of the empires (Imperialistic competition). 8) Eliminate the powerless empires. 9) If stop conditions satisfied, stop, if not go to 2. After dividing all colonies among imperialists and creatingthe initial empires, these colonies start moving toward theirrelevant imperialist state which is based on assimilationpolicy Results and Discussion: In this study, in order to achieve an optimal packing of non-guillotine cutting problems, at first the meta-heuristic algorithm of Imperialist Competitive Algorithm was used. Then the results were compared with the output of the genetic algorithm which is the typical algorithm in solving packing problems. The results showed that ICA had the better fitness function average than GA. Also, ICA needs less number of function evaluations. Therefore ICA is faster than GA in solving permutation packing problems. References Atashpaz-Gargari, E., & Lucas, C. (2007). "Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialistic competition". IEEE Congress on Evolutionary Computation, 4661-4667 Ebrahimi, S., & Payvandy, P. (2013). "Optimization of the Link Drive Mechanism in a Sewing Machine Using Imperialist Competitive Algorithm". International Journal of Clothing Science and Technology, 26(3), 247 – 260. Bluma, C., & Schmid, V. (2013). "Solving the 2D bin packing problem by means of a hybrid evolutionary algorithm". Procedia Computer Science, 18, 899 – 908.

This paper deals with strip packing metaheuristic algorithm selection using data mining techniques. Given a set of solved strip packing problem instances, the relationship between the instance characteristics and algorithm performance is learned and is used to predict the best algorithms to solve a new set of unseen problem instances. A framework capable of modelling this relationship for an automated packing algorithm selection is proposed. The effectiveness of the proposed framework is evaluated in the context of a large set of strip packing problem instances and the state-of-the-art strip packing algorithms. The results suggest a 91% accuracy in correctly identifying the best algorithm for a given instance. [ABSTRACT FROM AUTHOR]

We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those algorithms. We also demonstrate our framework by applying it to a variety of stochastic combinatorial optimization problems such as matching, matroid, and stable set problems. [ABSTRACT FROM AUTHOR]

This paper considers a real-world two-dimensional strip packing problem involving specific machinery constraints and actual cutting production industry requirements. To adapt the problem to a wider range of machinery characteristics, the design objective considers the minimisation of material length and the total number of cuts for guillotinable-type patterns. The number of cuts required for the cutting process is crucial for the life of the industrial machines and is an important aspect in determining the cost and efficiency of the cutting operation. In this paper we propose the application of evolutionary algorithms to address the multi-objective problem, for which numerous approaches to its single-objective formulation exist, but for which multi-objective approaches are almost non-existent. The multi-objective evolutionary algorithms applied provide a set of solutions offering a range of trade-offs between the two objectives from which clients can choose according to their needs. By considering both the length and number of cuts, they derive solutions with wastage levels similar to most previous approximations which just seek to optimise the overall length. [ABSTRACT FROM AUTHOR]

While semiconductors are being used in an increasing number of products, semiconductor manufacturers continually look for ways to make their processes more efficient. This paper will focus on an issue in the manufacturing process called the class-constrained lot-to-order matching problem (CLOMP), where individual lots of microprocessors are matched to customer orders, while seeking to optimize multiple objectives. Due to its complexity, the problem is decomposed into two stages - the first identifies which customer orders to fill while the second assigns specific lots to the chosen orders. We design an experiment with four first-stage sorting rules, four second-stage heuristics and two production cases. Based on our simulation results, this paper will recommend the first-stage sorting rule and second-stage heuristic which attain the best results with regards to our measures of effectiveness. [ABSTRACT FROM AUTHOR]

This paper proposes a new effective and robust algorithm for solving the classic NP-complete rectangle packing problem that is often encountered in various layout design work domains. The complexity and subjectivity in most layout design applications indicate the need for providing advanced design and analysis support to layout designers in order to facilitate the procurement of a superior solution in a timely manner. An automated system for providing efficient and easy ways of generating and analysing superior layout alternatives seems to be a logical choice in this direction. In this regard, various metaheuristics are known to be effective solution techniques. However, the efficiency of such techniques is largely determined by the efficiency and efficacy of the decoding placement algorithms employed. Here we propose an efficient and robust placement algorithm and compare it with some popular existing algorithms. Various quantitative fitness metrics and subjective evaluation of the aesthetic value of layout solutions by design experts are employed in our comparison regime. Comparative studies demonstrate the superiority of the proposed algorithm in terms of speed and robustness. Notably, the proposed algorithm consistently furnishes layout alternatives carrying relatively high aesthetic values. Such efficient and robust placement algorithms are expected to facilitate an efficient and effective utilization of resources in layout design applications and to stimulate future research in associated areas. [ABSTRACT FROM AUTHOR]

During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them constructive kernels with reasonably low explicit constants. To fill this gap, we recently presented [STACS 2014] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of vertices. In this article we enhance our framework to deal with packing problems, that is, problems whose solutions can be certified by collections of subgraphs of the input graph satisfying certain properties. F -Packing is a typical example: for a family F of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph G contains k vertex-disjoint subgraphs such that each of them contains a graph in F as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of F -Packing: for an integer ℓ ⩾ 1 , one aims at finding either minor-models that are pairwise at distance at least ℓ in G (ℓ - F -Packing), or such that each vertex in G belongs to at most ℓ minors-models (F -Packing with ℓ -Membership). Finally, we also provide linear kernels for the versions of these problems where one wants to pack subgraphs instead of minors. [ABSTRACT FROM AUTHOR]

Packing is one of the well-known problems in operation research, especially in production planning. The main objective of studying the packing problem is to reduce the wastes of cutting through optimization of packing of pieces. Packing is a kind of NP-hard problem that the precise methods are not able to solve it. In this paper, in order to achieve an optimal packing of Non-guillotine cutting problems, the meta-heuristic emerging Imperialist Competitive Algorithm was used and the results were compared with the output of the genetic algorithm, which is the typical algorithm in solving packing problems. To achieve better solutions, the parameters of all meta-heuristics were calibrated with Taguchi experiment method. The efficacy of the proposed approach was tested on a set of instances, taken from the literature, and the results of the proposed algorithm were tested statistically by ANOVA. The results of this study showed that the meta-heuristic emerging Imperialist Competitive algorithm is more efficient and faster in solving packing problems. [ABSTRACT FROM AUTHOR]