  The recent advancements of Large Language Models (LLMs), with their abundant
world knowledge and capabilities of tool-using and reasoning, fostered many LLM
planning algorithms. However, LLMs have not shown to be able to accurately
solve complex combinatorial optimization problems. In Xie et al. (2024), the
authors proposed TravelPlanner, a U.S. domestic travel planning benchmark, and
showed that LLMs themselves cannot make travel plans that satisfy user
requirements with a best success rate of 0.6%. In this work, we propose a
framework that enables LLMs to formally formulate and solve the travel planning
problem as a satisfiability modulo theory (SMT) problem and use SMT solvers
interactively and automatically solve the combinatorial search problem. The SMT
solvers guarantee the satisfiable of input constraints and the LLMs can enable
a language-based interaction with our framework. When the input constraints
cannot be satisfiable, our LLM-based framework will interactively offer
suggestions to users to modify their travel requirements via automatic
reasoning using the SMT solvers. We evaluate our framework with TravelPlanner
and achieve a success rate of 97%. We also create a separate dataset that
contain international travel benchmarks and use both dataset to evaluate the
effectiveness of our interactive planning framework when the initial user
queries cannot be satisfied. Our framework could generate valid plans with an
average success rate of 78.6% for our dataset and 85.0% for TravelPlanner
according to diverse humans preferences.
