[SCIP] column generation while cutting?

[James Cussens]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150929/edf7ed34/attachment.html>