[Scip] Design choices

Marc Pfetsch pfetsch at mathematik.tu-darmstadt.de
Sat Jun 29 21:04:59 MEST 2013



Hi Stefan,

SCIPsetObjlimit() simulates the effect of adding a feasible primal 
solution. When adding a feasible solution, all nodes are discarded in 
which no better solution can be found. As such, the function acts quite 
intuitive, I think.

Consequently, if you do not find a better solution the status is 
infeasible, since SCIP could not find a solution. If you want the status 
to be different, you would need to supply a solution. In any case, the 
behavior is roughly the same (except that supplying a primal might help 
other heuristics to find even better solutions) and the outcome just 
means that there does not exist a solution better than the limit supplied.

If you still want to find solutions with the same value, you currently 
need to add a constraint on the objective or add an epsilon to the value 
(this could also be beneficial for heuristics). I have encountered the 
need for the current implementation quite often, but not for the one 
with less or equal.

>    > If you would invest some more time to write the code which
> generates the solution itself instead of just its objective value (which
> you would probably do after the objective limit experiments show that a
> heuristic is promising), you would get the same behavior: [...]
>
> Most definitively not. Adding the (already optimal) solution data
> results in a solved problem. Setting the optimal value as ObjLimit
> results in infeasibility.

But this just results in the same conclusion: there is no better 
solution than the supplied solution or given objective limit. Up to the 
effect I described above, this results in the same behavior.

> Heuristics may find the optimal value, so allowing the best solution to
> be equal in value to the heuristic isn't "underestimating the positive
> effect of the heuristic", but _enabling_ the heuristic to be correct.

I do not understand: As indicated above (and by Gerald) you get a weaker 
behavior if solutions of the same value are still allowed - the search 
space is simply larger. Your heuristic is still correct if it still is 
able to provide the solution.

If you need to use SCIP to find this solution, this is an entirely 
different game. You are then redefining the purpose of the current run 
to run in favor of your heuristic.

> I _don't_ say that the implementation of SCIPsetObjlimit is false or
> bad. It's _not intuitive_.

Well, it obviously came unexpected for you.

> Of course it does. The naming does not imply strictness. Hence it is
> non-obvious that this should be different from a manually implemented
> constraint on the objective value. This should do the same, but it
> simply doesn't.

Well, SCIPsetObjlimit does neither imply less or equal or a strictly 
less. So the documentation applies.

>  > it is just the way an objective limit works within SCIP and probably
> works within every MIP solver
>
> CPLEX doesn't.

Yes, this is probably the source for your expectation of the behavior.

>  > , unless you want to do additional work and deteriorate your
> performance.
>
> I don't. I've already proposed an alternative. There's no downside at
> all. No additional work, no reduced performance.

Since the <= variant is weaker, there might be reduced performance. For 
the meantime this variant can be generated by adding a constraint.

> Please recall that I don't want to change your ways and do not intend to
> break your habits. I'm just curious about what led to these decisions.

Well, ...


Best

Marc


More information about the Scip mailing list