In this talk we discuss a hybrid belief-propagation (BP) /
mixed-integer linear programming (MI-LP) decoder.  The failure of a
first-stage BP decoding attempt triggers a second-stage MI-LP decoder.
The MI-LP decoder was presented at ISIT 2007 (Draper, Yedidia, and
Wang) where it was shown to achieve the optimum maximum-likelihood
(ML) decoding performance on a (155, 64) LDPC code introduced by
Tanner et al.

By using the MI-LP decoder only when a first-stage BP decoder fails,
we extend the applicability of the scheme to longer block lengths.  We
investigate the complex-scaling of the scheme both as a function of
block-length and of signal-to-noise ratio.  As observed in the ISIT
paper, in the high-SNR (error floor) regime, typically at most a few
integer constraints are required to force the mixed-integer LP
solution to the ML solution.  Since the complexity of MI-LP decoding
is exponential in the number of integer constraints, the error-floor
regime is thus of interest for this scheme. We therefore investigate
the performance gains possible when the number of integer constraints
allowed is limited to some maximum number.