[SCIP] column generation while cutting?

[Ambros Gleixner]

Dear James,

a relevant reference for you might also be Steve Maher's paper

Solving the integrated airline recovery problem using column-and-row
generation. Transportation Science, Articles in Advance, March 2015

which you can find on his homepage.  He uses column and row generation
within SCIP.

Best,
Ambros



Am 18.09.2015 um 14:52 schrieb Gerald Gamrath:
> Dear James,
> 
> you are only allowed to call SCIPaddPricedVar() during pricing, but you
> could add the variables just via SCIPaddVar(). You could even set the
> initial flag of the variable to FALSE so that SCIP will automatically
> price it into the LP (only) if needed.
> 
> Best,
> Gerald
> 
> On 18.09.2015 11:28, James Cussens wrote:
>> I have an application where I generate cuts which include variables
>> which do not exist yet. At present, I follow the normal two-stage
>> approach: the cut is generated without the missing variables, and
>> later a pricer deduces that they are worth adding and my application
>> ensures they are added to the previously generated cuts.
>>
>> My pricer only ever generates variables which appear in the cuts I
>> generate, so I suspect it will be more efficient to generate the
>> missing variables *as soon as my cutting plane algorithm (CPA) has
>> generated the cut*. That is, the idea is to create them just before
>> adding the cut (which would then contain all its variables). My CPA
>> generates (a representation of) the cut with all its variables,
>> including those not already created (so it does a sort of pricing), so
>> we have these variables immediately to hand at the point of adding the
>> cut. It is true that, since we are generating variables
>> unconditionally, we may end up with more variables than if we priced
>> them in, but my guess is that we won't get too many unnecessary
>> variables created. 
>>
>> The CPA is implemented as the separator for a certain constraint
>> handler. So presumably I could just add suitable calls to
>> SCIPaddPricedVar in the separator callback, just before creating and
>> adding the row (ie cut).
>>
>> Does anyone see a problem with doing this? It just seems an odd
>> approach ....
>>
>> James
>>
>> -- 
>> James Cussens
>> Dept of Computer Science &
>> York Centre for Complex Systems Analysis
>> Room 326, The Hub, Deramore Lane            Tel    +44 (0)1904 325371
>> <tel:%2B44%20%280%291904%20325371>
>> University of York                                        Fax  +44
>> (0)1904 500159 <tel:%2B44%20%280%291904%20500159>
>> York YO10 5GE, UK                              
>> <http://www.cs.york.ac.uk/%7Ejc>http://www.cs.york.ac.uk/~jc
>> http://www.york.ac.uk/docs/disclaimer/email.htm
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
> 
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
> 

-- 
______________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - TU Berlin - Berlin Mathematical School
http://www.zib.de/gleixner