[SCIP] Reduced cost about variables in LP relaxation

[Gerald Gamrath]

Dear Kai Wei,

as far as I can see from your output file, the only plugins changing the 
bounds of variables are the storeGraph constraint handler and possibly 
the branching rule (when creating children, but probably, branching is 
enforced by the storeGraph constraint handler). This looks ok.

Whenever there are variables with negative reduced cost, could it be 
that the storeGraph constraint handler fixed them to 0 already? In that 
case, your pricing should not generate them again if you correctly 
modify your pricing problem based on your branching decisions.

If this is not the case, can you check that SCIPvarGetCol() is not NULL 
for the variables with reduced cost and whether 
SCIPcolIsInLP(SCIPvarGetCol()) holds?

Best,
Gerald

On 15.03.2016 06:45, weikaimas at 163.com wrote:
> Hi Gerald,
>
> I attached the statistics in the attachment.
>
> Waiting for your reply.
>
> Best regards,
>
> Kai WEI
>
>     *From:* Gerald Gamrath <mailto:gamrath at zib.de>
>     *Date:* 2016-03-15 00:30
>     *To:* weikaimas at 163.com <mailto:weikaimas at 163.com>
>     *CC:* scip <mailto:scip at zib.de>
>     *Subject:* Re: Reduced cost about variables in LP relaxation
>     Hi Wei Kai,
>
>     could you please print the statistics at the end of the solving
>     process and send them to me. Probably, you can see there which
>     propagator did reductions.
>
>     Best,
>     Gerald
>
>
>     On 12.03.2016 06:49, weikaimas at 163.com wrote:
>>     Dear Gerald,
>>
>>     I have tried to use SCIPchgVarUbLazy() to set an upper bound
>>     value for each variable in 3.2.0 and use version 3.2.1.
>>     However, I also found some variables with negative reduced cost
>>     in both above methods. The number of negative reduced cost variable
>>     is much less than version 3.2.0 without SCIPchgVarUbLazy(),  and
>>     both new methods have the some results.
>>
>>     Would have some methods to avoid the this phenomenon because the
>>     pricing method will find some useless variables.
>>
>>     Best regards,
>>     Kai Wei
>>
>>
>>
>>
>>         *From:* Gerald Gamrath <mailto:gamrath at zib.de>
>>         *Date:* 2016-03-04 18:23
>>         *To:* weikaimas at 163.com <mailto:weikaimas at 163.com>; scip
>>         <mailto:scip at zib.de>
>>         *Subject:* Re: Reduced cost about variables in LP relaxation
>>         Dear Wei Kai,
>>
>>         if a variable has an upper bound and is nonbasic at its upper
>>         bound in the LP solution, it may have negative reduced cost.
>>
>>         Did you set an upper bound for your variables? If so, you can
>>         use SCIPchgVarUbLazy() to set an upper bound value which is
>>         implicitly given by the constraints and should not explicitly
>>         added to the LP as bound of the variable.
>>
>>         However, we also noticed that some propagators installed
>>         upper bound on variables in branch-and-price applications.
>>         Although the reductions were correct, they may lead to
>>         troubles as you are now observing them. Therefore, these
>>         propagators are now automatically disabled if pricers are
>>         active. This fix is already included in the bugfix version
>>         3.2.1 released earlier this week. Please try if updating your
>>         version fixes your issues.
>>
>>         Best,
>>         Gerald
>>
>>         On 04.03.2016 08:56, weikaimas at 163.com wrote:
>>>         Hi all,
>>>
>>>            I have used SCIP to implement a B&P procedure. At leaf
>>>         nodes, before I implement pricing algorithm I use
>>>         SCIPgetVarRedcosr()
>>>         to check the reduced cost of all variables
>>>         (SCIPgetLPSolstat() returns 1). I found some variables with
>>>         negative reduced cost.
>>>           Can you give me the reasons about this phenomenon?  How
>>>         can I avoid to find the variables with negative reduced cost
>>>         in my pricing algorithm?
>>>
>>>         Best regards,
>>>
>>>         Kai WEI
>>>
>>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20160315/75a30169/attachment.html>