Improving suboptimal solution for a network design problem

I'm solving a rather large network design problem (Xpress 9.2.4, python interface). Here's a very simplified version of the integer programming formulation.

Variables:

- y_ij: integer variable representing the number of vehicles required to service volume on arc (i,j)

- x_ijk: continuous variable representing the amount of volume for commodity k routed via arc (i,j)

Parameters:

c_ij: cost per vehicle on arc (i,j), with c_ij > 0 for every arc (i,j)

Q: capacity of a vehicle

Objective:

minimize sum_(i,j): c_ij y_ij

Constraint:

sum_k x_ijk <= Q y_ij for all (i,j)

... remaining constraints omitted.

I set a 2h time limit and solve the problem. After reaching the time limit, the solver terminates with a feasible solution.

Interestingly, when analyzing the solution, there's a few arcs where sum_k x_ijk = 0, yet the y_ij variable takes the value 1. Since the above constraint is the only constraint that relates to the y_ij variables, we can simply improve the objective value by setting y_ij=0 for those arcs.

I realize that because the solver terminated because of a time limit, the returned solution could potentially be suboptimal. I tried to run my instance much longer, but due to its size I cannot solve it to optimality (optimality gap < 3%). To verify that I did not make any implementation errors, I exported the model, fixed all variables to their values in the solution returned by Xpress. I only changed (set to 0) the y variables of arcs with sum_k x_ijk = 0. Then I resolved the model by Xpress which instantly returns this improved solution. This confirms that this better solution is indeed feasible and better.

I was somewhat surprised that I could find these simple opportunities to improve the objective. Is this as expected, or is there something I should be looking into?