Constrained regression problems appear in the context of optimal nonlinear filtering, as well as in a variety of other contexts, e.g., chromatographic analysis in chemometrics and manufacturing, and spectral estimation. This paper presents novel mathematical programming algorithms for some important constrained regression problems in IRN . For brevity, we focus on four key problems, namely, locally monotonic regression (the optimal counterpart of iterated median filtering), and the related problem of piecewise monotonic regression, runlength-constrained regression (a useful segmentation and edge detection technique), and uni- and oligo- modal regression (of interest in chromatography and spectral estimation). The proposed algorithms are exact and efficient, and they also naturally suggest slightly suboptimal but very fast approximate algorithms, which may be preferable in practice.