[Scip] Another SCIP Branch & Price question

[Tobias Achterberg]

Hi Thomas,

Thomas K. Stidsen wrote:
> Congratulations with the job at CPLEX. I could not see to whom
> this email should go, if you deem that another person from the SCIP
> team is more relevant to answer the question, let me know and I will
> send the email to that person.

You can just send it to the SCIP mailing list (at least if you are a member of this list 
yourself). I CC'ed my answer to the list, since it our discussion may also be interesting 
to others who want to do branch and price.


> Otherwise, here is my question.
> 
> I am again working on Branch & Price in SCIP and the good news
> is that now my branch and price code in SCIP works .... at least for some
> of the examples. But one of the larger examples fails because I find
> a dublicated column. After some debugging I hav now identified a strange
> problem:
> 
> I perform branching using the method scip_execlp. I use standard 
> Ryan-Foster
> branching, i.e. find a pair of fractional variables, identify a row on 
> which they
> disagree (and one on which they agree). Then I add two constraints, a 
> branch up
> and a branch down constraint. Before I can add the constraints, I have 
> to check which
> of the existing variables/columns which has to have a non-zero factor 
> (1) in the
> added constraints (the same for both up and down constraints). I loop 
> through the
> set of variables, the array extracted using: SCIPgetLPColsData and now I 
> observe
> a strange thing: Not all the variables are included in this set of 
> variables which are
> returned !!! This seems very strange to me, and it means that I do not 
> assign a branching
> constraint to a certain variable ???

Hmm.. I don't understand your issue. Could you please explain it in more detail? You are 
using your own branching rule. Did you implement this as branching rule plugin, or are you 
including an own constraint handler?
You branch on constraints by adding one constraint to each of the two children. How do 
these branching constraints look like, and why do you need to the variables? Is it the 
case that in the creation of the constraints you need to identify the existing (i.e., 
already priced in) variables that should be part of the constraints?

With SCIPgetLPColsData() you are getting the columns of the current LP relaxation. It is 
correct that not all variables are necessarily part of the current LP relaxation. In 
particular in branch-and-price, the variables generated at one node in the tree are not 
included in the LP relaxation of a different node (if the other node is not a descendant 
of the first node). But even if you are still at the same node or at a descendant node, 
SCIP can remove columns from the LP if they are at 0 in the LP relaxation. This dynamic 
column deletion can be avoided by setting the "removable" flag to FALSE in the 
SCIPcreateVar() call.


> Ok, I have thought about his, whether only the variables which are 
> relevant/active in
> this branching node are returned by the SCIPgetLPColsData method when it 
> is called in
> scip_execlp method. The problem is that later on, I find a dublicate 
> variable in the
> scip_redcost method, BECAUSE the variable which is dublicated is not 
> constrained by
> an active branching-constraint ??? I check that the column is not 
> included in the branching
> constraint using the method: SCIPcolPrint. The variable in consideration 
> is active and the corresponding
> column is also active (SCIPcolIsInLP and SCIPvarIsActive). Hence I think 
> this variable SHOULD
> have been included into the branching constraint, but if I cannot get 
> access to it in scip_execlp,
> how can I inlcude it in the branching constraints ?

Hmmm... still don't understand. Please be a little bit more specific.


> Another question: What is the intuitive difference between a column and 
> a variable in SCIP ?
> There does not seem to be a corresponding duality regarding rows ...

Constraints and variables are the objects that live in the "CP formulation", i.e., they 
are the most relevant objects to SCIP. Rows and columns are just needed to define the LP 
relaxation. Each variable can have at most one column (but it does not need to have one), 
and each column knows its variable. You can get the column's variable with SCIPcolGetVar() 
from pub_lp.h. Each constraint can give rise to zero, one, or multiple rows in the LP 
relaxation. For example, the subtour elimination constraint can produce an exponential 
number of rows (the subtour elimination cuts). Additionally, rows can live on their own 
without being associated to a constraint, for example Gomory cuts. Therefore, a row does 
not know to which constraint it belongs.


Best, Tobias