[SCIP] Problems with branch-and-price

[Veronica Dal Sasso]

Dear Steve,

Thank you for your answer,

the first problem was indeed my fault: a pause that I didn't realize was
there!

As for the second, there also was a mistake in how I generated the new
constraints for the pricing problem, so now it's working and I'm getting
the right solution.

All the best,

Veronica
Hi Veronica,

Thanks for your questions. It is great to see that you are using SCIP for
branch-and-price. The Bin Packing example is great as a starting point.

Your first problem seems a little strange. There is nothing in SCIP that
is expected to cause that behaviour. Since it only occurs in the Farkas
pricing, I would suggest that you review your own code to see if there is
anything unexpected. The Farkas pricing does not need user input by
default.

The addFixedVarsConss function in the bin packing pricer forbids the
columns that are excluded by your constraint handler from being generated
in the pricer. The constraint handler will ensure that at each node only
the feasible columns are present. However, the constraint handler does not
have any control over the columns that can be generated. It is necessary
in the pricer to get the currently active constraints from the constraint
handler and fix variables so that forbidden columns are not generated.

In writing your pricer, you don't necessarily need a function called
addFixedVarsConss. However, you do need some function to forbid columns
being generated that violate the active constraints.

Cheers,

Steve

On Fri, June 10, 2016 3:18 pm, Veronica Dal Sasso wrote:
> Dear all,
> I'm implementing a branch-and-price algorithm using C++ and SCIP, and I am
> facing a couple of difficulties:
>
> 1) most of the times, when I need to use Farkas pricing, my program stops
> and waits for some input, printing on the screen the string "<press>". I
> just give a letter as input and then it goes on with the computation, but
> I
> don't understand why it happens and how I can avoid it (and if it affects
> in any way the results).
>
> 2) I implemented a branching rule following the binpacking example, but I
> don't understand the role played by the function
>
> addFixedVarsConss(SCIP* scip, SCIP* subscip, SCIP_VAR** vars, SCIP_CONS**
> conss, int nitems)
>
> in file pricer_binpacking.c, as at each node I already fix to 0 the
> forbidden variables with the functions
>
> checkVariable(SCIP* scip, SCIP_CONSDATA* consdata, SCIP_VAR* var, int
> nfixedvars, SCIP_Bool cutoff)
>
> and
>
> consdataFixVariables((SCIP* scip, SCIP_CONSDATA* consdata, SCIP_VAR**
> vars,
> int nvars, SCIP_RESULT* result)
>
> in file cons_samediff.c and then my pricing problem is modified as to
> include informations on the forbidden columns, so that they will not be
> generated at that node and chid nodes.
> So as far as now I didn't implement the function addFixedVarsConss() but,
> as I get a wrong solution to my problem, I'm thinking that maybe it has a
> different role and that I need to implement it. Is that correct?
>
> Thank you very much for your help,
>
> Veronica Dal Sasso
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20160615/94d5530c/attachment.html>