Arrow Research search

Author name cluster

Herman Appelgren

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

AAMAS Conference 2022 Conference Paper

Learning Heuristics for Combinatorial Assignment by Optimally Solving Subproblems

  • Fredrik Präntare
  • Herman Appelgren
  • Mattias Tiger
  • David Bergström
  • Fredrik Heintz

Hand-crafting accurate heuristics for optimization problems is often costly due to requiring expert knowledge and time-consuming parameter tuning. Automating this procedure using machine learning has in recent years shown great promise. However, a large number of important problem classes remain unexplored. This paper investigates one such class by exploring learning-based methods for generating heuristics to perform value-maximizing combinatorial assignment (the partitioning of elements among alternatives). In more detail, we use machine learning leveraged by generating and optimally solving subproblems to produce heuristics that can, for example, be used with search algorithms to find feasible solutions of higher quality more quickly. Our results show that our learned heuristics outperform the state of the art in several benchmarks.

PDF

AAAI Conference 2021 Conference Paper

Anytime Heuristic and Monte Carlo Methods for Large-Scale Simultaneous Coalition Structure Generation and Assignment

  • Fredrik Präntare
  • Herman Appelgren
  • Fredrik Heintz

Optimal simultaneous coalition structure generation and assignment is computationally hard. The state-of-the-art can only compute solutions to problems with severely limited input sizes, and no effective approximation algorithms that are guaranteed to yield high-quality solutions are expected to exist. Real-world optimization problems, however, are often characterized by large-scale inputs and the need for generating feasible solutions of high quality in limited time. In light of this, and to make it possible to generate better feasible solutions for difficult large-scale problems efficiently, we present and benchmark several different anytime algorithms that use general-purpose heuristics and Monte Carlo techniques to guide search. We evaluate our methods using synthetic problem sets of varying distribution and complexity. Our results show that the presented algorithms are superior to previous methods at quickly generating near-optimal solutions for small-scale problems, and greatly superior for efficiently finding high-quality solutions for large-scale problems. For example, for problems with a thousand agents and values generated with a uniform distribution, our best approach generates solutions 99. 5% of the expected optimal within seconds. For these problems, the state-of-the-art solvers fail to find any feasible solutions at all.

PDF Details