[SCIP] Running primal heuristics for partial models

[Marc Pfetsch]

Hi Rolf,

I can only give you my thoughts on this, which are probably not conclusive.

I think that your application cannot be implemented within a single run 
of SCIP. The usual setup is that a constraint that defines feasibility 
needs to be present from the start of the problem (it defines which 
problem is actually solved). It can then enforce such solutions by, 
e.g., adding rows. From what I understand from your description, you do 
not know (or cannot/do not want to decide) which problem is solved at 
the beginning.

A reset of the primal bound would mean that the branch-and-bound tree of 
SCIP would need to be reevaluated, so this is not easy.

However, the reoptimization feature of SCIP implements something like 
this. If you solved your problem (or terminated because of other 
reasons), you can add constraints (or change the objective). Upon a 
reoptimization of the problem, the tree is evaluated and updated.

The problem is that I do not think that this will directly work with 
column generation. This is because the status of the reoptimization is 
stored in constraints, for which (I think) one needs to know all 
variables at the time of generation.

Best

Marc


On 15/06/2022 16:50, Rolf van der Hulst wrote:
> Dear SCIP community,
> 
> I am looking to implement an algorithm which uses both column generation 
> and row generation. In particular, there would be an inner loop which is 
> a branch-price-and-cut algorithm. Upon solving that subproblem, an outer 
> loop which adds model constraints would add one or more rows, and then I 
> would resolve the model-again using branch-price-and-cut. Any cutting 
> planes and primal solutions derived for the 'partial' problems are 
> likely helpful in solving the complete model.
> 
> Is it possible to ensure that SCIP runs its Primal Heuristics to 
> generate primal solutions for the problem where not all model rows have 
> yet been added? (Or does SCIP do so?) The main issue is that when adding 
> new model rows to the problem, the computed primal bound may become 
> worse and the solutions could become invalid. I could not find any 
> methods which reset the Primal bound, or which clear the solutions known 
> to SCIP. I looked into partial solutions, but it seems to me that they 
> have a different purpose. Is there a way to identify to SCIP's 
> heuristics that they should look for and report solutions to the 
> 'partial' model, which may be infeasible for the complete model? Perhaps 
> the restart or reoptimization features of SCIP can be helpful here?
> 
> Ofcourse, I could just run a new SCIP instance every time I add a model 
> constraint.  However, since I essentially only need to invalidate/change 
> the Primal bound and make the primal solutions in SCIPs internal cache 
> invalid, I was wondering if there was a better way to do this, which 
> does not involve copying all of the other problem data.
> 
> Best,
> 
> Rolf
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip