Search

This paper studies the constrained two-dimensional non-guillotine cutting problem with defects, in which a set of items of a specific size is cut from a large rectangular sheet with defective areas, with the number of each type of cut item cannot exceed a specified quantity. The objective is to maximise the total value of the cut items. We propose a decomposition approach to address the problem. The process involves decomposing the original problem into a master problem and a subproblem. The master problem is formulated as a one-dimensional contiguous bin packing problem, while the subproblem is an x-Check problem to identify a two-dimensional packing that does not lead to any overlap. The x-Check problem is effectively addressed by using an integer linear programming model. When the x-Check problem proves infeasible, cuts are added to the master problem, and the iteration is repeated until the x-Check finds a feasible solution. Furthermore, we introduce several novel techniques, including valid inequalities, preprocessing techniques, and lifting the cut methods to improve the performance of the algorithm. Extensive computational results show that our method can quickly find the optimal solution for the 5450 instances in the literature. [ABSTRACT FROM AUTHOR]

We consider the allocation of m balls (jobs) into n bins (servers). In the standard Two-Choice process, at each step t = 1, 2, . . ., m we first sample two randomly chosen bins, compare their two loads and then place a ball in the least loaded bin. It is well-known that for any m x n, this results in a gap (difference between the maximum and average load) of log2 logn + T(1) (with high probability). In this work, we consider Two-Choice in different settings with noisy load comparisons. One key setting involves an adaptive adversary whose power is limited by some threshold N. In each step, such adversary can determine the result of any load comparison between two bins whose loads differ by at most, while if the load difference is greater than, the comparison is correct. For this adversarial setting, we first prove that for anym x n the gap is O(1 + logn) with high probability. Then through a refined analysiswe prove that if x logn, then for anym x n the gap is O(1 log 1 ·log logn). For constant values of 1, this generalizes the heavily loaded analysis of [19, 61] for the Two-Choice process, and establishes that asymptotically the same gap bound holds even if load comparisons among "similarly loaded" bins are wrong. Finally, we complement these upper bounds with tight lower bounds, which establish an interesting phase transition on how the parameter 1 impacts the gap. The analysis also applies to settings with outdated and delayed information. For example, for the setting of [18] where balls are allocated in consecutive batches of size b = n, we present an improved and tight gap bound of T(log n log log n). This bound also extends for a range of values of b and applies to a relaxed setting where the reported load of a bin can be any load value from the last b steps. [ABSTRACT FROM AUTHOR]

Renting servers in the cloud is a generalization of the bin packing problem, motivated by job allocation to servers in cloud computing applications. Jobs arrive in an online manner, and need to be assigned to servers; their duration and size are known at the time of arrival. There is an infinite supply of identical servers, each having one unit of computational capacity per unit of time. A server can be rented at any time and continues to be rented until all jobs assigned to it finish. The cost of an assignment is the sum of durations of rental periods of all servers. The goal is to assign jobs to servers to minimize the overall cost while satisfying server capacity constraints. We focus on analyzing two natural algorithms, NextFit and FirstFit , for the case of jobs of equal duration. It is known that the competitive ratio of NextFit and FirstFit are at most 3 and 4 respectively for this case. We prove a tight bound of 2 on the competitive ratio of NextFit. For FirstFit , we establish a lower bound of ≈ 2. 519 on the competitive ratio, even when jobs have only two distinct arrival times 0 and t. Using the weight function technique, we show that this bound is almost tight when there are only two arrival times; we obtain an upper bound of 2.565 on the asymptotic competitive ratio of FirstFit. In fact, we show an upper bound of 168 131 (1 + t) on the asymptotic competitive ratio for any t > 0. 559. For the case when jobs have arrival times 0 and 1 and duration 2, we show a lower bound of ≈ 1. 89 and an upper bound of 2 on the strict competitive ratio of FirstFit. Finally, we show an upper bound of 3 / 2 on the competitive ratio of long-running uniform servers. [ABSTRACT FROM AUTHOR]

Motivated by a transit line planning problem in transportation systems, we investigate the following capacitated assignment problem under a budget constraint. Our model involves L bins and P items. Each bin l has a utilization cost c l and an n l -dimensional capacity vector. Each item p has an n l -dimensional binary weight vector r l p , where the 1s in r l p (if any) appear in consecutive positions, and its assignment to bin l yields a reward v l p. The objective is to maximize total rewards through an assignment that satisfies three constraints: (i) the total weights of assigned items do not violate any bin's capacity; (ii) each item is assigned to at most one open bin; and (iii) the overall utilization costs remain within a total budget B. We propose the first randomized rounding algorithm with a constant approximation ratio for this problem. We then apply our framework to the motivating transit line planning problem, presenting corresponding models and conducting numerical experiments using real-world data. Our results demonstrate significant improvements over previous approaches in addressing this critical transportation challenge. [ABSTRACT FROM AUTHOR]

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]

We use computer simulations to investigate the effects of the tip diameter of an electrostatic force microscope (EFM) operating at a constant force on the extraction of the growth exponent β during film growing in a one-dimensional substrate. Laplace's equation is solved in the EFM simulation using the finite element method to determine the electrostatic force between the tip and the film interface. Importantly, for EFM tips with sufficiently large apex diameters, the topographies calculated with EFM and those computed with the transformed mean height profile (TMHP) method, where the interface is divided into bins of the same tip diameter size and the average height within each bin is used to transform the original interface, are almost identical. This was shown in the context of lattice models of the Kardar–Parisi–Zhang (KPZ) and Villain–Lai–Das–Sarma (VLDS) classes. The global roughness of the film surface, W , scales with the diameter of the EFM tip, ε , as W / a = (ε / a) α g [ Ψ ] , where a is the lattice parameter, α is the KPZ/VLDS roughness exponent, and g is a universal scaling function of the argument Ψ ≡ t / (ε / a) z , where t and z are the reduced time of deposition and the KPZ/VLDS dynamic exponent, respectively. These results provide a limit for ε from which a KPZ/VLDS growth exponent can be reliably determined with EFM at a constant force. When the EFM tip diameter is larger than the surface correlation length, a misleading effective growth exponent consistent with uncorrelated growth is found. [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]

The bin packing problem is a classical problem widely existing in practical applications, such as shipping, warehousing and manufacturing industries. Whereas current research mainly focuses on reducing packing costs by optimizing the packing scheme, this study explores a novel approach by redesigning the bin sizes to fit the items ready to be packed. Specifically, this study considers a general three-dimensional open dimension problem (3D-ODP) where all dimensions, i.e. length, width and height, of a number of heterogeneous bin types are unknown and need to be decided. Based on the designed bin types, the corresponding packing scheme with minimal total costs is optimized, which is referred to as a three-dimensional multiple-bin-size bin packing problem (3D-MBSBPP). The combination of 3D-ODP and 3D-MBSBPP is redefined as a three-dimensional bin design and packing problem (3D-BDPP), for which a two-layer heuristic is developed. It consists of an outer heuristic framework (i.e. genetic algorithm or differential evolution algorithm) to design bin types, and an inner deterministic constructive heuristic (i.e. placement algorithm) to generate an effective solution for the 3D-MBSBPP. Extensive simulation tests on the classical benchmark and a case study derived from an e-commerce company are conducted to verify the algorithms and deduce managerial insights. [ABSTRACT FROM AUTHOR]

This work presents a knowledge discovery approach through Causal Bayesian Networks for understanding the conditions under which the performance of an optimization algorithm can be affected by the characteristics of the instances of a combinatorial optimization problem (COP). We introduce a case study for the causal analysis of the performance of two state-of-the-art algorithms for the one-dimensional Bin Packing Problem (BPP). We meticulously selected the set of features associated with the parameters that define the instances of the problem. Subsequently, we evaluated the algorithmic performance on instances with distinct features. Our analysis scrutinizes both instance features and algorithm performance, aiming to identify causes influencing the performance of the algorithms. The proposed study successfully identifies specific values affecting algorithmic effectiveness and efficiency, revealing shared causes within some value ranges across both algorithms. The knowledge generated establishes a robust foundation for future research, enabling predictions of algorithmic performance, as well as the selection and design of heuristic strategies for improving the performance in the most difficult instances. The causal analysis employed in this study did not require specific configurations, making it an invaluable tool for analyzing the performance of different algorithms in other COPs. [ABSTRACT FROM AUTHOR]

Cutting and Packing problems have been recognized as a sub-discipline of operation research for more than half a century. Such problems are involved in a range of circumstances such as pallet loading, wood or glass cutting, strip packing, and positioning problems. The focus of this study is on 2D rectangular strip packing problems in which rectangle items are not oriented and guillotine constraint is not considered aiming to pack all these items without overlapping into an open-ended bin called a strip of fixed width while the objective is obtaining the minimum total height of cutting. The main aim of this paper is to introduce two proposed heuristics for solving the problem under study. The two heuristics are improved versions of the known Best Fit heuristics, Tower Checker Best Fit (TCBF) and Waste Priority Best Fit (WPBF). The performance of the proposed heuristics is tested using well-known benchmark problems. The computational analysis of the results shows that the proposed heuristics can generate near-optimal solutions to large-scale problems. In addition, the performance of the heuristics outperforms other well-known heuristics from literature by 3%. [ABSTRACT FROM AUTHOR]

Weather radar is an active remote sensing device used to monitor the full lifecycle changes in severe convective weather with high spatial and temporal resolution. Effective radar calibration is a crucial foundation for ensuring the high-quality application of observational data. This paper utilizes a UAV platform equipped with a high-precision RTK system and standard metal spheres to study the principles and methods of metal sphere calibration, constructing a complete calibration process and calibration accuracy evaluation metrics. Additionally, a collocated radar comparison observation experiment was conducted for cross-validation, and metal sphere calibration tests were performed on problematic radars. The experimental results indicate the following: (1) The combined application of a high-precision RTK system and a laser range camera can provide real-time position information on the metal sphere, improving the efficiency of radar target acquisition. (2) The calibration method based on UAV-suspended metal spheres can periodically conduct the quantitative calibration of Z and ZDR, achieving calibration accuracies within 0.5 dB and 0.2 dB, respectively, and supports the qualitative inspection of key parameters such as beamwidth and pulse width. (3) During field tests, a high success rate "coarse adjustment + fine adjustment + staring" sphere-finding technique was established, based on automatic switching between RHI, PPI, and FIX scanning modes. This method directs the UAV to adjust the metal sphere to the center of the radar distance bin, reducing the impact of uneven beam filling and bin crossing, ensuring the accuracy of scattering characteristic measurements. [ABSTRACT FROM AUTHOR]

This paper introduces the Color Histogram Contouring (CHC) method, a new training-less approach to object detection that emphasizes the distinctive features in chrominance components. By building a chrominance-rich feature vector with a bin size of 1, the proposed CHC method exploits the precise information in chrominance features without increasing bin sizes, which can lead to false detections. This feature vector demonstrates invariance to lighting changes and is designed to mimic the opponent color axes used by the human visual system. The proposed CHC algorithm iterates over non-zero histogram bins of unique color features in the model, creating a feature vector for each, and emphasizes those matching in both the scene and model histograms. When both model and scene histograms for these unique features align, it ensures the presence of the model in the scene image. Extensive experiments across various scenarios show that the proposed CHC technique outperforms the benchmark training-less Swain and Ballard method and the algorithm of Viola and Jones. Additionally, a comparative experiment with the state-of-the-art You Only Look Once (YOLO) technique reveals that the proposed CHC technique surpasses YOLO in scenarios with limited training data, highlighting a significant advancement in training-less object detection. This approach offers a valuable addition to computer vision, providing an effective training-less solution for real-time autonomous robot localization and mapping in unknown environments. [ABSTRACT FROM AUTHOR]

Given a large set U where each item a∈ U has weight w(a), we want to estimate the total weight \(W=\sum _{a∈ U} w(a)\) to within factor of 1± ɛ with some constant probability > 1/2. Since n=|U| is large, we want to do this without looking at the entire set U. In the traditional setting in which we are allowed to sample elements from U uniformly, sampling Ω (n) items is necessary to provide any non-trivial guarantee on the estimate. Therefore, we investigate this problem in different settings: in the proportional setting we can sample items with probabilities proportional to their weights, and in the hybrid setting we can sample both proportionally and uniformly. These settings have applications, for example, in sublinear-time algorithms and distribution testing. Sum estimation in the proportional and hybrid setting has been considered before by Motwani, Panigrahy, and Xu [ICALP, 2007]. In their article, they give both upper and lower bounds in terms of n. Their bounds are near-matching in terms of n, but not in terms of ɛ. In this article, we improve both their upper and lower bounds. Our bounds are matching up to constant factors in both settings, in terms of both n and ɛ. No lower bounds with dependency on ɛ were known previously. In the proportional setting, we improve their \(\tilde{O}(\sqrt {n}/ɛ ^{7/2})\) algorithm to \(O(\sqrt {n}/ɛ)\). In the hybrid setting, we improve \(\tilde{O}(\sqrt [3]{n}/ ɛ ^{9/2})\) to \(O(\sqrt [3]{n}/ɛ ^{4/3})\). Our algorithms are also significantly simpler and do not have large constant factors. We then investigate the previously unexplored scenario in which n is not known to the algorithm. In this case, we obtain a \(O(\sqrt {n}/ɛ + \log n / ɛ ^2)\) algorithm for the proportional setting, and a \(O(\sqrt {n}/ɛ)\) algorithm for the hybrid setting. This means that in the proportional setting, we may remove the need for advice without greatly increasing the complexity of the problem, while there is a major difference in the hybrid setting. We prove that this difference in the hybrid setting is necessary, by showing a matching lower bound. Our algorithms have applications in the area of sublinear-time graph algorithms. Consider a large graph G=(V, E) and the task of (1 ± ɛ)-approximating |E|. We consider the (standard) settings where we can sample uniformly from E or from both E and V. This relates to sum estimation as follows: we set U = V and the weights to be equal to the degrees. Uniform sampling then corresponds to sampling vertices uniformly. Proportional sampling can be simulated by taking a random edge and picking one of its endpoints at random. If we can only sample uniformly from E, then our results immediately give a \(O(\sqrt {|V|} / ɛ)\) algorithm. When we may sample both from E and V, our results imply an algorithm with complexity \(O(\sqrt [3]{|V|}/ɛ ^{4/3})\). Surprisingly, one of our subroutines provides an (1 ± ɛ)-approximation of |E| using \(\tilde{O}(d/ɛ ^2)\) expected samples, where d is the average degree, under the mild assumption that at least a constant fraction of vertices are non-isolated. This subroutine works in the setting where we can sample uniformly from both V and E. We find this remarkable since it is O(1/ɛ2) for sparse graphs. [ABSTRACT FROM AUTHOR]

This paper introduces the three‐dimensional case picking problem (3D‐CPP) and proposes a multistart biased‐randomized algorithm (BRA) to solve it. The 3D‐CPP combines two important topics in modern warehouse logistics: the pallet loading problem and the routing of pickers in manual warehouses. The proposed optimization procedure aims at minimizing the overall distance traveled by the pickers, and is achieved by combining a routing problem (i.e., the order in which picking positions are visited) with a loading problem (i.e., the way in which cases are placed onto the pallet). We also consider additional constraints regarding the weight, vertical support, and strength of the cases. In order to solve this problem, we first propose a constructive heuristic which combines routing and packing procedures. This initial heuristic is then extended into a multistart BRA by employing a skewed probability distribution to introduce a certain degree of randomness during the solution‐construction process. A series of computational experiments allow us to assess the quality of the proposed approach, through a comparison with other algorithms as well as using real‐life data provided by an industrial partner. [ABSTRACT FROM AUTHOR]

Due to the competitive nature of the construction industry, the efficiency of requirement analysis is important in enhancing client satisfaction and a company's reputation. For example, determining the optimal configuration of panels (generally called panelization) that form the structure of a building is one aspect of cost estimation. However, existing methods typically rely on rule-based approaches that may lead to suboptimal material usage, particularly in complex designs featuring angled walls and openings. Such inefficiency can increase costs and environmental impact due to unnecessary material waste. To address these challenges, this research proposes a Panelization Algorithm for Architectural Designs, referred to as PAAD, which utilizes a genetic evolutionary strategy built on the 2D bin packing problem. This method is designed to balance between strict adherence to manufacturing constraints and the objective of optimizing material usage. PAAD starts with multiple potential solutions within the predefined problem space, facilitating dynamic exploration of panel configurations. It approaches structural rules as flexible constraints, making necessary corrections in post-processing, and through iterative developments, the algorithm refines panel sets to minimize material use. The methodology is validated through an analysis against an industry implementation and expert-derived solutions, highlighting PAAD's ability to surpass existing results and reduce the need for manual corrections. Additionally, to motivate future research, a synthetic data generator, the architectural drawing encodings used, and a preliminary interface are also introduced. This not only highlights the algorithm's practical applicability but also encourages its use in real-world scenarios. [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]

Given a non-decreasing sequence S = (s 1 , s 2 , ... , s k) of positive integers, an S -packing coloring of a graph G is a partition of the vertex set of G into k subsets { V 1 , V 2 , ... , V k } such that for each 1 ≤ i ≤ k , the distance between any two distinct vertices u and v in V i is at least s i + 1. In this paper, we study the problem of S -packing coloring of cubic Halin graphs, and we prove that every cubic Halin graph is (1 , 1 , 2 , 3) -packing colorable. In addition, we prove that such graphs are (1 , 2 , 2 , 2 , 2 , 2) -packing colorable. [ABSTRACT FROM AUTHOR]

We consider proof complexity in light of the unusual binary encoding of certain combinatorial principles. We contrast this proof complexity with the normal unary encoding in several refutation systems, based on Resolution and Sherali--Adams. We first consider Res(s), which is an extension of Resolution working on s-DNFs (Disjunctive Normal Form formulas). We prove an exponential lower bound of n \Omega (k)/\mathrm{d}(s) for the size of refutations of the binary version of the k-Clique Principle in Res(s), where s=o((log log n) 1/3) and d(s) is a doubly exponential function. Our result improves that of Lauria et al., who proved a similar lower bound for Res(1), i.e., Resolution. For the k-Clique and other principles we study, we show how lower bounds in Resolution for the unary version follow from lower bounds in Res(log n) for the binary version, so we start a systematic study of the complexity of proofs in Resolution-based systems for families of contradictions given in the binary encoding. We go on to consider the binary version of the (weak) Pigeonhole Principle Bin PHPmn. We prove that for any \delta, \epsilon >0, Bin PHPmn requires refutations of size 2n1 \delta in Res(s) for s =O(log 1 2 \epsilon n). Our lower bound cannot be improved substantially with the same method since for m\geq 2 \surd n\mathrm{l}\mathrm{o}\mathrm{g} n we can prove there are 2O(\surd n\mathrm{l}\mathrm{o}\mathrm{g} n) size refutations of Bin PHPmn in Res(log n). This is a consequence of the same upper bound for the unary weak Pigeonhole Principle of Buss and Pitassi. We contrast unary versus binary encoding in the Sherali--Adams (SA) refutation system where we prove lower bounds for both rank and size. For the unary encoding of the Pigeonhole Principle and the Ordering Principle, it is known that linear rank is required for refutations in SA, although both admit refutations of polynomial size. We prove that the binary encoding of the (weak) Pigeonhole Principle Bin PHPmn requires exponentially sized (in n) SA refutations, whereas the binary encoding of the Ordering Principle admits logarithmic rank, polynomially sized SA refutations. We continue by considering a natural refutation system we call "SA+Squares," which is intermediate between SA and Lasserre (Sum-of-Squares). This has been studied under the name static-LS\infty + by Grigoriev et al. In this system, the unary encoding of the Linear Ordering Principle LOPn requires O(n) rank while the unary encoding of the Pigeonhole Principle becomes constant rank. Since Potechin has shown that the rank of LOPn in Lasserre is O(\surd nlog n), we uncover an almost quadratic separation between SA+Squares and Lasserre in terms of rank. Grigoriev et al. noted that the unary Pigeonhole Principle has rank 2 in SA+Squares and therefore polynomial size. Since we show the same applies to the binary Bin PHPn+1 n, we deduce an exponential separation for size between SA and SA+Squares. [ABSTRACT FROM AUTHOR]

Let V n (d) denote the least number, such that every collection of n d-cubes with total volume 1 in d-dimensional (Euclidean) space can be packed parallelly into some d-box of volume V n (d) . We show that V 3 (d) = r 1 − d d if d ≥ 11 and V 3 (d) = 1 r + 1 r d + 1 r − r d + 1 if 2 ≤ d ≤ 10 , where r is the only solution of the equation 2 (d − 1) k d + d k d − 1 = 1 on 2 2 , 1 and (k + 1) d (1 − k) d − 1 d k 2 + d + k − 1 = k d d k d + 1 + d k d + k d + 1 on 2 2 , 1 , respectively. The maximum volume is achieved by hypercubes with edges x, y, z, such that x = 2 r d + 1 − 1 / d , y = z = r x if d ≥ 11 , and x = r d + (1 r − r) d + 1 − 1 / d , y = r x , z = (1 r − r) x if 2 ≤ d ≤ 10 . We also proved that only for dimensions less than 11 are there two different maximum packings, and for all dimensions greater than 10, the maximum packing has the same two smallest cubes. [ABSTRACT FROM AUTHOR]

Packing irregular objects composed by generalized spheres is considered. A generalized sphere is defined by an arbitrary norm. For three classes of packing problems, balance, homothetic and sparse packing, the corresponding new (generalized) models are formulated. Non-overlapping and containment conditions for irregular objects composed by generalized spheres are presented. It is demonstrated that these formulations can be stated for any norm. Different geometrical shapes can be treated in the same way by simply selecting a suitable norm. The approach is applied to generalized spheres defined by Lp norms and their compositions. Numerical solutions of small problem instances obtained by the global solver BARON are provided for two-dimensional objects composed by spheres defined in Lp norms to demonstrate the potential of the approach for a wide range of engineering optimization problems. [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]

Over the last decades, Structure from Motion (or image orientation) has been widely studied in the fields of photogrammetry and computer vision, mainly thanks to its feasibility for dealing with various image datasets (such as crowdsourced or UAV images). However, due to the fact that images are becoming easy to obtain, nowadays, it is challenging to deal with large scale of datasets, wherein the feature matching and pose-graph generation are the key limitations in terms of time efficiency. In this work, we proposed an efficient method to accelerate the generation of correspondences and two-view geometries. Specifically, based on some already estimated two-view geometries, unknown two-view geometries can be computed via A* algorithm. Then, the corresponding feature matching can be perform in a guided way using an epiploar-hash bins that is derived from the estimated two-view epipolar geometries. The experimental results demonstrated that, our method can improve the speed of generating pose-graph by 3–4 times comparing to two popular packages (colmap and OpenMVG) and is also faster than one SOTA method of Barath et al., (2021), yet the results of SfM are typically on par with them and reprojection error of our works are even better. [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]

The online 3D bin packing problem(3D-BPP) is widely used in the logistics industry and is of great practical significance for promoting the intelligent transformation of the industry. The heuristic algorithm relies too much on manual experience to formulate more perfect packing rules. In recent years, many scholars solve 3D-BPP via deep reinforcement learning(DRL) algorithms. However, they ignore many skills used in manual packing, one of the most important skill is workers put the item aside if the item is packed improperly. Inspired by this skill, we propose a DRL algorithm with a buffer zone. Firstly, we define the wasted space and the buffer zone. And then, we integrate them into the DRL algorithm framework. Importantly, we compare the bin utilization with di erent thresholds of wasted space and di erent buffer zone sizes. Experimental results show that our algorithm outperforms existing heuristic algorithms and DRL algorithms. [ABSTRACT FROM AUTHOR]

Background: Delirium, a common occurrence in clinical work, can be divided into three subtypes according to Diagnostic and Statistical Manual of Mental Disorders, 5 th Edition (DSM-5). Each subtype has its special significance and focus. As the primary caregivers and observer of delirious patients, nurses should be able to quickly and accurately indentify each subtype. Therefore, it is necessary to clarify nurses' assessment ability of delirium subtypes. However, there is currently no suitable questionnaire available for investigating nurses' assessment ability of delirium subtypes. Objective: To develop a scientifically validated questionnaire for assessing nursing assessment ability of delirium subtypes based on Knowledge-Attitude-Practice(KAP) Model. Methods: The questionnaire was conducted from October 2021 to February 2022 to assess the KAP status of nurses the regarding delirium subtype. A two-round Delphi Method was employed to revise the draft questionnaire, ensuring the importance and rationality of each item. Ten experts specializing in critically ill patients, clinical nursing, and nursing management were invited from seven provinces in China for the Delphi process. Additionally, we validated the reliability and validity of the questionnaire. Results: The return rate in the first and second rounds were 83% and 100%, respectively. The individual authority coefficients for the two rounds of correspondence ranged from 0.787 to 0.987, while the overall authority coefficient of experts was 0.866. Kendall's coefficient of coordination for the importance scores were found to be 0.192 and 0.156, respectively, whereas those for rationality scores were calculated as 0.149 and 0.141, respectively. Notably, all mean values of importance and rationality scores in the two rounds were exceeded a threshold of 4.10 across both rounds of assessment with coefficient variations (CV) ranging from 0.00 to 0.19 for importance ratings and 0.00 to 0.16 for rationality ratings, both of which were <0.25. Experts proposed modifications to eleven items while introducing four new ones into consideration during this process; thus ensuring that reliability and validity standards were met by the final questionnaire design which consists of a total of thirty-seven items distributed across four dimensions: delirium subtype-related knowledge, assessment attitude, assessment practice, and knowledge source–thereby establishing its clinical relevance as a reliable scientific instrument. Conclusion: The development process is both scientific and theoretical, encompassing reliable expert correspondence results and a diverse range of question formats. As thus, effectively captures the current landscape of delirium subtypes assessment among clinical nurses from multiple perspectives, including knowledge level and source, attitude, assessment behavior, and assessment barriers. It offers comprehensive and detailed insights. [ABSTRACT FROM AUTHOR]

This paper studies the assignment problem of multi product assembly jobs to days. The problem aims to minimize the amount of overtime while avoiding assembly delays for jobs that can be fragmented into smaller sub-tasks. When sequencedependent setup times are negligible, the problem considered transforms into the bin packing problem with restricted item fragmentation where jobs represent items and days stand for bins. We present a mixed integer programming model of the problem by extending earlier formulations in the literature. Computational experiments show that the mathematical model obtained optimal solutions for majority of instances tested within reasonable computation times. [ABSTRACT FROM AUTHOR]

We introduce a new class of balanced allocation processes which are primarily characterized by "filling" underloaded bins. A prototypical example is the Packing process: At each round we only take one bin sample, and if the load is below the average load, then we place as many balls until the average load is reached; otherwise, we place only one ball. We prove that for any process in this class the gap between the maximum and average load is \scrO (log n) w.h.p. for any number of balls m 1. For the Packing process, we also provide a matching lower bound. Additionally, we prove that the Packing process is sample efficient in the sense that the expected number of balls allocated per sample is strictly greater than one. Finally, we also demonstrate that the upper bound of \scrO (log n) on the gap can be extended to the Memory process studied by Mitzenmacher, Prabhakar, and Shah [43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, BC, Canada, 2002, pp. 799--808]. [ABSTRACT FROM AUTHOR]

The rectangular packing problem has been extensively studied over the years due to its wide application in industry. However, most of the research efforts are devoted to positioning techniques of the rectangles for various problem variants, the efficient implementation of the packing procedure is relatively less studied. In this paper, we propose an efficient constructive algorithm for the rectangular packing problem with rotations. We design a preprocess procedure with four data structures to store the information used for item selection. The gaps on the skyline are categorized into three types according to their associated edges for the placement procedure, during which the item is searched and packed in a descending order of the fitness value. The entire constructive phase takes a time complexity of O(nlogn). For the packing improvement phase, we optimize the packing through random perturbation on the sequence and orientation of the item. Three classes of stochastic problems are generated ranging from small-scale to extra-large-scale, the recorded running time confirms the efficiency of the proposed algorithm. We also test the proposed algorithm on the benchmark problem C21, N13, NT, Babu and CX, the computational results show that it delivers a good performance. [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]

The one-dimensional cutting-stock problem (1D-CSP) consists of obtaining a set of items of different lengths from stocks of one or different lengths, where the minimization of waste is one of the main objectives to be achieved. This problem arises in several industries like wood, glass, and paper, among others similar. Different approaches have been designed to deal with this problem ranging from exact algorithms to hybrid methods of heuristics or metaheuristics. The African Buffalo Optimization (ABO) algorithm is used in this work to address the 1D-CSP. This algorithm has been recently introduced to solve combinatorial problems such as travel salesman and bin packing problems. A procedure was designed to improve the search by taking advantage of the location of the buffaloes just before it is needed to restart the herd, with the aim of not to losing the advance reached in the search. Different instances from the literature were used to test the algorithm. The results show that the developed method is competitive in waste minimization against other heuristics, metaheuristics, and hybrid approaches. [ABSTRACT FROM AUTHOR]

This work presents a knowledge discovery approach through Causal Bayesian Networks for understanding the conditions under which the performance of an optimization algorithm can be affected by the characteristics of the instances of a combinatorial optimization problem (COP). We introduce a case study for the causal analysis of the performance of two state-of-the-art algorithms for the one-dimensional Bin Packing Problem (BPP). We meticulously selected the set of features associated with the parameters that define the instances of the problem. Subsequently, we evaluated the algorithmic performance on instances with distinct features. Our analysis scrutinizes both instance features and algorithm performance, aiming to identify causes influencing the performance of the algorithms. The proposed study successfully identifies specific values affecting algorithmic effectiveness and efficiency, revealing shared causes within some value ranges across both algorithms. The knowledge generated establishes a robust foundation for future research, enabling predictions of algorithmic performance, as well as the selection and design of heuristic strategies for improving the performance in the most difficult instances. The causal analysis employed in this study did not require specific configurations, making it an invaluable tool for analyzing the performance of different algorithms in other COPs.

We consider the bin packing problem with d different item sizes si and item multiplicities ai, where all numbers are given in binary encoding. This problem formulation is also known as the one-dimensional cutting stock problem. In this work, we provide an algorithm that, for constant d, solves bin packing in polynomial time. This was an open problem for all d ≥ 3. In fact, for constant d our algorithm solves the following problem in polynomial time: Given two d-dimensional polytopes P and Q, find the smallest number of integer points in P whose sum lies in Q. Our approach also applies to high multiplicity scheduling problems in which the number of copies of each job type is given in binary encoding and each type comes with certain parameters such as release dates, processing times, and deadlines.We show that a variety of high multiplicity scheduling problems can be solved in polynomial time if the number of job types is constant. [ABSTRACT FROM AUTHOR]

This document is a special issue of the journal Mathematics dedicated to recent advances in discrete optimization and scheduling. The issue includes 10 papers covering a range of topics such as batch loading and scheduling, optimization algorithms, scheduling surgeries, routing problems, and mathematical models for simplification. The papers present various approaches and algorithms for solving these problems, and they have been reviewed by experts in the field. The authors express their gratitude to the contributors, reviewers, and editorial staff, and hope that the readers will find stimulating ideas for further research in this area. [Extracted from the article]

In the Bin Packing problem one is given n items with weights w(1),. . . ,w(n) and m bins with capacities c1, . . ., cm. The goal is to partition the items into sets S1, . . . ,Sm such that w(Sj 0 such that an instance of Bin Packing with m bins can be solved in O (2(1 y m)n) randomized time. Before our work, such improved algorithms were not known even for m= 4. A key step in our approach is the following new result in Littlewood--Offord theory on the additive combinatorics of subset Σ: For every γ > 0 there exists an >0 such that if | { X n{ 1, . . . ,n}: w(X) =v} | 2(1)n for some v, then { w(X) :X { 1, . . . ,n\} | &#947n. [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]