An Efficient Structured Perceptron for NP-Hard Combinatorial Optimization Problems

Véjar, Bastián;Aglin, Gaël;Mahmutoğulları, Ali İrfan;Nijssen, Siegfried;Guns, Tias;et.al.
(2024) International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research — Location: Uppsala, Sweden (28.May.2024)

Files

cpaior2024_structured_perceptron.pdf
  • Open Access
  • Adobe PDF
  • 524.17 KB
Download

Details

Authors
  • Véjar, Bastián
    Author
  • Aglin, GaëlUCLouvain
    Author
  • Mahmutoğulları, Ali İrfan
    Author
  • Nijssen, Siegfriedorcid-logoUCLouvain
    Author
  • Schaus, Pierreorcid-logoUCLouvain
    Author
  • Guns, Tias
    Author
Show more
Abstract
A fundamental challenge when modeling combinatorial optimization problems is that often multiple sub-objectives need to be weighted against each other, but it is not clear how much weight each sub-objective should be given: consider routing problems that trade off distance and duration where the relative importance of the two is not known a priori. In recent work, it has been proposed to use machine learning algorithms from the domain of structured output prediction to learn such weights from examples of desirable solutions. However, until now such techniques were only evaluated on fast-to-solve optimization problems. We propose and evaluate three techniques that make it feasible to apply the structured perceptron on NP-hard optimization problems: 1) using heuristic solving methods during the learning process, 2) solving well-chosen satisfaction variants of the problems, 3) caching solutions computed during the learning process and reusing them. Experiments confirm the validity and speed-ups of these techniques, enabling structured output learning on larger combinatorial problems than before.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Véjar, B., Aglin, G., Mahmutoğulları, A. İ., Nijssen, S., Schaus, P., & Guns, T. (2024). An Efficient Structured Perceptron for NP-Hard Combinatorial Optimization Problems. LNCS, 14743 (2024). https://doi.org/10.1007/978-3-031-60599-4_17 (Original work published 2024)