  A subset of Q^n is called semilinear (or piecewise linear) if it is Boolean
combination of linear half-spaces. We study the computational complexity of the
constraint satisfaction problem (CSP) over the rationals when all the
constraints are semilinear. When the sets are convex the CSP is polynomial-time
equivalent to linear programming. A semilinear relation is convex if and only
if it is preserved by taking averages. Our main result is a polynomial-time
algorithm for the CSP of semilinear constraints that are preserved by applying
medians. We also prove that this class is maximally tractable in the sense that
any larger class of semilinear relations has an NP-hard CSP. To illustrate, our
class contains all relations that can be expressed by linear inequalities with
at most two variables (so-called TVPI constraints), but it also contains many
non-convex relations, for example constraints of the form x in S for arbitrary
finite subset S of Q, or more generally disjunctive constraints of the form x <
c or y < d for constants c and d.
