Well, you formulate all your constraints in the language of your favourite constraint based programming solver (eg convex optimisation or mixed integer linear optimisation etc). For simplicity, let's call your candidate solution x (where x is a vector of suitable size) and the constraints are formulated as some function f from your vector to real numbers, so that the problem reduces to "minimize f(x)".
Then it's relatively easy to formulate your (5) as an additional constraint in the same language:
Given a previous solution x_0, find a new solution x_1 to slightly different constraints f_1 by minimizing af_1(x_1) + bdistance(x_1-x0)
You'd need to decide on the weights a and b and on the distance function. (Instead combining distance from old solution and constraints linearly, you could also use other ways to combine them. Eg you could also say:
Keep f_1(x_1) <= epsilon and minimize distance(x_1-x_0). Or you could do minimize the sum of squares:
af_1(x_1)^2 + bdistance(x_1-x0)^2
Specifics depends on what works well for your problem, and what your solver can handle.
