[SCIP] separators and pricing

[Jonas Witt]

Hi James,

If cutting planes are added to the master problem, the corresponding 
dual variables need to be considered in the pricing problem. If you 
don't consider these dual variables, it will make the pricing problem 
invalid. Usually the structure of the pricing problem changes when cuts 
that are formulated with master variables are added, i.e., additional 
variables or constraints have to be added to the subproblem. How the 
subproblem is changed depends on the type of the added cut. This is why 
separation is disabled in the bin packing example.

Alternatively, one can add cuts from the original problem in the context 
of Dantzig-Wolfe reformulation; these cuts only change the objective 
function of the subproblem. But in the bin packing problem the pricing 
problems are aggregated, which is why this would reintroduce a lot of 
symmetry and pricing problems have to be disaggregated again.

For more details, you can have a look at the following paper:
https://doi.org/10.1002/net.20471

Best regards,
Jonas

On 09/11/2018 01:53 PM, James Cussens wrote:
> I notice that in the binpacking branch-and-price example, that all 
> separators are turned off. My guess is that this is to avoid the risk 
> of a separator generating an inequality that (1) becomes invalid once 
> a new variable is added by the pricer and (2) where it be too complex 
> to add the new variable to recover validity.
>
> Is this correct, or is there some other reason for this?
>
> Thanks,
>
> James
> -- 
> James Cussens
> Dept of Computer Science &
> York Centre for Complex Systems Analysis
> Room 326, The Hub, Deramore Lane            Tel    +44 (0)1904 325371
> University of York  Fax  +44 (0)1904 500159
> York YO10 5GE, UK http://www.cs.york.ac.uk/~jc 
> <http://www.cs.york.ac.uk/%7Ejc>
> http://www.york.ac.uk/docs/disclaimer/email.htm
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip


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