[Scip] Obtaining the LP solution to a node in Branch, Cut and Price

Timo Berthold berthold at zib.de
Wed Jun 15 09:50:41 MEST 2011


Hey Tue.

> Hello SCIP subscribers!
>
> I have yet another question. I am during a heuristic in a branch, cut and
> price algorithm. The heuristic is called at SCIP_HEURTIMING_AFTERLPNODE
> and obtains a feasible solution from the current optimal LP solution (the
> nonzero variables to be precise). The question, what is the fastest way to
> obtain the LP solution of a node?
>
> Currently I find it by going through all the variables added and checking
> manually by SCIPvarGetSol. This is not very satisfying because of a
> potentially large number of variables.

I suggest using
SCIP_VAR** lpcands;
SCIP_Real* lpcandssol;
int nlpcands;

SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL,
&nlpcands, NULL) );

This gives you all fractional integer/binary variables, their LP solution
values and the number of them.

> Also, this might give me the
> solution the a pseudo solution which should be avoided.

You can avoid this by putting

if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
  return SCIP_OKAY;

at the beginning of the HEUREXEC callback.

> Currently if the
> heuristic detects a pseudo solution (e.g. binary variables with value > 1
> or < 0), it simple stops the heuristic.

In the pseudo solution, all binary variables x_i have values = 0 (iff c_i
>= 0) or = 1 (iff c_i < 0).

>
> It seems that the SCIPcreateLPSol, could be a way of doing it. I am,
> however, not sure how to iterate through the solution to make the required
> changes for the solution to be feasible.

This function you only need if you want to have a complete copy of the LP
solution that you want to change.

> The optimal way would be a call
> to a function that yields me with an array of the variables nonzero in the
> current LP along with the number of variables and an array containing
> their current value. Is there such a function?

Yes, see above.

>
> Thank you all in advance!
>
> Tue Christensen

Cheers, Timo

>
> --
> The information transmitted is intended only for the person or entity to
> which it is addressed and may contain confidential and privileged
> material.
>
> Any review, retransmission, dissemination or other use of,or taking of any
> action in reliance upon, this informationby persons or entities other than
> the intended recipientis prohibited.
>
> If you received this in error, please contact the sender and delete the
> material from any computer.
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>



More information about the Scip mailing list