  We present FRA-Poly, a facial reduction algorithm (FRA) for conic linear
programs that is sensitive to the presence of polyhedral faces in the cone. The
main goals of FRA and FRA-Poly are the same, i.e., finding the minimal face
containing the feasible region and detecting infeasibility, but FRA-Poly treats
polyhedral constraints separately. This idea enables us to reduce the number of
iterations drastically when there are many linear inequality constraints. The
worst case number of iterations for FRA-poly is written in the terms of a
"distance to polyhedrality" quantity and provides better bounds than FRA under
mild conditions. In particular, in the case of the doubly nonnegative cone,
FRA-Poly gives a worst case bound of $n$ whereas the classical FRA is
$\mathcal{O}(n^2)$. Of possible independent interest, we prove a variant of
Gordan-Stiemke's Theorem and a proper separation theorem that takes into
account partial polyhedrality. We provide a discussion on the optimal facial
reduction strategy and an instance that forces FRAs to perform many steps. We
also present a few applications. In particular, we will use FRA-poly to improve
the bounds recently obtained by Liu and Pataki on the dimension of certain
affine subspaces which appear in weakly infeasible problems.
