# Why does one objective function prove feasibility faster than another?

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?

• Do you try replacing the objective function with a dummy one (equal to zero) to assert how long does it take the model can produce a feasible solution? Maybe the direction of the first objective value is to be more complicated than the second one. Sep 10 at 7:46
• @A.Omidi Interesting, I tried having a dummy objective function (equal to zero) and it solved just as fast as model 2. In other words, model 1 is slower. This is an assignment problem in which model 1's objective function should maximize the number of assignments. Both models had a constraint specifying that all assignments should, well, be assigned. Sep 10 at 8:15

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.