[SCIP] Deleting constraints in branch-and-price

[Marc Pfetsch]

Hi Rolf,

this is a very good question. Unfortunately, I do not currently have a 
good answer.

Here are some thoughts:

- There is no API function to delete rows. This is because SCIP tries to 
keep the basis information whenever possible in order to make a 
warmstart possible. (This is also one of the reasons why deleting 
columns is not easy.) SCIP even tries to only delete rows that were 
newly added at a certain node.

- Moreover, if you delete constraints its attached rows are not deleted, 
because of the reason above (and because there is usually not a 
one-to-one correspondence between constraint and rows, e.g., if we have 
a separation algorithm).

- The conclusion of the above seems to be that:
   1. It would be easy to add a function to delete a row.
   2. It would require major work to make this efficient in connection 
with bases statuses.

If I understand your description correctly, in your case, there exists 
an optimal solution of the LP in which the dual variable of the 
redundant row is 0. It depends on your problem and on how you branch 
whether such a solution is found.

Thus, the only option I see is to reconsider your pricing problem. It 
seems that the rows you want to delete are redundant and they were 
correctly treated in the parent nodes. Thus, it might be that you can 
change your pricing problem in such a way that it still works.

Best

Marc


On 20/09/2022 16:34, Rolf van der Hulst wrote:
> Dear SCIP community,
> 
> I am working on a branch-and-price application where some of the 
> problem's (set covering) constraints can be removed during node 
> preprocessing. In order to delete the row, I tried using SCIPdelCons, 
> SCIPdelConsLocal and SCIPdisable /SCIPenable but they all run into the 
> same issue.
> 
> The issue I am running in to is that deleting/disabling a constraint 
> does not necessarily remove the associated row from the LP.  This is 
> problematic in my case, as the row which is still in the LP can then 
> also have a nonzero dual solution, which makes it impossible to solve 
> the pricing problem. I would like to know how to prevent these 
> Disabled/deleted rows from having a nonzero dual solution after I have 
> called SCIPdelCons() (or any of the above equivalents). Constraint 
> ageing (e.g. setting Removable to True) also does not work as SCIP still 
> does not evict this row from the LP as it is still a tight constraint.
> 
> My questions boil down to the following:
> 1. How can I force a constraint/row to be removed from the (current) LP?
> 2. Is this a bug?
> 
> Best,
> 
> Rolf
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip