Segev Shlomov, Avi Yaeli
CHI 2024
Branch-and-bound techniques allow intractable problems to be solved by using heuristics to bound the cost of partial solutions. The use of admissible heuristics can guarantee that the solutions found are optimal. This paper examines one paradigm-problem relaxation by constraint deletion-which has been used to develop many admissible heuristics. The paradigm suggests three steps: simplify (or relax) a problem, solve the simplified problem, and use that solution to guide the search for a solution to the original problem. We introduce the following extension to this methodology: by criticizing the feasibility of a relaxed solution, we arrive at a closer approximation of the solution to the original problem. We apply this methodology to two well-studied problems in operations research and artificial intelligence. For the traveling-salesman problem, iteration of our technique yields a series of novel heuristics, culminating in Held and Karp's minimum-spanning-tree heuristic. For the eight puzzle, it yields a heretofore undiscovered heuristic which is shown to perform significantly better than any previously known. © 1992.
Segev Shlomov, Avi Yaeli
CHI 2024
Anurag Ajay, Seungwook Han, et al.
NeurIPS 2023
Fahiem Bacchus, Joseph Y. Halpern, et al.
IJCAI 1995
Zhikun Yuen, Paula Branco, et al.
DSAA 2023