One model Packs Thousands of Items with Recurrent Conditional Query Learning

• URL: http://arxiv.org/abs/2111.06726v1
• Date: Fri, 12 Nov 2021 14:00:30 GMT
• Title: One model Packs Thousands of Items with Recurrent Conditional Query Learning
• Authors: Dongda Li, Zhaoquan Gu, Yuexuan Wang, Changwei Ren, Francis C.M. Lau
• Abstract summary: We propose a Recurrent Conditional Query Learning (RCQL) method to solve both 2D and 3D packing problems. RCQL reduces the average bin gap ratio by 1.83% in offline 2D 40-box cases and 7.84% in 3D cases compared with state-of-the-art methods.
• Score: 8.821298331302563
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent studies have revealed that neural combinatorial optimization (NCO) has advantages over conventional algorithms in many combinatorial optimization problems such as routing, but it is less efficient for more complicated optimization tasks such as packing which involves mutually conditioned action spaces. In this paper, we propose a Recurrent Conditional Query Learning (RCQL) method to solve both 2D and 3D packing problems. We first embed states by a recurrent encoder, and then adopt attention with conditional queries from previous actions. The conditional query mechanism fills the information gap between learning steps, which shapes the problem as a Markov decision process. Benefiting from the recurrence, a single RCQL model is capable of handling different sizes of packing problems. Experiment results show that RCQL can effectively learn strong heuristics for offline and online strip packing problems (SPPs), outperforming a wide range of baselines in space utilization ratio. RCQL reduces the average bin gap ratio by 1.83% in offline 2D 40-box cases and 7.84% in 3D cases compared with state-of-the-art methods. Meanwhile, our method also achieves 5.64% higher space utilization ratio for SPPs with 1000 items than the state of the art.

Related papers

• Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders [77.84801537608651]
  Cross-encoder (CE) models which compute similarity by jointly encoding a query-item pair perform better than embedding-based models (dual-encoders) at estimating query-item relevance. We propose a sparse-matrix factorization based method that efficiently computes latent query and item embeddings to approximate CE scores and performs k-NN search with the approximate CE similarity.
  arXiv  Detail & Related papers  (2024-05-06T17:14:34Z)
• Advancing LLM Reasoning Generalists with Preference Trees [119.57169648859707]
  We introduce Eurus, a suite of large language models (LLMs) optimized for reasoning. Eurus models achieve state-of-the-art results among open-source models on a diverse set of benchmarks.
  arXiv  Detail & Related papers  (2024-04-02T16:25:30Z)
• Learning based 2D Irregular Shape Packing [29.044043493942013]
  2D irregular shape packing is a necessary step to arrange UV patches of a 3D model within a texture atlas for memory-efficient appearance rendering in computer graphics. We introduce a learning-assisted 2D irregular shape packing method that achieves a high packing quality with minimal requirements from the input. In order to efficiently deal with large problem instances with hundreds of patches, we train deep neural policies to predict nearly rectangular patch subsets.
  arXiv  Detail & Related papers  (2023-09-19T05:21:52Z)
• SqueezeLLM: Dense-and-Sparse Quantization [80.32162537942138]
  Main bottleneck for generative inference with LLMs is memory bandwidth, rather than compute, for single batch inference. We introduce SqueezeLLM, a post-training quantization framework that enables lossless compression to ultra-low precisions of up to 3-bit. Our framework incorporates two novel ideas: (i) sensitivity-based non-uniform quantization, which searches for the optimal bit precision assignment based on second-order information; and (ii) the Dense-and-Sparse decomposition that stores outliers and sensitive weight values in an efficient sparse format.
  arXiv  Detail & Related papers  (2023-06-13T08:57:54Z)
• Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems [2.3642391095636484]
  In this paper, we demonstrate the potential of using variational classical annealing (VCA) as an approach to solving real-world optimization problems. We find that VCA outperforms simulated annealing (SA) on average in the limit by one or more orders of magnitude in terms of relative error. We conclude that in the best case scenario, VCA can serve as a great alternative when SA fails to find the optimal solution.
  arXiv  Detail & Related papers  (2022-07-17T14:33:17Z)
• LassoBench: A High-Dimensional Hyperparameter Optimization Benchmark Suite for Lasso [84.6451154376526]
  LassoBench is a new benchmark suite tailored for an important open research topic in the Lasso community. We evaluate 5 state-of-the-art HPO methods and 3 baselines, and demonstrate that Bayesian optimization, in particular, can improve over the methods commonly used for sparse regression.
  arXiv  Detail & Related papers  (2021-11-04T12:05:09Z)
• Pack Together: Entity and Relation Extraction with Levitated Marker [61.232174424421025]
  We propose a novel span representation approach, named Packed Levitated Markers, to consider the dependencies between the spans (pairs) by strategically packing the markers in the encoder. Our experiments show that our model with packed levitated markers outperforms the sequence labeling model by 0.4%-1.9% F1 on three flat NER tasks, and beats the token concat model on six NER benchmarks.
  arXiv  Detail & Related papers  (2021-09-13T15:38:13Z)
• When Liebig's Barrel Meets Facial Landmark Detection: A Practical Model [87.25037167380522]
  We propose a model that is accurate, robust, efficient, generalizable, and end-to-end trainable. In order to achieve a better accuracy, we propose two lightweight modules. DQInit dynamically initializes the queries of decoder from the inputs, enabling the model to achieve as good accuracy as the ones with multiple decoder layers. QAMem is designed to enhance the discriminative ability of queries on low-resolution feature maps by assigning separate memory values to each query rather than a shared one.
  arXiv  Detail & Related papers  (2021-05-27T13:51:42Z)
• Solve routing problems with a residual edge-graph attention neural network [10.42872026679616]
  In this paper, an end-to-end deep reinforcement learning framework is proposed to solve NP-hard optimization problems. The proposed framework is aiming to improve the models in literacy in terms of the neural network model and the training algorithm. Specifically, the average optimality gap is reduced from 4.53% (reported best citeR22) to 3.67% for TSP with 100 nodes and from 7.34% (reported best citeR22) to 6.68% for CVRP with 100 nodes when using the greedy decoding strategy.
  arXiv  Detail & Related papers  (2021-05-06T14:47:47Z)
• A threshold search based memetic algorithm for the disjunctively constrained knapsack problem [21.803219880299764]
  The disjunctively constrained knapsack problem consists in packing a subset of pairwisely compatible items in a capacity-constrained knapsack. We present a threshold search based memetic algorithm for solving the DCKP that combines the memetic framework with threshold search to find high quality solutions.
  arXiv  Detail & Related papers  (2021-01-12T21:07:33Z)
• Lookahead-Bounded Q-Learning [8.738692817482526]
  We introduce the lookahead-bounded Q-learning (LBQL) algorithm, a new, provably convergent variant of Q-learning. Our approach is particularly appealing in problems that require expensive simulations or real-world interactions.
  arXiv  Detail & Related papers  (2020-06-28T19:50:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.