  Given an undirected graph $G=(V,E)$, the longest induced path problem (LIPP)
consists of obtaining a maximum cardinality subset $W\subseteq V$ such that $W$
induces a simple path in $G$. In this paper, we propose two new formulations
with an exponential number of constraints for the problem, together with
effective branch-and-cut procedures for its solution. While the first
formulation (cec) is based on constraints that explicitly eliminate cycles, the
second one (cut) ensures connectivity via cutset constraints. We compare, both
theoretically and experimentally, the newly proposed approaches with a
state-of-the-art formulation recently proposed in the literature. More
specifically, we show that the polyhedra defined by formulation cut and that of
the formulation available in the literature are the same. Besides, we show that
these two formulations are stronger in theory than cec. We also propose a new
branch-and-cut procedure using the new formulations. Computational experiments
show that the newly proposed formulation cec, although less strong from a
theoretical point of view, is the best performing approach as it can solve all
but one of the 1065 benchmark instances used in the literature within the given
time limit. In addition, our newly proposed approaches outperform the
state-of-the-art formulation when it comes to the median times to solve the
instances to optimality. Furthermore, we perform extended computational
experiments considering more challenging and hard-to-solve larger instances and
evaluate the impacts on the results when offering initial feasible solutions
(warm starts) to the formulations.
