[Scip] Fwd: getting column coefficients and realloc error

[Stefan Heinz]

Hi Mattia,

what you want to do is called strong branching. In case of SCIP there are
methods supporting this. Besides that there also branching rules doing
this all ready. You should have a lock at the branching rules
branch_fullstrong.c and branch_allfullstrong.c. These rules do strong
branching for certain set of variables and select the final variable
w.r.t. to the increase in the lower bound.

The methods SCIPgetVarStrongbranch*() are the once you want to use.

-- Stefan

>> > In my branching plugin, I try doing this:
>> >
>> >  for (int v = 0; v < nlpcands; v++) {
>> >
>> >         cVar = lpcands[v];
>> >
>> >         *//include var*
>> >         SCIPstartDive(scip);
>> >
>> >         SCIPchgVarLbDive(scip, cVar, 1.0);
>> >         SCIPchgVarUbDive(scip, cVar, 1.0);
>> >         SCIPsolveDiveLP(scip, -1, error);
>> >
>> >         LPval1 = SCIPgetLowerbound(scip);
>> >
>> >         SCIPendDive(scip);
>> >
>> >        * //exclude var*
>> >         SCIPstartDive(scip);
>> >
>> >         SCIPchgVarLbDive(scip, cVar, 0.0);
>> >         SCIPchgVarUbDive(scip, cVar, 0.0);
>> >         SCIPsolveDiveLP(scip, -1, error);
>> >
>> >         LPval1 = SCIPgetLowerbound(scip);
>> >
>> >         SCIPendDive(scip);
>> >
>> >         LPval = MIN(LPval1, LPval2);
>> >
>> >         *//take max of LPval of all fractional variables*
>> >         if (LPval > bestLPval) {
>> >             bestLPval = LPval;
>> >             bestVarIndex = v;
>> >         }
>> >     }
>> >
>> > But what I get is an incorrect primal bound (integer) solution. I
>> suppose
>> > this happens because a change in Lower/Upper bound in this way is done
>> > permanently, while what I hope to get is a change only during the time
>> I
>> > solve the LP to select the best variable. Then I want the variable's
>> > Upper/Lower bound come back to its original values, letting me going
>> on
>> to
>> > the usual branching process without any changes in the variables (I
>> will
>> > include or exclude "arcs" from paths, not entire variables).
>> I do not understand the Problem yet. First, if the above code is just a
>> copy
>> of the real code, then there is bug. Since one of these lines
>> >         LPval1 = SCIPgetLowerbound(scip);
>> should be
>> >         LPval2 = SCIPgetLowerbound(scip);
>> Second, with this call you should get a dual value and not a primal
>> value.
>> Besides that you should try SCIPgetNodeLowerbound() instead of
>> SCIPgetLowerbound().
>> http://scip.zib.de/doc/html/scip_8c.html#f365112efafb8219d42ee2ab205be2e1
>>
>
> You're right: I committed a mistake when copying the code. Now I change
> SCIPgetLowerbound() with SCIPgetNodeLowerbound(), but things don't change.
> I
> try to explain my idea. My problem is essentially a Multicommodity Flow
> Problem, where a variable describe a path of a commodity on a net.
> In my current B&B tree, I am determining on which variable perform branch.
> A
> solution could be to select the most fractional variable, or the variable
> associated with the longest path. I would instead select the variable
> giving
> the best bound. Citing the article where I read this strategy: "[...]
> choosing a candidate set of variables for branching and selecting the best
> among them by LP testing, i.e., by solving both linear programs induced by
> the two possible values of the variable. The best variable is then chosen
> as
> the one for which the minimum of the two objective function values is the
> largest."
> So I would like to perform this, solving, at each node, an LP problem for
> each fractional variable, one if it is included in the problem, and if
> not.
> Finally select the variable that give the best value.
> Including a variable in the problem for me is equivalent to set his LB and
> UB to 1. Exclude it setting LB and UB to 0. But this seems to be
> irrilevant:
> the Lowerbound is the same for each variable even after having set them to
> 1
> or 0. It changes only after having perform the branch (when the pricing
> routine is called). Any ideas?
>
>>
>> > > -  After few nodes the actives variables are a lot (1000 to 20k
>> > > variables,
>> > >
>> > > > considering 70-nodes problems). These are all the variables that
>> my
>> > >
>> > > pricer
>> > >
>> > > > plugin find, but in practice only a half (or less) are active
>> columns
>> > > > of the current LP at one node (I suppose that SCIP has a own
>> mechanism
>> > > > to define a pool of active columns).
>> > >
>> > > Yes that is the case.
>> > >
>> > > > Thousands of columns are anyway too
>> > > >  much, because the LP solving process is very slow. Is there
>> anyway
>> to
>> > > >  better manage this problem?
>> > >
>> > > I am not sure if I got your question right. I try to answer it in
>> the
>> > > follwing
>> > > way:
>> > > There is one problem in the current version of SCIP. It is not
>> possible
>> > > to remove variables from the problem. In your case I would suggest
>> to
>> > > select only
>> > > a certain number of the variables your pricer creates for adding to
>> your
>> > > problem in each round. That  might help to reduce the amount of
>> useless
>> > > variables in the end.
>> >
>> > Instead it may help to remove from the current LP variables whit a
>> very
>> >  high positive (min object sense) reduced cost. How can I deal whit
>> this
>> >  approach?
>> SCIP does that for you already. The only thing you have to do, is to
>> allow
>> that a variable can be removed from the LP. To do this you have to set
>> the
>> parameter "removable" in the method call SCIPcreateVar() to TRUE.
>> http://scip.zib.de/doc/html/scip_8c.html#9025d19ffd6d4fd3d10714485709fefc
>>
>
> Yes, this is already like this in my project. Another question: do
> variables
> which are fixed to 0 be ignored (removed) by the presolving routine, at
> *each
> node* LP? (not only on the presolving done at root node)
>
>>
>> Hope that helps.
>>
>> -- Stefan
>>
>
> Thanks again for your patience.
>
> --
> Mattia Barbieri
> barbieri.mattia at gmail.com
>