[SCIP] column generation while cutting?

[James Cussens]

Dear Gerald,

I'm having problems when adding a new variable into the problem just before
including it in a cut. The (abbreviated) output below shows my problem. In
this example, all original variables get fixed
in presolving. We then try to separate using my constraint handler's
separator. The separator generates a valid cut which includes a new
variable <cb1(bob)>. This variable is added (using addVar), it is
down-locked and then
the cut with this new variable included. The cut is printed out below: this
is the correct cut (since the other two variables in the cut are fixed at
this point).

However, rather than just fixing cb1(bob) to 1 and returning the optimal
solution, SCIP tells me that we have a cutoff, and that the problem is
infeasible. If I add the variable  cb1(bob) at the start, all is well and I
get the correct optimal solution. (In fact, cb1(bob) gets fixed to 1 in
presolving which is fine.)

Any ideas what the problem is? I suspect this is something to do with the
original vs transformed problem

Best wishes,

James

 time | node  | left  |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols
|rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap
  0.0s|     1 |     0 |     0 |     - | 195k|   0 |   0 |   0 |   1 |   0 |
  0 |   0 |   0 |   0 | 0.000000e+00 |      --      |    Inf
[cons_folinear.c:371] debug: separating LP solution for first order linear
constraint <fo2>.
[cons_folinear.c:401] debug: New variable:
  [binary] <cb1(bob)>: obj=2, global bounds=[-0,1], local bounds=[-0,1]
[cons_folinear.c:403] debug: Down lock = <1>, Up lock = <0>
[cons_folinear.c:438] debug: Variable in cut:
  [binary] <smokes(bob)_neg>: obj=0, original bounds=[0,1], negated: 1 -
<smokes(bob)>
[cons_folinear.c:449] debug: Variable in cut:
  [binary] <cb1(bob)>: obj=2, global bounds=[-0,1], local bounds=[-0,1]
[cons_folinear.c:449] debug: Variable in cut:
  [binary] <cancer(bob)>: obj=0, original bounds=[0,1]
cut: 1 <= +1<cb1(bob)> <= 1e+20
[cons_folinear.c:479] debug: separated 1 cuts.
  0.0s|     1 |     0 |     0 |     - | 197k|   0 |   - |   1 |   1 |   1 |
  0 |   1 |   0 |   0 | 0.000000e+00 |      --      |    Inf
  0.0s|     1 |     0 |     0 |     - | 197k|   0 |   - |   1 |   1 |   1 |
  0 |   1 |   0 |   0 |    cutoff    |      --      |   0.00%
  0.0s|     1 |     0 |     0 |     - | 197k|   0 |   - |   1 |   1 |   1 |
  0 |   1 |   0 |   0 |    cutoff    |      --      |   0.00%

SCIP Status        : problem is solved [infeasible]


On 18 September 2015 at 13: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/974452c6/attachment.html>