Max Is More than Min: Solving Maximization Problems with Heuristic Search

Stern, Roni; Kiesel, Scott; Puzis, Rami; Felner, Ariel; Ruml, Wheeler

Max Is More than Min: Solving Maximization Problems with Heuristic Search

Roni Stern, Scott Kiesel, Rami Puzis, Ariel Felner, Wheeler Ruml

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Best Papers from Sister Conferences Track. Pages 4324-4329.

Abstract

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding a longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and close relationships between Dijkstra's algorithm, weighted A*, and depth-first search.

Roni Stern, Scott Kiesel, Rami Puzis, Ariel Felner, and Wheeler Ruml. 2015. Max Is More than Min: Solving Maximization Problems with Heuristic Search. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 4324–4329. https://ijcai.org/proceedings/2015/615

@inproceedings{ijcai2015p615,
  title     = {Max Is More than Min: Solving Maximization Problems with Heuristic Search},
  author    = {Stern, Roni and Kiesel, Scott and Puzis, Rami and Felner, Ariel and Ruml, Wheeler},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {4324--4329},
  year      = {2015},
  month     = {7},
  note      = {Best Papers from Sister Conferences Track},
  url       = {https://ijcai.org/proceedings/2015/615},
}

TY  - CPAPER
TI  - Max Is More than Min: Solving Maximization Problems with Heuristic Search
AU  - Stern, Roni
AU  - Kiesel, Scott
AU  - Puzis, Rami
AU  - Felner, Ariel
AU  - Ruml, Wheeler
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 4324
EP  - 4329
UR  - https://ijcai.org/proceedings/2015/615
ER  -