Why does one objective function prove feasibility faster than another?

Question

I recently ran a MIP model with cplex specifying it should stop solving when integer feasibility was proven (mipsolutions=1).

When I ran the model with one easy objective function, the model did not find any feasible integer solutions after an hour. However, when I replaced the objective function with a different, also easy one—keeping all constraints the same—cplex proved integer feasibility in 3–4 minutes.

Moreover, I constructed the second objective function in such a way that if I had plugged the solution from model 2 into the objective function from model 1, the objective function value would have been exactly equal the value that would have been obtained from model 1. And vice versa.

This makes me wonder: why does one objective function prove feasibility faster than another?

Answer 1

Consider maximizing $\sum_{i=1}^n x_i$ subject to $x$ binary and $\sum_{i=1}^n i x_i \leq 2$

Solve relaxation and it gives $x_1 = 1, x_2 = 1/2$ with remaining variables 0. Branch on $x_2 = 0$ and the new solution is $x_1 = 1, x_3 = 1/3$ with the rest 0. Continue in the same fashion and you will have to go through fixing all variables.

Had you minimized $\sum_{i=1}^n x_i$ instead (or used another branching and variable selection strategy or simply a better solver) you would have had the optimal solution immediately.