[Scip] Design choices

[Gerald Gamrath]

Hi Martin,

the canonical workaround, as I mentioned previously, would be to add 
SCIPcutoffbounddelta() to the objective limit.

But do you really want to do that? You potentially loose quite some 
performance in the subproblem solving, because proving that no solution 
with negative reduced costs exists does not suffice, you additionally 
need to find one with 0 reduced cost. Do you think it happens so often, 
that a subproblem is (really) infeasible?

An alternative suggestion would be to keep track of the number of 
variables in each block that is not locally fixed to 0. If you thenhave 
a pricing problem without negative reduced cost and all existing 
variables in this problem are fixed to 0, the problem is infeasible, 
otherwise, there are just no improving variables.

But I see that the result code could be misleading, we will clarify this 
in the documentation.

Best,
Gerald

Am 30.06.2013 12:35, schrieb Martin Bergner:
> Hi Marc,
>
> just to throw in my 2 cents and in order to support Stefans intuition,
> we recently spent some time thinking about just this objective limit
> issue and also considered that a bug.
>
> In a branch-and-price context, we often provide the dual bound of the
> convexity constraint as an objective limit since we only want to find
> solutions with a strictly better objective value. Nonetheless, if the
> problem is feasible, we know that there exists a solution with exactly
> the given objective function limit without precisely knowing how it
> looks like (yes it's probably one of the columns already priced before,
> but I don't want to find that particular column and transfer it back to
> a pricing solution). There, an apparently infeasible pricing problem is
> highly disturbing and not intuitive at all. Actually, you usually
> suspect some issues in your model and I wonder how many hours we have
> actually spent trying to trace down a bug in our code. In any case, I
> don't want to put a number on that, it might be less than I thought.
>
> In our GCG context, we further are able to propagate bound changes on
> original variables to the pricing problem in certain cases. If a pricing
> problem is infeasible after a branching decision and some bound changes,
> I considered the node to be infeasible. That is not true, if we add the
> solution limit and I have multiple pricing problems. I was planning to
> trace down this issue next week because we encountered it just recently.
>
> Thank you very much for clarifying this, I was planning to submit a bug
> report to SCIP about this behavior because I also considered it broken.
> But, according to your explanation, it's not a bug, it's a feature and
> your reasoning behind that is perfectly logical. I don't like the status
> to be SCIP_INFEASIBLE but I don't see how you could change that, given
> how the whole behavior is implemented. Please mention that in at least
> in the documentation.
>
> What is the canonical workaround in my case? Forget the objective limit
> or add 10*feas_epsilon to it in case of a MIN Problem?
>
> Regards,
> Martin
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20130701/803a086a/attachment.html