Search

Bin packing problem (BPP) is one of the fastest-growing research issues within the field of combinatorial optimization. Over the last years, several studies carried out various BPP variants, mathematical models, and proposed methods to the BPPs. The classical BPP consists of packing a set of rectangular items in a minimum number of rectangular bins while respecting some constraints.Throughout the years, an improved typology was introduced by Wäscher et al. (2007), providing an excellent instrument for the organization and categorization criteria that defined the problem categories different from those of Dyckhoff (1990). Several early literature reviews have been conducted on various aspects of related packing problem variants.The contribution of this paper is to provide a comprehensive and refined taxonomy intended for BPPs. In addition to that, it is an up-to-date review based on a chronological taxonomy of the literature and depicts further research horizons.This systematic review allowed us to identify other characteristics and constraints, based on Wäscher's original ideas, mainly distinguished according to real cases studies. The detailed analysis provides a valuable framework for understanding the research gaps for future studies that should be acknowledged while proposing and solving new extensions. Note: The addresses of second and third authors have been corrected online. [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]

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]

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]

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]

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]

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]

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]

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]

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(Sjmn) notation omits factors polynomial in the input size). In this paper, we show that for every m N there exists a constant Σm > 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]

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]

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]

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]

Many algorithms that were developed for solving three-dimensional bin packing problems use generic data for either experiments or evaluation. However, none of these datasets became accepted for benchmarking 3D bin packing algorithms throughout the community. To close this gap, this paper presents the benchmarking dataset for robotic bin packing problems (BED-BPP), which is based on realistic data. We show the variety of the dataset by elaborating an n-gram analysis. Besides, we propose an evaluation function, which contains a stability check that uses rigid body simulation. We demonstrated the application of our dataset on four different approaches, which we integrated in our software environment. [ABSTRACT FROM AUTHOR]

Manufacturing systems need to be resilient and self-organizing to adapt to unexpected disruptions, such as product changes or rapid order, in supply chain changes while increasing the automation level of robotized logistics processes to cope with the lack of human experts. Deep Reinforcement Learning is a potential solution to solve more complex problems by introducing artificial neural networks in Reinforcement Learning. In this paper, a game engine was used for Deep Reinforcement Learning training, which allows visualization of view learning and result processes more intuitively than other tools, as well as a physical engine for a more realistic problem-solving environment. The present research demonstrates that a Deep Reinforcement Learning model can effectively address the real-time sequential 3D bin packing problem by utilizing a game engine to visualize the environment. The results indicate that this approach holds promise for tackling complex logistical challenges in dynamic settings. [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]

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]

The bin packing problem has a wide range of applications in industry. With the upgrade of the task difficulty, the traditional 2d rectangular layout algorithm can no longer meet the needs of modern industry, such as express packing task and exoplanet ore collection task. The express or ore samples come in heterogeneous shapes so they cannot all be treated as rectangular pieces. In this paper, we propose a three-stage method called covering, corner-searching and occupying (C,S&O) to solve the two-dimensional multishape part packing problem. The objective of the packing problem variant is to ensure maximum use of the raw material and minimize the trim loss. The algorithm cannot make use of information about the sequence of future objects that are going to arrive, only knowing the shape and size of the coming one, and the coming part must be packed into the bin immediately after its arrival without buffering or readjusting. The method of C,S&O hybridizes the idea of "gold corners, silver edges and grass belly" in the Chinese game Go and the method of finding picture corners in machine vision. In the first stage, the rectangular bin and the coming part are transformed into matrix representation, and generating the position matrix that indicates possible ways of packing the part into the bin. In the second stage, the suitable layout position of the coming part is obtained using machine vision image processing technology for reference. The third stage is calculating the environment matching degree to determine the current optimal placement orientation. In order to facilitate the display of the simulation results, only three shapes of parts are considered in the simulation, rectangle, circle and triangle. The experimental results show the effectiveness of this method. Consulting the literature, it is found that this paper is the first to propose a layout method for multishape manufacturing parts. [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]

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]

In this paper three heuristic algorithms using the Divide-and-Conquer paradigm are developed and assessed for three integer optimizations problems: Multidimensional Knapsack Problem (d-KP), Bin Packing Problem (BPP) and Travelling Salesman Problem (TSP). For each case, the algorithm is introduced, together with the design of numerical experiments, in order to empirically establish its performance from both points of view: its computational time and its numerical accuracy. [ABSTRACT FROM AUTHOR]

The low-energy task scheduling of cloud computing systems is a key issue in the field of cloud computing. Nevertheless, existing works on task scheduling lack consideration of the conflict relationship between tasks and focus on heuristic and other approximate algorithms. Thus, solving the problem of minimizing energy consumption with antiaffinity constraints between tasks and designing an efficient exact algorithm for task scheduling is a major challenge. This paper abstracts the problem into a multidimensional bin packing model with conflict constraints. The model is decomposed by the Lagrange relaxation principle and Dantzig–Wolfe decomposition principle. Moreover, we propose an accurate algorithm based on branch-and-price. The algorithm benefits from a new initial solution generation scheme based on maximum cliques and dominant resource proportion, and a multipattern branching strategy. The efficiency of the proposed branch-and-price algorithm is verified by a number of numerical experiments. [ABSTRACT FROM AUTHOR]

Robots are widely used in present day situations. Since a robot consists of number of systems with different mechanisms, it needs to be planned and programmed systematically. Discrete Mathematics helps us in designing and functioning of a robotic system. For instance Robotic arm is a type of linkage and the study of which is a part of Discrete Geometry. Scheduling tasks to be completed by a set of machines use the concept of Bin-packing problem, which is a part of Discrete Optimization. Discussing functions like these, motion and path planning of the robotic system is the main concern of any industry to adapt new and modern technologies in its functioning. Literature surveys reveal that there a worldwide attempts to develop robotic systems with minimum errors and maximum efficiency. This Paper includes the usage of the Concepts of Discrete Mathematics to have a path planning for a Robotic System to work with high efficiency. [ABSTRACT FROM AUTHOR]

This paper is devoted to a class of singularly perturbed nonlinear Schrödinger systems defined on a smooth bounded domain in R N (N = 2 , 3). We use the Lyapunov–Schmidt reduction method to construct synchronized vector solutions with multiple spikes both on the boundary and in the interior of the domain. For each vector solution that has been constructed, we point out that the interior spikes locate near sphere packing points in the domain, and the boundary spikes locate near the critical points of the mean curvature function related to the boundary of the domain. [ABSTRACT FROM AUTHOR]

International Journal of Technology 12(2) 228-231 (2021) International Journal of Technology http://ijtech.eng.ui.ac.id Managing Cross-Sectoral Coordination in Accelerating the Sustainable Development Agenda Mohammed Ali Berawi 1* 1 Faculty of Engineering, Universitas Indonesia, Kampus UI Depok, Depok 16424, Indonesia Building on my previous editorial notes on sustainable development themes, I would like to expand our discussion on how the concept of cross-sectoral coordination can be a booster for the sustainable development agenda. Science and technology development plays a significant role in achieving sustainable development by improving the efficiency and effectiveness of new and more sustainable approaches to development. [Extracted from the article]

This paper introduces a novel method for online 3-D bin packing, which is a strongly NP-hard problem, based on a space splitting and merging technique. In this scenario, the incoming box is unknown and must be immediately packed. The problem has many applications in industries that use manipulators to automate the packing process. The main idea of the approach is to divide the bin into spaces. These spaces are then categorized into one of two types of data structures: main and secondary data structures. Each node in the main data structure holds the information of a space that can be used to fit a new box. Each node in the secondary data structure holds the information of a space that cannot be used to place a box. The search algorithm based on these two data structures reduces the required search effort and simplifies the organizing and editing of the data structure. The experimental results demonstrate that the proposed method can achieve a packed volume ratio of up to 83% in the case of multiple bins being used. The position of a placed box can be found within milliseconds. [ABSTRACT FROM AUTHOR]

Synchrophasor estimation was mostly used in transmission systems in the past, and it is difficult to directly apply an existing synchrophasor algorithm to a distribution system with a more complex structure and environment. A synchrophasor estimation algorithm with a high accuracy and fast response speed is required to complete the calculation of the phasor in the face of the complex and changeable power signal of a distribution network. Therefore, an enhanced all-phase discrete Fourier transform (e-apDFT) algorithm is proposed for a distribution system in this paper, and the algorithm is deployed in a phasor measurement unit (PMU) prototype based on digital signal processing (DSP). Aiming to solve the problem of the accuracy of the traditional apDFT being reduced when the response speed is fast due to the influence of a dense spectrum, the existing algorithm is improved through iteratively compensating the spectral interferences to the main bin produced by adjacent bins. The experimental results show that the e-apDFT algorithm still has a fast response speed and that its estimation accuracy is much better than that of the traditional apDFTs in the presence of adjacent harmonic components. The proposed algorithm also complies with the IEEE standards for P-class PMUs. [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]

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]

In recent years, the volume of spatial data has rapidly grown, so it is crucial to process them in an efficient manner. The level of parallel processing in big data platforms such as Hadoop and Spark is determined by partitioning the dataset. A common approach is to split the data into chunks based on the number of bytes. While this approach works well for text-based batch processing, in many cases, it is preferable to take advantage of the structured information contained in the dataset (e.g., spatial coordinates) to plan data partitioning. In view of the huge amount of data and the impossibility of quickly establishing partitions, this paper designs a method for approximate partition boundary solving, which divides the data space into multiple non-overlapping symmetric bins and samples each bin, making the probability density of the sampling set bounded by the deviation of the probability density of the original data. The sampling set is read into the memory at one time for calculation, and the established partition boundary satisfies the partition threshold-setting. Only a few boundary adjustment operations are required, which greatly shortens the partition time. In this paper, the method proposed in the paper is tested on the synthetic dataset, the bus trajectory dataset, and six common spatial partitioning methods (Grid, Z-curve, H-curve, STR, Kd-tree, and R*-Grove) are selected for comparison. The results show that the symmetric bin sampling method can describe the spatial data distribution well and can be directly used for partition boundary division. [ABSTRACT FROM AUTHOR]

Packing problems, also known as nesting problems or bin packing problems, are classic and popular NP-hard problems with high computational complexity. Inspired by classic reinforcement learning (RL), we established a mathematical model for two-dimensional (2D) irregular-piece packing combined with characteristics of 2D irregular pieces. An RL algorithm based on Monte Carlo learning (MC), Q-learning, and Sarsa-learning is proposed in this paper to solve a 2D irregular-piece packing problem. Additionally, mechanisms of reward–return and strategy-update based on piece packing were designed. Finally, the standard test case of irregular pieces was used for experimental testing to analyze the optimization effect of the algorithm. The experimental results show that the proposed algorithm can successfully realize packing of 2D irregular pieces. A similar or better optimization effect can be obtained compared to some classical heuristic algorithms. The proposed algorithm is an early attempt to use machine learning to solve 2D irregular packing problems. On the one hand, our hybrid RL algorithm can provide a basis for subsequent deep reinforcement learning (DRL) to solve packing problems, which has far-reaching theoretical significance. On the other hand, it has practical significance for improving the utilization rate of raw materials and broadening the application field of machine learning. [ABSTRACT FROM AUTHOR]

Ship–infrastructure cooperation, i.e., infrastructure scheduling, is significant for optimizing the utilization of spatial-temporal resources of infrastructures and improving the efficiency and safety of waterborne transportation systems. This paper carries out a systematic review of the scheduling problems of the infrastructures in waterborne transportation systems, including locks, terminals, berths, and waterway intersections. The infrastructure scheduling problems are linked to the classical optimization problems, and a generalized infrastructure scheduling problem is formulated. For lock scheduling, the ship placement sub-problem aims at minimizing the number of lockages, which is a kind of classic 2D bin packing problem; the lockage scheduling sub-problem deals with chamber assignment and lockage operation planning, which is modeled as a single or parallel machine scheduling problem. For berth and terminal scheduling, the idea of queuing theory (for discrete terminal) and 2D bin packing (for continuous terminal) are usually applied. Most research aims at minimizing the waiting time of ships and focuses on the continuous dynamic terminal scheduling problems. As a special infrastructure, the waterway intersection receives little attention. Most research focuses on traffic conflicts and capacity problems. Future research directions are provided based on the review results and problems of infrastructure scheduling in practice. [ABSTRACT FROM AUTHOR]

Cloud computing has been studied and used extensively in many scenarios for its nearly unlimited resources and X as a service model. To reduce the latency for accessing the remote cloud data centers, small data centers or cloudlets are deployed near end-users, which is also called edge computing. In this paper, we mainly focus on the efficient scheduling of distributed simulation tasks in collaborative cloud and edge environments. Since simulation tasks are usually tightly coupled with each other by sending many messages and the status of tasks and hosts may also change frequently, it is essentially a dynamic bin-packing problem. Unfortunately, popular methods, such as meta-heuristics, and accurate algorithms are time-consuming and cannot deal with the dynamic changes of tasks and hosts efficiently. In this paper, we present Pool, an incremental flow-based scheduler, to minimize the overall communication cost of all tasks in a reasonable time span with the consideration of migration cost of task. After formulating such a scheduling problem as a min-cost max-flow (MCMF) problem, incremental MCMF algorithms are adopted to accelerate the procedure of calculating an optimal flow and heuristic scheduling algorithm, with the awareness of task migration cost, designed to assign tasks. Simulation experiments on Alibaba cluster trace show that Pool can schedule all of the tasks efficiently and is almost 5.8 times faster than the baseline method when few tasks and hosts change in the small problem scale. [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]

In this paper, we propose a generalisation of the bin packing problem, obtained by adding precedences between items that can assume heterogeneous non-negative integer values. Such generalisation also models the well-known Simple Assembly Line Balancing Problem of type I. To solve the problem, we propose a simple and effective iterated local search algorithm that integrates in an innovative way of constructive procedures and neighbourhood structures to guide the search to local optimal solutions. Moreover, we apply some preprocessing procedures and adapt classical lower bounds from the literature. Extensive computational experiments on benchmark instances suggest that the developed algorithm is able to generate good quality solutions in a reasonable computational time. [ABSTRACT FROM AUTHOR]

Many industrial processes require the nesting of 2D profiles prior to the cutting, or stamping, of components from raw sheet material. Despite decades of sustained academic effort, algorithmic solutions are still sub-optimal and produce results that can frequently be improved by manual inspection. However, the Internet offers the prospect of novel ‘human-in-the-loop’ approaches to nesting problems that uses online workers to produce packing efficiencies beyond the reach of current CAM packages. To investigate the feasibility of such an approach, this paper reports on the speed and efficiency of online workers engaged in the interactive nesting of six standard benchmark data-sets. To ensure the results accurately characterise the diverse educational and social backgrounds of the many different labour forces available online, the study has been conducted with subjects based in both Indian IT service (i.e. Rural BPOs) centres and a network of homeworkers in Northern Scotland. The results (i.e. time and packing efficiency) of the human workers are contrasted with both the baseline performance of a commercial CAM package and recent research results. The paper concludes that online workers could consistently achieve packing efficiencies roughly 4% higher than the commercial based-line established by the project. Beyond characterising the abilities of online workers to nest components, the results also make a contribution to the development of algorithmic solutions by reporting new solutions to the benchmark problems and demonstrating methods for assessing the packing strategy employed by the best workers. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of automating the definition of feasible pallets configurations. This issue is crucial for the competitiveness of logistic companies and is still one of the most difficult problems in internal logistics. In fact, it requires the fast solution of a three-dimensional Bin Packing Problem (3D-BPP) with additional logistic specifications that are fundamental in real applications. To this aim, we propose a matheuristics that, given a set of items, provides feasible pallets configurations that satisfy the practical requirements of items’ grouping by logistic features, load bearing, stability, height homogeneity, overhang as well as weight limits, and robotized layer picking. The proposed matheuristics combines a mixed integer linear programming (MILP) formulation of the 3D-Single Bin-Size BPP (3D-SBSBPP) and a layer building heuristics. In particular, the feasible pallets configurations are obtained by sequentially solving two MILP sub-problems: the first, given the set of items to be packed, aims at minimizing the unused space in each layer and thus the number of layers; the latter aims at minimizing the number of shipping bins given the set of layers obtained from the first problem. The approach is extensively tested and compared with existing approaches. For its validation we use both realistic data-sets drawn from the literature and real data-sets, obtained from an Italian logistics leader. The resulting outcomes show the effectiveness of the method in providing high-quality bin configurations in short computational times. Note to Practitioners—This work is motivated by the intention of facilitating the transition from Logistics 3.0 to Logistics 4.0 by providing an effective tool to automate bin packing, suitable for automated warehouses. On the one hand, the proposed technique provides stable and compact bin configurations in less than half a minute per bin on average, despite the high computational complexity of the 3D-SBSBPP. On the other hand, the approach allows to consider compatibility constraints for the items (e.g., final customer and category of the items), and the use of robotized layer picking in automated warehouses. In effect, layers composed by only one type of items (i.e., monoitem layers) can be directly picked and placed on the pallet by a robotic arm without the intervention of any operator. Consequently, the adoption of this approach in warehouses could drastically improve the efficiency of the packing process. [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]

Column generation (CG) algorithms are well known to suffer from convergence issues due, mainly, to the degenerate structure of their master problem and the instability associated with the dual variables involved in the process. In the literature, several strategies have been proposed to overcome this issue. These techniques rely either on the modification of the standard CG algorithm or on some prior information about the set of dual optimal solutions. In this paper, we propose a new stabilization framework, which relies on the dynamic generation of aggregated rows from the CG master problem. To evaluate the performance of our method and its flexibility, we consider instances of three different problems, namely, vehicle routing with time windows (VRPTW), bin packing with conflicts (BPPC), and multiperson pose estimation (MPPEP). When solving the VRPTW, the proposed stabilized CG method yields significant improvements in terms of CPU time and number of iterations with respect to a standard CG algorithm. Huge reductions in CPU time are also achieved when solving the BPPC and the MPPEP. For the latter, our method has shown to be competitive when compared with a tailored method. Summary of Contribution: Column generation (CG) algorithms are among the most important and studied solution methods in operations research. CG algorithms are suitable to cope with large-scale problems arising from several real-life applications. The present paper proposes a generic stabilization framework to address two of the main issues found in a CG method: degeneracy in the master problem and massive instability of the dual variables. The newly devised method, called dynamic separation of aggregated rows (dyn-SAR), relies on an extended master problem that contains redundant constraints obtained by aggregating constraints from the original master problem formulation. This new formulation is solved in a column/row generation fashion. The efficacy of the proposed method is tested through an extensive experimental campaign, where we solve three different problems that differ considerably in terms of their constraints and objective function. Despite being a generic framework, dyn-SAR requires the embedded CG algorithm to be tailored to the application at hand. [ABSTRACT FROM AUTHOR]

The pagination problem is described as follows. We have a set of symbols, a collection of subsets over these symbols (we call these subsets the tiles) and an integer capacity C. The objective is to find the minimal number of pages (a type of container) on which we can schedule all the tiles while following two fundamental rules. We cannot assign more than C symbols on each page and a tile cannot be broken into several pieces, all of its symbols must be assigned to at least one of the pages. The difference from the Bin Packing Problem is that tiles can merge. If two tiles share a subset of symbols and if they are assigned to the same page, this subset will be assigned only once to the page (and not several times). In this paper, as this problem is NP-complete, we will consider a particular case of the dual problem, where we have exactly two pages for which the capacity must be minimized. We will present a fully polynomial time approximation scheme (FPTAS) to solve it. This approximation scheme is based on the simplification of a dynamic programming algorithm and it has a strongly polynomial time complexity. The conducted numerical experiments show its practical effectiveness. [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]

Bin packing is a classic optimization problem with a wide range of applications, from load balancing to supply chain management. In this work, we study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. The online algorithm is enhanced with a potentially erroneous prediction concerning the frequency of item sizes in the sequence. We design and analyze online algorithms with efficient tradeoffs between the consistency, which is the competitive ratio assuming no prediction error, and the robustness, which is the competitive ratio under adversarial error. Moreover, we demonstrate that the performance of our algorithm degrades near-optimally as a function of the prediction error. This is the first theoretical and experimental study of online bin packing under competitive analysis in the realistic setting of learnable predictions. Previous work addressed only extreme cases with respect to the prediction error and relied on overly powerful and error-free oracles. [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]

We consider robust variants of the bin packing problem with uncertain item sizes. Specifically we consider two uncertainty sets previously studied in the literature. The first is budgeted uncertainty (the U\Gamma model), in which at most \Gamma items deviate, each reaching its peak value, while other items assume their nominal values. The second uncertainty set, the U\Omega model, bounds the total amount of deviation in each scenario. We show that a variant of the Next-cover algorithm is a 2 approximation for the U\Omega model, and another variant of this algorithm is a 2\Gamma approximation for the U\Gamma model. Unlike the classical bin packing problem, it is shown that (unless \scrP " \scrN \scrP) no asymptotic approximation scheme exists for the U\Gamma model, for \Gamma " 1. This motivates the question of the existence of a constant approximation factor algorithm for the U\Gamma model. Our main result is to answer this question by proving a (polynomial-time) 4.5 approximation algorithm, based on a dynamic-programming approach. [ABSTRACT FROM AUTHOR]