Is it true that the optimal solution to an ILP problem must be one of the neighboring points of the points on the boundaries of the corresponding relaxed LP problem? Is so, how to prove it?
That is, let V be the set of vertices in the feasible region. For each vertex v=(v1, v2, ..., v_n), we call w=(w1, w2, ..., w_n) an integer neighbor of v if for every k, w_k = ceiling(v_k) or w_k = floor(v_k). Let Neighbor(V) ={w | w is a neighbor of v and v is on the boundary of the feasible region}. Is the hypothesis true? If so, prove it. If not, give a counterexample.