Search

The two-dimensional (2D) irregular packing problem is a combinatorial optimization problem with NP-complete characteristics, which is common in the production process of clothing, ships, and plate metals. The classic packing solution is a hybrid algorithm based on heuristic positioning and meta-heuristic sequencing, which has the problems of complex solving rules and high time cost. In this study, the similarity measurement method based on the twin neural network model is used to evaluate the similarity of pieces in the source task and the target task. The reusability evaluation of packing tasks is designed to select appropriate source task knowledge. The transfer operator is used to transfer the piece sequence knowledge from the source task to complete the reuse of packing knowledge in the target task. The bottom-left algorithm is improved to complete the placement of 2D irregular pieces. The computational experiments show that the proposed algorithm for the bin packing problem using knowledge reuse and improved heuristic (KRIH) has good robustness. The KRIH algorithm can obtain 8 equal or better results on 16 instances in a relatively short time compared with some classical heuristic algorithms, which has good application potential. [ABSTRACT FROM AUTHOR]

The Colored bin packing problem (CBPP) is a generalization of the Bin packing problem (BPP). The CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity, minimizing the number of used bins and satisfying the constraint that two items of the same color cannot be packed side by side in the same bin. In this article, we proposed an adaptation of BPP heuristics and new heuristics for the CBPP. Moreover, we propose a set of fast neighborhood search algorithms for CBPP. These neighborhoods are applied in a meta-heuristic approach based on the Variable neighborhood search (VNS) and a matheuristic approach that combines linear programming with the meta-heuristics VNS and Greedy randomized adaptive search (GRASP). The results indicate that our matheuristic is superior to VNS and that both approaches can find near-optimal solutions for a large number of instances, even for those with many items. [ABSTRACT FROM AUTHOR]

Many packing, routing, and knapsack problems can be expressed in terms of integer linear programming models based on set covering. These models have been exploited in a range of successful heuristics and exact techniques for tackling such problems. In this paper, we show that integer linear programming models based on set covering can be very useful for their use within an algorithm called "Construct, Merge, Solve & Adapt"(CMSA), which is a recent hybrid metaheuristic for solving combinatorial optimization problems. This is because most existing applications of CMSA are characterized by the use of an integer programming solver for solving reduced problem instances at each iteration. We present applications of CMSA to the variable-sized bin packing problem and to the electric vehicle routing problem with time windows and simultaneous pickups and deliveries. In both applications, CMSA based on a set covering model strongly outperforms CMSA when using an assignment-type model. Moreover, state-of-the-art results are obtained for both considered optimization problems. [ABSTRACT FROM AUTHOR]

Virtual machine placement (VMP) has a significant importance with respect to resource utilization in cloud data centers. Indeed, the optimized management of machine placement usually results in a significant reduction in energy consumption. VMP is a bin packing problem generalization, which is a well known hard combinatorial optimization problem. Besides being NP-hard, VMP is characterized by conflicting objectives and a noisy search space. Meta-heuristics, such as genetic algorithms, particle swarm optimization (PSO), cuckoo search (CS), tabu search and simulated annealing (SA) have been shown to be effective for this category of problems. This paper reports a performance comparison between SA, CS and PSO meta-heuristics to solve the VMP problem. In contrast to reported research work in this area, we study the performance behavior of these three meta-heuristics with respect to, not only the quality of solutions, but also the quality of the explored solution sub-space, in addition to the convergence speed towards reported solutions and the speed with which each meta-heuristic evolves towards the best reported optimized solution. Extensive simulations on randomly generated tests with sizes varying between 200 and 1000 virtual machine demands show that PSO achieves the best performance behavior with respect to all criteria. Moreover, for all tests, PSO produces a reduction of as much as 17% of the number of physical machines, 15% of the energy cost and 21% of the resource utilization of physical machines. [ABSTRACT FROM AUTHOR]

This paper presents theoretical and practical results for the bin packing problem with scenarios, a generalization of the classical bin packing problem which considers the presence of uncertain scenarios, of which only one is realized. For this problem, we propose approximation algorithms whose ratios are bounded by the square root of the number of scenarios times the approximation ratio for an algorithm for the vector bin packing problem. We also show how an asymptotic polynomial-time approximation scheme is derived when the number of scenarios is constant, that is, not a part of the input. As a practical study of the problem, we present a branch-and-price algorithm to solve an exponential set-cover model and a variable neighborhood search heuristic. Experiments show the competence of the branch-and-price in obtaining optimal solutions for about 59% of the instances considered, while the combined heuristic and branch-and-price optimally solved 62% of the instances considered. [ABSTRACT FROM AUTHOR]

We present a new generalization of the bin covering problem that is known to be a strongly NP-hard problem. In our generalization there is a positive constant Δ , and we are given a set of items each of which has a positive size. We would like to find a partition of the items into bins. We say that a bin is near exact covered if the total size of items packed into the bin is between 1 and 1 + Δ . Our goal is to maximize the number of near exact covered bins. If Δ = 0 or Δ > 0 is given as part of the input, our problem is shown here to have no approximation algorithm with a bounded asymptotic approximation ratio (assuming that P ≠ N P ). However, for the case where Δ > 0 is seen as a constant, we present an asymptotic fully polynomial time approximation scheme (AFPTAS) that is our main contribution. [ABSTRACT FROM AUTHOR]

To improve cargo loading efficiency and achieve diverse needs of companies for the loading process, this paper innovatively establishes a multiple objective mixed integer programming model for the three-dimensional multiple bin-size bin packing problem (3D-MBSBPP). The model is designed to maximize container space utilization rate and cargo load balance, minimize container usage costs, and incorporates some practical constraints. On this basis, we propose a novel dynamic feedback algorithm based on spatial corner fitness (SCF_DFA) to solve this model, which consists of three stages. Specifically, Stage 1 employs a heuristic algorithm based on spatial corner fitness to optimize the search of the remaining spaces. Stage 2 employs a container type selection algorithm to dynamically adjust and optimize container types. Stage 3 uses an improved genetic algorithm to improve the quality of the solutions of the first two stages. We demonstrate the effectiveness of the proposed algorithm through comparative experiments on benchmark instances, and apply it to solve the real-life instances for the 3D-MBSBPP. The results show that the proposed algorithm can make the average container space utilization rate reach 85.38%, which is 1.48% higher than that of baseline method, while the loading results obtained are more balanced, indicating the advantages of the SCF_DFA in solving 3D-MBSBPP. Furthermore, we conduct ablation experiments to confirm the effectiveness of each component within the algorithm. [ABSTRACT FROM AUTHOR]

The bin packing is a well-known NP-Hard problem in the domain of artificial intelligence, posing significant challenges in finding efficient solutions. Conversely, recent advancements in quantum technologies have shown promising potential for achieving substantial computational speedup, particularly in certain problem classes, such as combinatorial optimization. In this study, we introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation designed specifically for bin packing and suitable for quantum computation. QAL-BP utilizes the Augmented Lagrangian method to incorporate the bin packing constraints into the objective function while also facilitating an analytical estimation of heuristic, but empirically robust, penalty multipliers. This approach leads to a more versatile and generalizable model that eliminates the need for empirically calculating instance-dependent Lagrangian coefficients, a requirement commonly encountered in alternative QUBO formulations for similar problems. To assess the effectiveness of our proposed approach, we conduct experiments on a set of bin packing instances using a real Quantum Annealing device. Additionally, we compare the results with those obtained from two different classical solvers, namely simulated annealing and Gurobi. The experimental findings not only confirm the correctness of the proposed formulation, but also demonstrate the potential of quantum computation in effectively solving the bin packing problem, particularly as more reliable quantum technology becomes available. [ABSTRACT FROM AUTHOR]

In this paper we present an evolutionary heuristic for the offline two-dimensional variable-sized bin packing problem. In this problem we have to pack a set of rectangles into two-dimensional variable-sized rectangular bins. The bins are divided into types, and the bins in different types have different sizes and possibly different weights (costs). There are (sufficiently) many bins from each type, and any rectangle fits into at least one bin-type. The goal is to pack the rectangles into the bins without overlap, parallel to the sides, so that the total area of the used bins (or total cost) is minimized. Our algorithm is a hybrid heuristic. It uses two different techniques to generate the descendants: either estimation of distribution algorithm and sampling the resulting probability model, or applying the usual operators of evolutionary algorithms (selection, mutation). To pack the rectangles into the bins the algorithm uses the strategy of randomly choosing one of two placement heuristics, that pack always only one group (one to three) of rectangles. It improves the quality of the solutions with three local search procedures. The algorithm has been tested on benchmark instances from the literature and has been compared with other heuristics and metaheuristics. Our algorithm outperformed the previously published results. [ABSTRACT FROM AUTHOR]

Any collection of homothetic copies of some tetrahedron T r , whose total volume does not exceed one quarter of the volume of T r , can be packed into T r . [ABSTRACT FROM AUTHOR]

We consider the temporal bin packing problem with fire-ups (TBPP-FU), a branch of operations research recently introduced in multi-objective cloud computing. In this scenario, any item is equipped with a resource demand and a lifespan meaning that it requires the bin capacity only during that time interval. We then aim at finding a schedule minimizing a weighted sum of the total number of bins required and the number of switch-on processes (so-called fire-ups) caused during operation. So far, research on the TBPP-FU has mainly focused on exact approaches and their improvement by valid cuts or variable reduction techniques. Although these studies have revealed the problem considered here to be very difficult to cope with, theoretical contributions to heuristic solution methods have not yet been presented in the available literature. Hence, in this article we investigate the worst-case behavior of some approximation algorithms, ranging from classic online algorithms to a more sophisticated look-ahead heuristic specifically designed for the TBPP-FU. In addition, we theoretically study three heuristics the ideas of which are inspired by solution methods for generalized bin packing problems in the field of logistics. As a main contribution, we constructively show that the feasible solutions obtained by all these approaches can be arbitrarily bad. By doing so, we (i) identify a new open problem in cutting and packing, and (ii) establish another previously unknown difference between the classical TBPP and the extended problem with fire-ups, rendering the latter the more difficult problem even from a heuristic point of view. [ABSTRACT FROM AUTHOR]

We study bin-packing and lot-sizing decisions in an integrated way. Such a problem appears in several manufacturing settings where items first need to be cut and next assembled into final products. One of the main novelties of this research is the modeling of the complex setup operations in the cutting process, which is modeled using a bin-packing formulation. More specifically, we consider the operation regarding the insertion or removal of the knives in the cutting process. Since this operation depends on the number of items cut in the current cutting process and in the previous one, the number of insertions and removals is sequence-dependent. The setups in the lot-sizing problem related to the production of the final products are also sequence-dependent. To deal with such a problem, two compact formulations are proposed. The sequence-dependent setups in the bin-packing problem are modeled in two different ways: based on known constraints from the literature, and based on the idea of micro-periods and a phantom cutting process. Due to the dependency in the setups decisions, the resulting formulations are mixed-integer nonlinear mathematical models. In order to deal with the sequence-dependent cutting and production setups, different polynomial-sized sets of subtour elimination constraints are employed to the coupled problem. A computational study is conducted in order to analyze the impact of the proposed approaches to model sequence-dependent setups, as well as the different subtour elimination strategies to solve the coupled bin-packing and lot-sizing problem, via an automatic-Benders decomposition algorithm. [ABSTRACT FROM AUTHOR]

Irregular packing in e-commerce warehouses is a special case of a three-dimensional box packing problem (3DBPP). It is necessary to select the type and quantity of boxes and determine the location and orientation of the items to maximize the use of the loading space. In this paper, a spatial particle model of the 3DBPP for multiple boxes and irregular items is constructed using the three-dimensional (3D) point cloud and granulation method. In the model, the 3D point cloud is used to describe the shapes of irregular items, and the granulation method is used for the transformation from sparse and uneven point clouds to spatial particle convex hulls. In addition, we designed an empirical simulation algorithm (ESA) based on the combination of expert rules extracted in practical packing activities and empirical simulation, and an intelligent algorithm for 3DBPPs with irregular items combined with the framework of the deep Q network (DQN) algorithm in deep reinforcement learning. An instance generator is proposed based on industry data to generate realistic projects with representative attributes for the above two algorithms, such as types of boxes, irregular items, 3D spatial plane convex hulls, and spatially granular data. The numerical results show that the ESA can quickly obtain a high-quality packing scheme, and the intelligent DQN packing algorithm in deep reinforcement learning can avoid the limitation of expert rules and achieve a better scheme with a certain time for the training process. [ABSTRACT FROM AUTHOR]

A rose diagram is a representation that circularly organizes data with the bin width as the central angle. This diagram is widely used to display and summarize circular data. Some studies have proposed the selector of bin width based on data. However, only a few papers have discussed the property of these selectors from a statistical perspective. Thus, this study aims to provide a data-based bin width selector for rose diagrams using a statistical approach. We consider that the radius of the rose diagram is a nonparametric estimator of the square root of two times the circular density. We derive the mean integrated square error of the rose diagram and its optimal bin width and propose two new selectors: normal reference rule and biased cross-validation. We show that biased cross-validation converges to its optimizer. Additionally, we propose a polygon rose diagram to enhance the rose diagram. [ABSTRACT FROM AUTHOR]

This paper addresses the two-dimensional irregular bin packing problem, whose main aim is to allocate a given set of irregular pieces to larger rectangular containers (bins), while minimizing the number of bins required to contain all pieces. To solve the problem under study a dynamic hierarchical hyper-heuristic approach is proposed. The main idea of the hyper-heuristics is to search the space of low-level heuristics for solving computationally difficult problems. The proposed approach is "dynamic" since the low-level heuristic to be executed is chosen on the basis of the main characteristics of the instance to be solved. The term "hierarchical" is used to indicate the fact that the main hyper-heuristic can execute either simple heuristics or can run in a "recursive fashion" a hyper-heuristic. The developed solution strategy is evaluated empirically by performing extensive experiments on irregular packing benchmark instances. A comparison with the state-of-the-art approaches is also carried out. The computational results are very encouraging. [ABSTRACT FROM AUTHOR]

In Two-dimensional Bin Packing (2BP), we are given n rectangles as input and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. 2BP admits no APTAS and the current best approximation ratio is 1.406 by Bansal and Khan (ACM-SIAM symposium on discrete algorithms (SODA), pp 13–25, 2014. https://doi.org/10.1137/1.9781611973402.2). A well-studied variant of 2BP is Guillotine Two-dimensional Bin Packing (G2BP), where rectangles must be packed in such a way that every rectangle in the packing can be obtained by applying a sequence of end-to-end axis-parallel cuts, also called guillotine cuts. Bansal et al. (Symposium on foundations of computer science (FOCS). IEEE, pp 657–666, 2005. https://doi.org/10.1109/SFCS.2005.10) gave an APTAS for G2BP. Let λ be the smallest constant such that for every set I of items, the number of bins in the optimal solution to G2BP for I is upper bounded by λ opt (I) + c , where opt (I) is the number of bins in the optimal solution to 2BP for I and c is a constant. It is known that 4 / 3 ≤ λ ≤ 1.692 . Bansal and Khan (2014) conjectured that λ = 4 / 3 . The conjecture, if true, will imply a (4 / 3 + ε) -approximation algorithm for 2BP. Given a small constant δ > 0 , a rectangle is called large if both its height and width are at least δ , else it is called skewed. We make progress towards the conjecture by showing that λ = 4 / 3 when all input rectangles are skewed. We also give an APTAS for 2BP for skewed items, though general 2BP does not admit an APTAS. [ABSTRACT FROM AUTHOR]

Efficient packing of items into bins is a common daily task. Known as Bin Packing Problem, it has been intensively studied in the field of artificial intelligence, thanks to the wide interest from industry and logistics. Since decades, many variants have been proposed, with the three-dimensional Bin Packing Problem as the closest one to real-world use cases. We introduce a hybrid quantum-classical framework for solving real-world three-dimensional Bin Packing Problems (Q4RealBPP), considering different realistic characteristics, such as1) package and bin dimensions, (2) overweight restrictions, (3) affinities among item categories and (4) preferences for item ordering. Q4RealBPP permits the solving of real-world oriented instances of 3 dBPP, contemplating restrictions well appreciated by industrial and logistics sectors. [ABSTRACT FROM AUTHOR]

In the d-dimensional online bin packing problem, d-dimensional cubes of positive sizes no larger than 1 are presented one by one to be assigned to positions in d-dimensional unit cube bins. In this work, we provide improved upper bounds on the asymptotic competitive ratio for square and cube bin packing problems, where our bounds do not exceed 2.0885 and 2.5735 for square and cube packing, respectively. To achieve these results, we adapt and improve a previously designed harmonic-type algorithm, and apply a different method for defining weight functions. We detect deficiencies in the state-of-the-art results by providing counter-examples to the current best algorithms and their analysis, where the claimed bounds were 2.1187 for square packing and 2.6161 for cube packing. [ABSTRACT FROM AUTHOR]

Submissions of papers were open to the entire communities of Operations Research and Computer Science, and in particular from the participants to the International Conference ODS2020 on Optimization and Decision Science, held online on November 19, 2020. The main contribution of the paper I A constrained optimization model for the provision of services in a 5G network with multi-level cybersecurity investments i , by Cappello et al. ([3]), is a multi-tiered network-based optimization model, and a solution algorithm, for the provision of 5G services considering the security levels of each provider. The paper I Price of robustness optimization through demand forecasting with an application to waste management, i by Gentile et al. ([5]), studies a robust optimization approach for making effective decisions in the presence of different forms of uncertainty. [Extracted from the article]

We consider the two-bar charts packing problem generalizing the strongly NP-hard bin packing problem. We prove that the problem remains strongly NP-hard even if each two-bar chart has at least one bar higher than 1/2. If the first (or second) bar of each two-bar chart is higher than 1/2, we show that the O(n2)-time greedy algorithm with lexicographic ordering of two-bar charts constructs a packing of length at most OPT+1, where OPT is optimum, and present an O(n2.5)-time algorithm that constructs a packing of length at most 4/3 ・ OPT+2/3 in the NP-hard case where each two-bar chart has at least one bar higher than 1/2. [ABSTRACT FROM AUTHOR]

Cloud computing has become one of the most popular frameworks for big data processing and analysis. To have better performance, the data chunks and their corresponding process nodes must be near each other, which is known as data locality. Moreover, to meet the deadline constraints, the available processing power next to the data locations is crucial. Considering the time and resource constraints, designing an appropriate job scheduler is essential for the effective management of memory and processing capacity. These concerns coalesce into the problem of joint data placement and job scheduling with data locality and deadline constraints. In this paper, two kinds of job sets are determined, one with equal deadlines and the other one with various deadlines. The problem of joint data placement and job scheduling with a single deadline is formulated as the problem of bin packing with splittable items and cardinality constraints, which is strongly NP-hard. Moreover, this paper proposes the polynomial-time Meddal algorithm to find a feasible solution with a few processing nodes. Experiment results have shown that the proposed method is effective, with the number of required nodes reduced by 33 % when compared to the algorithms Cred and First Fit. [ABSTRACT FROM AUTHOR]

We study parallel online algorithms: For some fixed integer k, a collective of k parallel processes that perform online decisions on the same sequence of events forms a k-copy algorithm. For any given time and input sequence, the overall performance is determined by the best of the k individual total results. Problems of this type have been considered for online makespan minimization; they are also related to optimization with advice on future events, i.e., a number of bits available in advance. Parallel online algorithms are also of interest in practical scenarios in which redundancy is used for hedging against undesired outcomes. We develop Predictive Harmonic 3 (PH3), a relatively simple family of k-copy algorithms for the online Bin Packing Problem, whose joint competitive factor converges to 1.5 for increasing k. In particular, we show that k = 6 suffices to guarantee a factor of 1.5714 for PH3, which is better than 1.57829, the performance of the best known 1-copy algorithm Advanced Harmonic, while k = 11 suffices to achieve a factor of 1.5406, beating the known lower bound of 1.54278 for a single online algorithm. In the context of online optimization with advice, our approach implies that 4 bits suffice to achieve a factor better than this bound of 1.54278, which is considerably less than the previous bound of 15 bits. [ABSTRACT FROM AUTHOR]

The upcoming square kilometer array (SKA) is expected to produce humongous amount of data for undertaking H i science. We have developed an MPI-based Python pipeline to deal with the large data efficiently with the present computational resources. Our pipeline divides such large H i 21-cm spectral cubes into several small cubelets, and then processes them in parallel using publicly available H i source finder SoFiA-2. The pipeline also takes care of sources at the boundaries of the cubelets and also filters out false and redundant detections. By comapring with the true source catalog, we find that the detection efficiency depends on the SoFiA-2 parameters, such as the smoothing kernel size, linking length and threshold values. We find the optimal kernel size for all flux bins to be between 3–5 and 7–15 pixels, respectively, in the spatial and frequency directions. Comparing the recovered source parameters with the original values, we find that the output of SoFiA-2 is highly dependent on kernel sizes and a single choice of kernel is not sufficient for all types of H i galaxies. We also propose the use of alternative methods to SoFiA-2, which can be used in our pipeline to find sources more robustly. [ABSTRACT FROM AUTHOR]

Here, we focus on a generalized version of the strip packing problem; namely we have several open-end strips with different widths, and we wish to pack rectangular items into these strips without overlapping such that we have to minimize either the makespan (i.e. the top of the topmost item), or the total area used. We investigate the online variant of the problem, where the items are arriving one-by-one, and we have to make irrevocable decisions on their packing. A similar framework was proposed by Ye and Mei (On-line scheduling of parallel jobs in heterogeneous multiple clusters. Frontiers in algorithmics and algorithmic aspects in information and management, Springer, Berlin, pp 139–148, 2012. https://doi.org/10.1007/978-3-642-29700-7%5f13) for scheduling models, and they studied the absolute competitive ratio of their algorithm. Our contribution is to define a new objective function and several algorithms by combining so-called shelf algorithms with techniques taken from the areas of the variable-sized bin packing problem and scheduling. We analyzed the asymptotic competitive ratio of our algorithms. [ABSTRACT FROM AUTHOR]

We consider the two-bar charts packing problem which is a generalization of the strongly NP-hard bin packing problem and 2-D vector packing problem. We propose an O(n2.5)-time 16/11-approximation algorithm for packing two-bar charts when at least one bar of each two-bar chart has height more than 1/2 and an O(n2.5)-time 5/4-approximation algorithm for packing nonincreasing or nondecreasing two-bar charts when each two-bar chart has at least one bar higher than 1/2. [ABSTRACT FROM AUTHOR]

Not all products meet customers' quality expectations after the steelmaking process. Some of them, labelled as 'non-prime' products, are sold in a periodic online auction. These products need to be grouped into the smallest feasible number of bundles as homogeneous as possible, as this increases the attractiveness of the bundles and hence their selling prices. This results in a highly complex optimisation problem, also conditioned by other requirements, with large economic implications. It may be interpreted as a variant of the well-known bin packing problem. In this article, we formalise it mathematically by studying the real problem faced by a multinational in the steel industry. We also propose a structured, three-stage solution procedure: (i) initial division of the products according to their characteristics; (ii) cluster analysis; and (iii) allocation of products to bundles via optimisation methods. In the last stage, we implement three heuristic algorithms: FIFO, greedy, and distance-based. Building on previous works, we develop 80 test instances, which we use to compare the heuristics. We observe that the greedy algorithm generally outperforms its competitors; however, the distance-based one proves to be more appropriate for large sets of products. Last, we apply the proposed solution procedure to real-world datasets and discuss the benefits obtained by the organisation. [ABSTRACT FROM AUTHOR]

Edge computing plays a critical role in IoT as it potentially minimized the computation tasks response latency demanded by time-critical IoT applications. The growth of IoT users with high demanded computation power as well as ultra-low latency tasks may cause the performance degradation. One way to minimize the end-to-end (E2E) latency is to form horizontal edge federation (HEF) so that the computation resources can be shared with each participating edge node. Achieving ultra-low latency in HEF-IoT ecosystem involves setting two factor: resource allocation and task dispatching. This two factor interact with each other yet feasible solutions must provide satisfactory service level to meet latency constraints demanded by target applications. In this paper, we formulate it as E2E latency minimization problem and proposed a two-phase iterative (TPI) approach. The TPI method alternately determines optimal task dispatching and computation resource allocation. We exploit bin packing problem and, genetic algorithm (GA) to determine the edge nodes, and the required computation resources. The simulation results show that by using TPI approach, we can achieve more throughput, minimum E2E latency and optimum number of required edge nodes. [ABSTRACT FROM AUTHOR]

The energy consumption of large-scale data centers or server clusters is expected to grow significantly in the next couple of years contributing to up to 13% of the worldwide energy demand in 2030. As the involved processing units require a disproportional amount of energy when they are idle, underutilized, or overloaded, balancing the supply of and the demand for computing resources is a key issue to obtain energy-efficient server consolidations. Whereas traditional concepts mostly consider deterministic predictions of the future workloads or only aim at finding approximate solutions, in this article, we propose an exact approach to tackle the problem of assigning jobs with (not necessarily independent) stochastic characteristics to a minimal amount of servers subject to further practically relevant constraints. As a main contribution, the problem under consideration is reformulated as a stochastic bin packing problem with conflicts and modeled by an integer linear program. Finally, this new approach is tested on real-world instances obtained from a Google data center. [ABSTRACT FROM AUTHOR]

We present a new generalization of the extensible bin packing with unequal bin sizes problem. In our generalization the cost of exceeding the bin size (also known as the bin capacity) depends on the index of the bin and not only on the amount in which the size of the bin is exceeded. This generalization does not satisfy the assumptions on the cost function that were used to present the existing polynomial time approximation scheme (PTAS) for the extensible bin packing with unequal bin sizes problem. In this work, we show the existence of an efficient PTAS (EPTAS) for this new generalization and thus in particular we improve the earlier PTAS for the extensible bin packing with unequal bin sizes problem into an EPTAS. Our new scheme is based on using the shifting technique followed by a solution of a polynomial number of n-fold programming instances. In addition, we present an asymptotic fully polynomial time approximation scheme for the related bin packing type variant of the problem. [ABSTRACT FROM AUTHOR]

We tackle the online 3D bin packing problem (3D-BPP), a challenging yet practically useful variant of the classical bin packing problem. In this problem, the items are delivered to the agent without informing the full sequence information. The agent must directly pack these items into the target bin stably without changing their arrival order, and no further adjustment is permitted. Online 3D-BPP can be naturally formulated as a Markov decision process (MDP). We adopt deep reinforcement learning, in particular, the on-policy actor-critic framework, to solve this MDP with constrained action space. To learn a practically feasible packing policy, we propose three critical designs. First, we propose an online analysis of packing stability based on a novel stacking tree. It attains a high analysis accuracy while reducing the computational complexity from O(N2) to O(N log N), making it especially suited for reinforcement learning training. Second, we propose a decoupled packing policy learning for different dimensions of placement which enables high-resolution spatial discretization and hence high packing precision. Third, we introduce a reward function that dictates the robot to place items in a far-to-near order and therefore simplifies the collision avoidance in movement planning of the robotic arm. Furthermore, we provide a comprehensive discussion on several key implemental issues. The extensive evaluation demonstrates that our learned policy outperforms the state-of-the-art methods significantly and is practically usable for real-world applications. [ABSTRACT FROM AUTHOR]

We consider the Ordered Open End Bin Packing problem. Items of sizes in (0, 1] are presented one by one, to be assigned to bins in this order. An item can be assigned to any bin for which the current total size is strictly below 1. This means also that the bin can be overloaded by its last packed item. We improve lower and upper bounds on the asymptotic competitive ratio in the online case. Specifically, we design the first algorithm whose asymptotic competitive ratio is strictly below 2, and its value is close to the lower bound. This is in contrast to the best possible absolute competitive ratio, which is equal to 2. We also study the offline problem where the sequence of items is known in advance, while items are still assigned to bins based on their order in the sequence. For this scenario, we design an asymptotic polynomial time approximation scheme. [ABSTRACT FROM AUTHOR]

Although blind source separation of convolutive mixtures can be efficiently solved in the frequency domain, the problem of permutation ambiguity must be solved. Thus, this paper proposes an improved permutation algorithm. Firstly, the improved algorithm uses energy correlation of the separated signal to sort the signals of each frequency bin. Then, the reliability of the sorting of the signals on the frequency bin will be judged according to the threshold. The unreliable frequency bins will be corrected in time so that we can obtain the separated signal accurately, eventually. This algorithm effectively reduces sorting errors and error propagation, thereby improving the separation effect. BSS experiments are performed on the voice signals and radar signals under different convolutive mixing models. The simulation results show that the improved algorithm has better separation performance and higher robustness than the traditional permutation algorithms, which is reflected by the increasing signal to interference ratio of separated signals. [ABSTRACT FROM AUTHOR]

With the penetration of Network Function Virtualization (NFV), network functions, traditionally deployed as proprietary physical equipment like firewalls, Network Address Translations (NATs), are gradually being implemented as software and deployed on standardized hardware. One of the crucial challenges in this paradigm is how to place the software implemented network functions to minimize the number of used physical servers. In this paper, we study the problem of how to optimally place Virtual Network Functions (VNFs) in networks where it is allowed to migrate already placed VNFs to decrease used servers. We first formulate the offline problem as an Integer Linear Programming (ILP) problem, and then propose a semi-online algorithm to solve the online variant of the problem. We name the proposed algorithm Semi-onlIne Vnf plAcement (SIVA). In particular, SIVA is based on a bin packing algorithm that solves online bin packing problem while taking care of migrations. According to our theoretical analysis, SIVA migrates at most λ VNFs each step, and it has Asymptotic Competitive Ratio (ACR) of 3/2 if k → ∞ , where λ = k · | N | , k is a tunable parameter, and | N | is the the number of supported VNF types. We conduct extensive numerical simulations to evaluate the performances of SIVA. The experiment results validate the theoretical analysis and show that SIVA outperforms the state-of-the-art algorithms by achieving near-optimal performance with minor VNF migrations. [ABSTRACT FROM AUTHOR]

Best Fit is a well known online algorithm for the bin packing problem, where a collection of one-dimensional items has to be packed into a minimum number of unit-sized bins. In a seminal work, Kenyon [SODA 1996] introduced the (asymptotic) random order ratio as an alternative performance measure for online algorithms. Here, an adversary specifies the items, but the order of arrival is drawn uniformly at random. Kenyon's result establishes lower and upper bounds of 1.08 and 1.5, respectively, for the random order ratio of Best Fit. Although this type of analysis model became increasingly popular in the field of online algorithms, no progress has been made for the Best Fit algorithm after the result of Kenyon. We study the random order ratio of Best Fit and tighten the long-standing gap by establishing an improved lower bound of 1.10. For the case where all items are larger than 1/3, we show that the random order ratio converges quickly to 1.25. It is the existence of such large items that crucially determines the performance of Best Fit in the general case. Moreover, this case is closely related to the classical maximum-cardinality matching problem in the fully online model. As a side product, we show that Best Fit satisfies a monotonicity property on such instances, unlike in the general case. In addition, we initiate the study of the absolute random order ratio for this problem. In contrast to asymptotic ratios, absolute ratios must hold even for instances that can be packed into a small number of bins. We show that the absolute random order ratio of Best Fit is at least 1.3. For the case where all items are larger than 1/3, we derive upper and lower bounds of 21/16 and 1.2, respectively. [ABSTRACT FROM AUTHOR]

Problems involving the efficient arrangement of simple objects, as captured by bin packing and makespan scheduling, are fundamental tasks in combinatorial optimization. These are well understood in the traditional online and offline cases, but have been less well-studied when the volume of the input is truly massive, and cannot even be read into memory. This is captured by the streaming model of computation, where the aim is to approximate the cost of the solution in one pass over the data, using small space. As a result, streaming algorithms produce concise input summaries that approximately preserve the optimum value. We design the first efficient streaming algorithms for these fundamental problems in combinatorial optimization. For Bin Packing, we provide a streaming asymptotic (1 + ε)-approximation with O ~ 1 ε , where O ~ hides logarithmic factors. Moreover, such a space bound is essentially optimal. Our algorithm implies a streaming (d + ε)-approximation for Vector Bin Packing in d dimensions, running in space O ~ d ε . For the related Vector Scheduling problem, we show how to construct an input summary in space O ~ (d 2 ⋅ m / ε 2) that preserves the optimum value up to a factor of 2 − 1 m + ε , where m is the number of identical machines. [ABSTRACT FROM AUTHOR]

We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bounds. The values of previous lower bounds were approximately 1.5401 and 1.5403. [ABSTRACT FROM AUTHOR]

Enterprise cloud data centers consume a tremendous amount of energy due to the large number of physical machines (PMs). These PMs host a huge number of virtual machines (VMs), on which a vast number of applications are deployed. Existing research uses two separate layers to manage data center resources: application assignment to VMs, and VM placement to PMs, each of which is a bin packing problem. While this consecutive two-layer bin packing (Consec2LBP) makes the problems easier to solve, it also limits further improvement in the quality of solution. To address this issue, an integrated any colony optimization approach is proposed in this paper to deal with both layers simultaneously. It formulates the two-layer resource management into an integrated two-layer bin packing (Int2LBP) optimization problem. Then, an integrated first fit-decreasing (FFD) algorithm Int2LBP_FFD is proposed to solve this optimization problem. Using the result of Int2LBP_FFD as an initial solution, an integrated ant colony system (ACS) algorithm Int2LBP_ACS is further developed to improve the quality of solution. Simulation experiments are conducted to demonstrate the effectiveness of our integrated approach. [ABSTRACT FROM AUTHOR]

In this paper we present an evolutionary heuristic for the offline one-dimensional Bin Packing Problem. In this problem we have to pack a set of items into bins of the same capacity, and the objective is to minimize the number of bins used. Our algorithm is a hybrid evolutionary algorithm where an individual is a feasible solution, and it contains the description of the bins. The algorithm works without recombination; it uses two new mutation operators and improves the quality of the solutions with local search procedures. The mutation operators' work is based on a relative pair frequency matrix, and, based on this matrix, we know the frequency of every pair of items i.e. how often they are included in the same bin in the best solutions. The frequency matrix helps to pack items into subsets of items; these subsets are the bins in our problem. The algorithm was tested on well-known benchmark instances from the literature and was compared with both evolutionary and state-of-the-art algorithms. Our algorithm achieved a valuable result with the difficult hard28 test set, and in most of the test problems it reached the optimum. [ABSTRACT FROM AUTHOR]

This paper investigates the mother plate design (MPD) problem which is a typical problem in the production planning of steel plants. The MPD problem refers to a variant of the two-dimensional variable-sized bin packing problem in which the height of a bin is in a given finite set and the width of each bin is continuous in an interval. The problem is first formulated as a mixed integer nonlinear programming model and then linearized into a mixed integer programming model. We present a column generation-based (CG-based) algorithm to approximately solve the MPD problem, in which a height combination scheme is devised to decrease the dimensions of the pricing sub-problem. We present an accelerated CG (ACG) algorithm with improved performance which adopts two heuristic accelerating strategies in the pricing process. We use practical instances collected from a Chinese steel plant to test the performance of the proposed algorithms. The results indicate that the ACG algorithm is suitable for solving real-world instances. [ABSTRACT FROM AUTHOR]

This paper addresses a special bin packing problem in which each item can only be assigned to a subset of the bins. We name this problem as the restricted bin packing problem (RBPP). This paper is designed to explore the relationships of RBPP with classic NP-complete problems, and to resolve the restrictions of assignment through heuristic and meta-heuristic algorithms. A new heuristic algorithm named 'Max-fit Based on Zigzag Sorting with Retained Feasibility' is proposed. In this heuristic algorithm, a feasibility retaining rule is constructed to assure the assignment of every item; a zigzag sorting method is designed to improve the performance of the algorithm. Our heuristic algorithm is able to generate better results in comparison with existing heuristics. Greedy Randomized Adaptive Search Procedure (GRASP) and Simulated Annealing (SA) are exploited to obtain better solutions for RBPP. A new construction method based on cliques and zigzag sorting are built for GRASP and SA. The proposed methods are shown to have higher efficiency than traditional ones through numeric examples. [ABSTRACT FROM AUTHOR]

Counting and enumerating maximal and maximum independent sets are well-studied problems in graph theory. In this paper we introduce methods to count and enumerate maximal/maximum independent sets in threshold graphs and k-threshold graphs and improve former results for these problems. The results can be applied to combinatorial optimization problems, and in particular to different variations of the knapsack problem. As feasible solutions for instances of those problems correspond to independent sets in threshold graphs and k-threshold graphs, we obtain polynomial time results for special knapsack and multidimensional knapsack instances. Also, we show lower and upper bounds for the number of necessary bins in several bin packing problems. [ABSTRACT FROM AUTHOR]

We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ratio of 1 + ϵ for the number of bins, a relatively simple argument proves a lower bound of Ω (1 / ϵ) for the migration factor. We establish a nearly matching upper bound of O (1 / ϵ 4 log 1 / ϵ) using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items nand in 1 / ϵ . The previous best trade-off was for an asymptotic competitive ratio of 5 / 4 for the bins (rather than 1 + ϵ ) and needed an amortized number of O (log n) repackings (while in our scheme the number of repackings is independent of n and non-amortized). [ABSTRACT FROM AUTHOR]

The bin packing problem deals with packing items of sizes no larger than 1 into unit capacity bins. Here, we analyze a class of bin packing games where the cost of an item is 1 over the total number of items packed into its bin, which is a bin packing congestion game. We study strong equilibria and find the tight values of the SPoA and SPoS, that is, asymptotic approximation ratios of the worst and best strong equilibria. We show that these values are approximately 1.69103 and 1.611824, respectively. In particular, we observe that the two values are not equal, showing a difference from other known kinds of cost sharing approaches. [ABSTRACT FROM AUTHOR]

The consolidation of virtual machine (VM) is the strategy of efficient and intelligent use of cloud datacenters resources. One of the important subproblems of VM consolidation is VM placement problem. The main objective of VM placement problem is to minimize the number of running physical machines or hosts in cloud datacenters. This paper focuses on solving VM placement problem with respect to the available bandwidth which is formulated as variable sized bin packing problem. Moreover, a new bandwidth allocation policy is developed and hybridized with an improved variant of whale optimization algorithm (WOA) called improved Lévy based whale optimization algorithm. Cloudsim toolkit is used in order to test the validity of the proposed algorithm on 25 different data sets that generated randomly and compared with many optimization algorithms including: WOA, first fit, best fit, particle swarm optimization, genetic algorithm, and intelligent tuned harmony search. The obtained results are analyzed by Friedman test which indicates the prosperity of the proposed algorithm for minimizing the number of running physical machine. [ABSTRACT FROM AUTHOR]

We consider the one-dimensional skiving stock problem, also known as the dual bin packing problem, with the aim of maximizing the best known dual and proper dual gaps. We apply the methods of computational search of large gaps initially developed for the one-dimensional cutting stock problem, which is related to the bin packing problem. The best known dual gap is raised from 1.0476 to 1.1795. The proper dual gap is improved to 1.1319. We also apply a number of new heuristics developed for the skiving stock problem back to the cutting stock problem, raising the largest known proper gap from 1.0625 to 1.1. [ABSTRACT FROM AUTHOR]

Scheduling over scenarios is one of the latest approaches in modelling scheduling problems including uncertainty. However, to the best of our knowledge, scenarios have never been applied to the bin packing problem, so here we introduce the bin packing problem with scenarios. In this model, we have a list of items with sizes between 0 and 1, and each item is assigned to one or more scenarios. In reality, the items of only one scenario will occur, but this chosen scenario is unknown at the time of packing, so the algorithms have to examine all scenarios. This means that the items have to be packed into bins such that for any scenario, the total size of the items in this scenario is at most 1 in each bin. The objective of the standard bin packing problem is to minimize the number of bins. Here, we introduce some extensions of the objective function to the scenario based model, and we present our competitive analysis of some online bin packing algorithms adapted to scenarios. [ABSTRACT FROM AUTHOR]

In this paper, a multiobjective dynamic bin packing problem for storing cooling objects is introduced along with a metaheuristic designed to work well in mixed-variable environments. The dynamic bin packing problem is based on cookie production at a bakery, where cookies arrive in batches at a cooling rack with limited capacity and are packed into boxes with three competing goals. The first is to minimize the number of boxes used. The second objective is to minimize the average initial heat of each box, and the third is to minimize the maximum time until the boxes can be moved to the storefront. The metaheuristic developed here incorporated greedy heuristics into an adaptive evolutionary framework with partial decomposition into clusters of solutions for the crossover operator. The new metaheuristic was applied to a variety benchmark bin packing problems and to a small and large version of the dynamic bin packing problem. It performed as well as other metaheuristics in the benchmark problems and produced more diverse solutions in the dynamic problems. It performed better overall in the small dynamic problem, but its performance could not be proven to be better or worse in the large dynamic problem. [ABSTRACT FROM AUTHOR]

We consider the one-dimensional skiving stock problem which is strongly related to the dual bin packing problem: find the maximum number of objects, each having a length of at least L, that can be constructed by connecting a given supply of m∈N smaller item lengths l1,…,lm with availabilities b1,…,bm. For this NP-hard discrete optimization problem, the (additive integrality) gap, i.e., the difference between the optimal objective values of the continuous relaxation and the skiving stock problem itself, is known to be strictly less than 3 / 2 if li∣L is assumed for all items, hereinafter referred to as the divisible case. Within this framework, we derive sufficient conditions that ensure the integer round-down property, i.e., a gap smaller than one, of a given instance. As a main contribution, we present improved upper bounds for the gap (of special subclasses) of the divisible case by means of combinatorial and algorithmic approaches. In a final step, possible generalizations of the introduced concepts are discussed. Altogether, the results presented in this paper give strong evidence that 22 / 21 represents the best possible upper bound for the gap of divisible case instances. [ABSTRACT FROM AUTHOR]

Bin packing problem (BPP) is a classical combinatorial optimization problem widely used in a wide range of fields. The main aim of this paper is to propose a new variant of whale optimization algorithm named improved Lévy-based whale optimization algorithm (ILWOA). The proposed ILWOA adapts it to search the combinatorial search space of BPP problems. The performance of ILWOA is evaluated through two experiments on benchmarks with varying difficulty and BPP case studies. The experimental results confirm the prosperity of the proposed algorithm in proficiency to find the optimal solution and convergence speed. Further, the obtained results are discussed and analyzed according to the problem size. [ABSTRACT FROM AUTHOR]

Bin packing with fragmentable items is a variant of the classic bin packing problem where items may be cut into smaller fragments. The objective is to minimize the number of item fragments, or equivalently, to minimize the number of cuts, for a given number of bins. Models based on packing fragmentable items are useful for representing finite shared resources. In this article, we present improvements to approximation and metaheuristic algorithms to obtain an optimality-preserving optimization algorithm with polynomial complexity, worst-case performance guarantees and parametrizable running time. We also present a new family of fast lower bounds and prove their worst-case performance ratios. We evaluate the performance and quality of the algorithm and the best lower bound through a series of computational experiments on representative problem instances. For the studied problem sets, one consisting of 180 problems with up to 20 items and another consisting of 450 problems with up to 1024 items, the lower bound performs no worse than 5 / 6. For the first problem set, the algorithm found an optimal solution in 92 % of all 1800 runs. For the second problem set, the algorithm found an optimal solution in 99 % of all 4500 runs. No run lasted longer than 220 ms. [ABSTRACT FROM AUTHOR]