  A semilinear relation is a finite union of finite intersections of open and
closed half-spaces over, for instance, the reals, the rationals, or the
integers. Semilinear relations have been studied in connection with algebraic
geometry, automata theory, and spatiotemporal reasoning. We consider semilinear
relations over the rationals and the reals. Under this assumption, the
computational complexity of the constraint satisfaction problem (CSP) is known
for all finite sets containing R+={(x,y,z) | x+y=z}, <=, and {1}. These
problems correspond to expansions of the linear programming feasibility
problem. We generalise this result and fully determine the complexity for all
finite sets of semilinear relations containing R+. This is accomplished in part
by introducing an algorithm, based on computing affine hulls, which solves a
new class of semilinear CSPs in polynomial time. We further analyse the
complexity of linear optimisation over the solution set and the existence of
integer solutions.
