[Scip] Get linear constraint to corresponding row

Gerald Gamrath gamrath at zib.de
Mon Apr 7 11:45:26 CEST 2014


Hi Markus,

that means you create the cuts based on the LP rows of the master
problem? Did I understand you correctly that you want to save for each
created cut the set of rows used to create that cut and use that
information to take the cut into account in the pricing problem (getting
the master constraint for it, then getting the corresponding original
constraint and using that to update the objective of the pricing problem)?

If this is the case, I would suggest you try to separate the solution in
the original space and transfer the original cut into the master
problem. This is what the master separator of GCG already does for some
separators (mainly the combinatorial ones).
The zerohalf cut separator is so far not used in this context. However,
this is mainly a technical issue: the separator does not implement the
sepaexecsol callback needed for that. But I think this should be easy to
add to the separator, Jonas Witt might even have this laying around
somewhere. If this works and is sufficient for you, it should be very
convenient because you do not need to care about how the pricing
objective is updated.

On the other hand, you could also run your separation algorithm not on
the rows but on the constraints and also store for each cut the
constraints used to create it instead of the rows.

Best,
Gerald


Am 02.04.2014 10:42, schrieb Markus Kruber:
> Hi Gerald,
>
> thanks for the quick response.
>
> We are working on the separation of zerohalf cuts in branch-and-price
> and we want to implement this in GCG. Therefore, we extended SCIP's
> zerohalf separator. At the moment we store for each zerohalf cut the
> corresponding coefficients of the lprows which were used to create the
> zerohalf cut. We want to use this information in the pricing problem
> in order to include the zerohalf cuts correctly in the
> branch-price-and-cut procedure.
>
> The problem is that in GCG we only calculate a variable's coefficients
> corresponding to the constraints and not to the rows of the master
> problem. This is why it would be helpful to have the constraints
> corresponding to the rows that were used to create a zerohalf cut. But
> maybe we can access this information by using SCIPgetRowLinear() and
> getting the corresponding coefficient of the row. If our problem only
> contains linear constraints (which it does since the master problem in
> GCG only constains linear constraints), each row corresponds to one
> linear constraint and this should work. Do you agree with that?
>
> Regards,
> Markus
>
>
> 2014-04-01 9:06 GMT+02:00 Gerald Gamrath <gamrath at zib.de
> <mailto:gamrath at zib.de>>:
>
>     Dear Markus,
>
>     there is no such method in SCIP. The reason for this is, that in a
>     general CIP setting, there is no one-to-one correspondence between
>     constraints and rows. An "and" constraint, for example can add
>     multiple rows to get a tighter relaxation of the constraint in the
>     LP. The knapsack constraint handler, on the other hand, separates
>     knapsack cover cuts, so generates multiple rows as well, even if
>     the initial LP relaxation is just one row. Even more, a constraint
>     handler could also separate cuts based on more than one constraint
>     of its type.
>
>     Therefore, there is no general method for this. "SCIPgetRowLinear"
>     is implemented in the linear constraint handler, which knows at
>     that point that it creates exactly one row for each constraint and
>     therefore can return the row.
>
>     What was it you wanted to do? Perhaps you can just work on the row
>     (you can get the columns there and also get the variable for a
>     column by "SCIPcolGetVar") or work directly on the linear constraints?
>
>     Best,
>     Gerald
>
>     Am 31.03.2014 19 <tel:31.03.2014%2019>:13, schrieb Markus Kruber:
>>     Dear all,
>>
>>     I have given a row in my LP which belongs to a linear constraint.
>>     Now I am looking for a method which returns me this linear
>>     constraint.
>>     I already have found the method "SCIPgetRowLinear". In my
>>     understanding the other direction.
>>
>>     Best regards,
>>     Markus
>>
>>
>>     _______________________________________________
>>     Scip mailing list
>>     Scip at zib.de <mailto: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/20140407/14b49054/attachment.html>


More information about the Scip mailing list