[Scip] Reusing cuts and other solution information

[Hewitt, Michael]

I am working on an iterative refinement algorithm for a class of fixed charge network design integer programs
that iteratively solves relaxations of the original problem. When the solution to a relaxation can not be mapped
to a solution of equal cost to the original problem, we refine the relaxation and solve again. 
The relaxation solved at each iteration is an integer program. 

When we refine the integer program we do three things (not always the third but nearly always):
1) Add a variable
2) Modify the constraints a variable participates in
3) Add a constraint

That said we do not refine the integer program that much; e.g. it's a network design problem and 
we may add just one node to the network and change/add a handful arcs. The refinement is done in such a
way that the relaxations only get tighter. As such, ideally the cuts (flow cover, cover, etc.) that are valid for the
relaxation solved in iteration k are valid for all further relaxations. Thus, ideally, they'd be re-used. Right now
I have implemented the algorithm in CPLEX and they are not. Given that the IPs are not trivial to solve I think
re-using these cuts could make for a significant speed-up in the code.

If I were to implement this algorithm in SCIP, e.g. the code solves the MIP, refines it, and then solves it again,
would the cuts be re-used? Instead of modifying the constraints a variable participates in we could instead fix
that variable to 0 and add a new one. Would that change SCIPs behavior?

If not, I think there is another approach to implementing the algorithm. Namely, it could be implemented within a 
branch-and-bound search tree. Namely, we feed the initial relaxation to SCIP to solve. Then at a node in the 
search tree where an integer-feasible solution is found we refine the network as per the 3 steps listed above.
In this sense our algorithm could be thought of as being like Branch-and-price-and-cut, particularly if instead
of modifying the constraints some variables participate in we just fix those variables to zero and add new ones.

Would this second implementation be possible in SCIP?

Thanks and sorry for the long email,

Mike Hewitt
Department of Information Systems & Operations Management
Quinlan School of Business
Loyola University Chicago
820 N. Michigan Ave
Chicago, IL, 60611
312-915-7394
mhewitt3 at luc.edu