I'm thinking specifically of situations where you want your model to be a linear program or, at worst, an integer linear program. It is well known that linear programs have convex feasible regions, and that is the basis for most algorithms. For integer or mixed integer problems, solvers again rely on convexity, in two respects: the continuous relaxation of the model (relaxing integrality constraints) should have a convex feasible region; and the restricted problem obtained by fixing values for the integer variables should have a convex feasible region.
What makes the order matching constraint tricky can be seen in Figure 1 below. Let's assume for simplicity that $N=2$. Figure 1 shows a two dimensional space spanned by $x_1 - x_2$ and $y_1 - y_2$, with the set of points satisfying the ordering constraint (the first and third quadrants) shaded green. If we relax any integrality restrictions in the original model and project its feasible region (linearly) onto this plane, the "shadow" of the feasible region must lie within the green area.
 |
| Figure 1 |
Assuming the original feasible region (again, with any integrality restrictions relaxed) is convex, the way we want (need?) it to be, its projection will also be convex. The green area, though is not convex. The blue dotted line segment connects two feasible points but obviously leaves the green region. When we "cut away" the portion of the original feasible region that projects onto the white areas, we gain enforcement of the ordering constraint but may lose convexity of the feasible region.
So, are we screwed (to use a technical term)? Not necessarily. The projection of the original feasible region is unlikely to fill the green quadrants, and other constraints may cooperate to force the projection to remain convex. Figure 2 shows a somewhat trivial case, in which the original model also contains the constraint $x_1 - x_2 = y_1 - y_2$. That constraint by itself will cause the ordering restriction to be satisfied. The projection of the feasible region is the red line in Figure 2, which is clearly convex.
 |
| Figure 2 |
The takeaway from Figure 1, at least for me, is that getting the ordering constraint in while preserving convexity will be tricky in general (unless you get "lucky" courtesy of other constraints). Since the green area is the union of two convex sets (cones, to be specific), a standard way to finesse the convexity issue is to add a binary variable indicating which cone you are in. (See, for instance, Partitioning with Binary Variables.) Once the value of the binary variable is fixed, the feasible region is restricted to a particular quadrant (cone), and you can stop worrying about loss of convexity. You need a binary variable for each pair of subscripts, though, so in the general case this introduces $O(N^2)$ binary variables, which might get a bit annoying.
If all the variables are bounded and either $x$ or $y$ is integer valued, there might be a less cumbersome way to handle the ordering constraint, but that's a topic for another day (or never, whichever comes second).
