Comparing Heuristics, Constraint Optimization, and Reinforcement Learning for an Industrial 2D Packing Problem

• URL: http://arxiv.org/abs/2110.14535v1
• Date: Wed, 27 Oct 2021 15:47:47 GMT
• Title: Comparing Heuristics, Constraint Optimization, and Reinforcement Learning for an Industrial 2D Packing Problem
• Authors: Stefan B\"ohm, Martin Neumayer, Oliver Kramer, Alexander Schiendorfer, Alois Knoll
• Abstract summary: Cutting and Packing problems are occurring in different industries with a direct impact on the revenue of businesses. Machine learning is increasingly used for solving such problems.
• Score: 58.720142291102135
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Cutting and Packing problems are occurring in different industries with a direct impact on the revenue of businesses. Generally, the goal in Cutting and Packing is to assign a set of smaller objects to a set of larger objects. To solve Cutting and Packing problems, practitioners can resort to heuristic and exact methodologies. Lately, machine learning is increasingly used for solving such problems. This paper considers a 2D packing problem from the furniture industry, where a set of wooden workpieces must be assigned to different modules of a trolley in the most space-saving way. We present an experimental setup to compare heuristics, constraint optimization, and deep reinforcement learning for the given problem. The used methodologies and their results get collated in terms of their solution quality and runtime. In the given use case a greedy heuristic produces optimal results and outperforms the other approaches in terms of runtime. Constraint optimization also produces optimal results but requires more time to perform. The deep reinforcement learning approach did not always produce optimal or even feasible solutions. While we assume this could be remedied with more training, considering the good results with the heuristic, deep reinforcement learning seems to be a bad fit for the given use case.

Related papers

• Near-Optimal Solutions of Constrained Learning Problems [85.48853063302764]
  In machine learning systems, the need to curtail their behavior has become increasingly apparent. This is evidenced by recent advancements towards developing models that satisfy dual robustness variables. Our results show that rich parametrizations effectively mitigate non-dimensional, finite learning problems.
  arXiv  Detail & Related papers  (2024-03-18T14:55:45Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights [59.93939636422896]
  The ML4CO aims at improving state-of-the-art optimization solvers by replacing key components. The competition featured three challenging tasks: finding the best feasible solution, producing the tightest optimality certificate, and giving an appropriate routing configuration.
  arXiv  Detail & Related papers  (2022-03-04T17:06:00Z)
• Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem [18.735056206844202]
  We show that we can construct a model capable of learning without supervision and inferences significantly faster than current autoregressive approaches. We also empirically evaluate the benefits of including optimal transport algorithms within deep learning models to enforce assignment constraints during end-to-end training.
  arXiv  Detail & Related papers  (2022-03-02T07:21:56Z)
• How to effectively use machine learning models to predict the solutions for optimization problems: lessons from loss function [0.0]
  This paper aims to predict a good solution for constraint optimization problems using advanced machine learning techniques. It extends the work of citeabbasi 2020predicting to use machine learning models for predicting the solution of large-scaled optimization models.
  arXiv  Detail & Related papers  (2021-05-14T02:14:00Z)
• Learning to Optimize: A Primer and A Benchmark [94.29436694770953]
  Learning to optimize (L2O) is an emerging approach that leverages machine learning to develop optimization methods. This article is poised to be the first comprehensive survey and benchmark of L2O for continuous optimization.
  arXiv  Detail & Related papers  (2021-03-23T20:46:20Z)
• SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning [0.0]
  This paper presents the proof of concept for SeaPearl, a new constraint programming solver implemented in Julia. SeaPearl supports machine learning routines in order to learn branching decisions using reinforcement learning. Although not yet competitive with industrial solvers, SeaPearl aims to provide a flexible and open-source framework.
  arXiv  Detail & Related papers  (2021-02-18T07:34:38Z)
• Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization [5.669790037378094]
  The goal is to find an optimal solution among a finite set of possibilities. Deep reinforcement learning (DRL) has shown its promise for solving NP-hard optimization problems. constraint programming (CP) is a generic tool to solve optimization problems. In this work, we propose a general and hybrid approach, based on DRL and CP, for solving optimization problems.
  arXiv  Detail & Related papers  (2020-06-02T13:54:27Z)
• Learning with Differentiable Perturbed Optimizers [54.351317101356614]
  We propose a systematic method to transform operations into operations that are differentiable and never locally constant. Our approach relies on perturbeds, and can be used readily together with existing solvers. We show how this framework can be connected to a family of losses developed in structured prediction, and give theoretical guarantees for their use in learning tasks.
  arXiv  Detail & Related papers  (2020-02-20T11:11:32Z)

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.