[SCIP] Help for Diagnosing Disabled Constraints in Branch-and-Price Model

[Kamp, Dominik]

Dear Mahdi,

a constraint is disabled if it is locally redundant in a node. In this case the corresponding dual value is implicitly fixed to zero. So I guess the incorrectness you mention is because of missing lambda variables in the pricing problem.

The original binpacking formulation only has smaller-equal constraints so that lambda variables with zero dual value are never required in an optimal solution of the pricing problem.

However, in your formulation the bins are required to be full (equality in pricing). In this case, just remove the left hand side of the pricing constraint (this gives a relaxation of the problem because the set of priceable variables is increased) and fill the bins up to the capacity in the very end (possible without violation or cost).

Best regards,

Dominik

> On 23. Dec 2024, at 17:40, Mahdi Mohammadi <mo.mahdi1379 at gmail.com> wrote:
> 
> Dear SCIP Support Team,
> I hope this email finds you well. I am reaching out regarding an issue I’ve encountered in my branch-and-price implementation in SCIP. My implementation is based on the bin packing project, and I have made minimal modifications as my problem structure is nearly identical to the original (see the attached PDF).
> 
> The issue arises in pricing problem, some of my Master Problem constraints are unexpectedly disabled after a few iterations. This leads to their exclusion during the initialization of the pricing problem and affects its correctness (see the attached PDF).
> To investigate, I added a printf in the initPricing method where it compute the dual variable of the master problem:
> for (c = 0; c < n_edges; ++c) {
> cons = conss[c];  assert(!strncmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "setppc", 6)); 
>  if (!SCIPconsIsEnabled(cons)) {
>            printf("cons: %s was disabled\n", SCIPconsGetName(cons));
>           continue; }
> ...
>       /* dual value in original SCIP */
>       dual = isfarkas ? SCIPgetDualfarkasSetppc(scip, cons) : SCIPgetDualsolSetppc(scip, cons);
> ...
>  }
> Using this, I found that two of the master problem constraints are disabled and skipped during initialization. I have not modified the cons_samediff or branchryanfoster logic, assuming they would work as expected given the similarity to the bin packing problem.
> Could you please help me identify the root cause of these constraints being disabled and suggest a resolution? Is it because of cons_samediff  or branchryanfoster?
> Thank you for your time and expertise.
> Best regards,
> Mahdi
> 
> PS:
> I have also attached a abstraction of initPricing method implementation
> <abstraction of initPricing.txt><Model-Attachment.pdf>_______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip