Assumptions about Discrete Space I have always had this question about "practical assumptions about discrete space".
Take for instance a classic problem in Integer Programming:

Had we been dealing with a function in continuous space (e.g. assuming a certain level of smoothness and differentiability), the theoretical properties of continuous space allow us to "somewhat" generalize the gradient of a function at a certain point to a local "neighborhood" from this point where the gradient was evaluated at. This property of continuous space is what allows algorithms like Gradient Descent to work - for example, the "Directional Derivative of a Function" tells us that the Function reduces locally with the greatest magnitude in the negative direction of its derivative. But all this time, all this is only possible because the notion of the derivative of a function in continuous space at a certain point can be generalized to other points in a certain radius.
Going back to the example of Integer Programming and discrete space - suppose we consider the point with the circle drawn around it:

Is there some "practical assumption" that the value of the function at neighboring points are more similar to this point compared to the value of the function at the non-neighboring blue point?
I have heard the following analogy being made: suppose you have some function f(x1, x2, x3...xn). For each tuple of (x1,x2,x3...xn), if you were to assign the corresponding value of the function at this tuple with some randomly generated number - naturally, this function would become impossible to optimize: this is because the idea of the derivative loses its meaning - since the topography of the function is now a random surface, a "valley" might be immediately followed by a "mountain" without any gradual change in the function. From a practical standpoint, "Valleys" need to gradually become "Mountains" for optimization algorithms to work - we must be able to have some level of confidence that if the elevation of the function has been decreasing, it can not magically increase some unbounded amount in the next moment (I believe this idea is reflected in concept of "Lipschitz Continuity").
The same way, suppose we consider some problem in discrete space such as the Travelling Salesman for 10 cities. Is there some "practical assumption" that the paths "1,2,3,4,5,6,7,8,9,10,1"  and "1,2,3,4,5,6,7,8,10,9,1" are more similar in distance - instead of either of these paths with "4,9,1,3,8,6,2,5,7,10,4" ? If paths that are closer to each other in discrete space are not generally closer in distance to each other when compared to a path that is far from both of these paths: how would any algorithm be able to optimize this function?
Thus, is there some "practical assumption" being made about the similarity of neighboring points in discrete space - similar to the idea of the derivative of a function being generalized over some local neighborhood?
Thanks!
 A: You can still define a notion of derivative over discrete-set which is given by
$$\Delta f_{x}(h)=\dfrac{f(x+h)-f(x)}{||h||}.$$
If we restrict $h$ such that $||h||_\infty=1$, then this reduces to
$$\Delta f_{x}(h)=f(x+h)-f(x).$$
This is used in the analysis of discrete-time systems or sequences.
The difficulty here is that it is impossible to extrapolate that further. For instance, the knowledge of $\Delta f_{x}(h_1)$ may not give us much information about that $\Delta f_{x}(h_2)$ for $h_1\ne h_2$.
However, in certain situations the function $f$ defined on a lattice is actually a restriction of a function $g$ defined on a continuous set such that $\mathbb{R}^n$. This is, for instance, what happens when we discretize of partial differential equation on its spatial domain. In such scenarios, we are able to consider certain properties of the function $g$ that will allow for bounding $\Delta f_x(h)$.
For instance, if the function $g$ is Lipschitz with Lipschitz constant $L$, we get that
$$|\Delta f_{x}(h)|=\dfrac{|f(x+h)-f(x)|}{||h||}\le \dfrac{L||x+h-x||}{||h||}=L.$$
As a result, we have that $|f(x+h)-f(x)|\le L||h||$, which gives you some indication on how the function behaves.
A: In both of the problems you mention, we generally have more structure than just "neighboring points are similar", and solution methods generally exploit that structure instead. (I realize this may seem like I'm dealing with just the two examples rather than the general case, but I think this often happens in general as well.)
In integer programming, we usually consider a linear objective function (integer variables are already so much power we don't need the flexibility of other objective functions). This does have nice properties with respect to the neighbors of a lattice point, but we don't use them, because often even finding a lattice point is hard. We deal with the linear programming relaxation instead, getting optimal fractional points that are not solutions, and then fight with their fractionality:

*

*Either with branch-and-bound methods, where we split the problem into two problems that have a different optimal fractional solution;

*Or with cutting plane methods, where we add a new constraint that eliminates the optimal fractional solution.

In the traveling salesman problem, we know that paths "1,2,3,4,5,6,7,8,9,10,1" and "1,2,3,4,5,6,7,8,10,9,1" are (almost always) more similar in distance to each other than to "4,9,1,3,8,6,2,5,7,10,4", not by assumption, but due to the structure of the problem. The path "1,2,3,4,5,6,7,8,9,10,1" has cost $c_{12} + c_{23} + c_{34} + \dots + c_{9,10} + c_{10,1}$. This differs from the second path only in that $c_{8,9} + c_{9,10} + c_{10,1}$ is replaced by $c_{8,10} + c_{10,9} + c_{9,1}$. Going from the first path to the third, all the costs are different.
(You can construct examples where this small change makes a huge difference in cost: for example, in a graph where the cost of traveling from $8$ to $9$ is much higher than all other costs combined, the first path will be very different from the other two, which are nearly the same. But you should think of this as analogous to a smooth function which just has very high derivative in some directions, not to a failure of smoothness.)
In practice, we often use integer programming methods to solve the TSP as well. But you can imagine that a method like simulated annealing would be able to exploit this structural similarity, because making a small change to the structure of a path lets us keep most of the costs of the edges.
