[Scip] Fwd: getting column coefficients and realloc error

[Mattia Barbieri]

>
> Hi Mattia,
> > 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20100520/e2a14015/attachment.html