5
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Sep 10 at 7:46
  • $\begingroup$ @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. $\endgroup$
    – Christian
    Sep 10 at 8:15
5
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Very nice example! $\endgroup$
    – prubin
    Sep 10 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.