[SCIP] Interaction of heuristic and delayed exact pricers with SCIP_DIDNOTRUN

[Lars Jaeger]

Hello SCIP-Enthusiasts,


 


I have a question about combining a heuristic pricer with a delayed exact
pricer for the same family of variables.


 


The intended setup is:


 


1. A heuristic pricer is called first.


2. If it finds an improving column, the LP is re-solved.


3. If it finds no column, a delayed exact pricer is called automatically.


4. The exact pricer either adds a column or proves that no improving column
exists.                              

 

According to type_pricer.h, a heuristic pricer that finds no column but
cannot prove that none exists return SCIP_DIDNOTRUN. Returning SCIP_SUCCESS
would appear incorrect because the heuristic has neither added a variable
nor completed pricing exactly. And I thought, that in older versions of
SCIP, that was the case, but maybe a gaslight myself here.

 

However, in solve.c, any SCIP_DIDNOTRUN result immediately sets:


 


```c


  *aborted = TRUE;


```


 


SCIP continues with the remaining pricers, so the delayed exact pricer is
still called if no column has been generated. 

If that exact pricer returns SCIP_SUCCESS and certifies that no improving
column exists, the aborted flag nevertheless appears to remain set. 

 

Consequently, the LP solution is not treated as a valid lower bound even
though pricing was subsequently         

completed exactly. 

 


A simplified callback setup is:


 


 ```cpp


  // Heuristic pricer


  if( improvingColumnFound )


  {


     addColumn();


     *result = SCIP_SUCCESS;


  }


  else


  {


     *result = SCIP_DIDNOTRUN;


  }


 


  // Delayed exact pricer


  if( improvingColumnFound )


     addColumn();


 


  *result = SCIP_SUCCESS; // column found or absence proved


```


 


Is this behavior intentional?


 


I understand that different pricers may be responsible for disjoint variable
families. In that case, a later     

successful pricer cannot compensate for an earlier incomplete one. However,
in this setup, the exact pricer      

covers the same variable family as the heuristic pricer and therefore
subsumes its search.                       

 


Is there a supported way to tell SCIP that the delayed exact pricer
certifies the same variable family as the    

heuristic pricer? Alternatively, should heuristic and exact pricing always
be implemented inside one pricer      

callback? Currently I just use a Lagrangian-Bound in the exact pricer, so
there is no problem, but I was working on a teaching example and stumbled
upon this.


 


If there is currently no way to express this relationship, could SCIP defer
the final aborted decision until all 

active pricers have run, or provide a mechanism through which an exact
pricer can supersede an earlier           

SCIP_DIDNOTRUN result? Maybe we could use the SCIP_DIDNOTFIND flag for that
behavior?

 

Thank you for your help.

Best regards,


Lars

___________________________________________________

 

Lars Jäger, M.Sc.

Wissenschaftlicher Mitarbeiter

Leibniz Universität Hannover

Institut für Produktionswirtschaft

Königsworther Platz 1

D-30167 Hannover

Büro: I-125

E-Mail:  <mailto:lars.jaeger at prod.uni-hannover.de>
lars.jaeger at prod.uni-hannover.de

Tel: +49 (0)511 762 - 5649

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20260914/c63a59d1/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 18115 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20260914/c63a59d1/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image002.png
Type: image/png
Size: 21018 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20260914/c63a59d1/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 6076 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20260914/c63a59d1/attachment.p7s>