[SCIP] column generation while cutting?

[James Cussens]

Dear Gerald and fellow SCIPers,

Sorry for all the emails but I have eventually got to the bottom of this
problem which is, I think, sufficiently non-obvious
to share on this list.

In my SCIP project I generate new variables during solving without
implementing a pricer. However, since there are
no pricers implemented SCIP (quite reasonably!) assumes that no new
variables will come on the scene. In my example,
this led SCIP to compute an incorrect "trivial primal bound" due to this
piece of code (in scip.c):

 /* if all variables are known, calculate a trivial primal bound by setting
all variables to their worst bound */
   if( scip->set->nactivepricers == 0 )

I implemented a dummy pricer which does absolutely nothing, and my problem
has gone away.

James







On 29 September 2015 at 21:28, James Cussens <james.cussens at york.ac.uk>
wrote:

> Dear Gerald,
>
> Further to my earlier email, I've done a bit more digging. It looks as if
> the problem is not what I though but instead that the LP upper objective
> limit gets set very low early on (before either my new variable or the cut
> containing it is created):
>
> [src/scip/lp.c:12485] debug: setting LP upper objective limit from 1e+20
> to 0.0001
>
> and this means that my desired solution with objective value 2 is cut
> off...
>
> ....
>   0.0s|     1 |     0 |     0 |     - | 197k|   0 |   - |   1 |   1 |   1
> |   0 |   1 |   0 |   0 |    cutoff    |      --      |   0.00%
> [src/scip/solve.c:2619] debug:  -> final lower bound: 1e+20 (LP status: 4,
> LP obj: 1e+20)
> [src/scip/solve.c:3500] debug:  -> LP status: 4, LP obj: 1e+20, iter: 0,
> count: 3
> [src/scip/solve.c:2663] debug:  -> lower bound: 1e+20 [1e+20] (pseudoobj:
> 2 [2]), cutoff bound: 0.0001 [0.0001]
> [src/scip/solve.c:2672] debug: node is cut off by bounding (lower=1e+20,
> upper=0.0001)
> [src/scip/conflict.c:6800] debug: analyzing pseudo solution (obj: 2) that
> exceeds objective limit (0.0001)
> ....
>
> James
>
>
>
> On 18 September 2015 at 14:52, Gerald Gamrath <gamrath at zib.de> wrote:
>
>> 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
>> University of York                                        Fax  +44
>> (0)1904 500159
>> 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 listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>>
>
>
> --
> 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.york.ac.uk/docs/disclaimer/email.htm
>



-- 
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.york.ac.uk/docs/disclaimer/email.htm
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150930/29ed8037/attachment.html>