[Scip] Reusing cuts and other solution information

[Gregor Hendel]

Dear Michael,

I am deeply sorry that your first mail did not receive an answer.

Am 02.04.2015 um 20:13 schrieb 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?
I think the easiest way to achieve the reuse of cuts would be to create 
a new SCIP instance and copy the SCIP instance from the preceding 
iteration. Please see the documentation on SCIPcopy() 
<http://scip.zib.de/doc/html/scip_8h.php#ae0f9695c2985d240e1f09ec6a6fb640a>. 
Cuts, eg, are then converted into linear constraints. Through hash-maps 
you can access the copied variables and constraints and apply your 
modifications.
>
> 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?
I guess it is possible through the use of a custom relaxation handler 
<http://scip.zib.de/doc/html/RELAX.php> that solves the node Integer 
Problem by delegating the problem to a SCIP copy and solving it as a 
regular IP. Relaxation handlers can store relaxation solutions and 
declare candidates for relaxation branching. Afterwards, a branching 
rule should
take care of the result of the relaxed problem solution through the use 
of the BRANCHEXECEXT-callback.

I hope this serves as a starting point. Personally, I would advise you 
to start with a realization of the first approach because the 
implementation effort is considerably smaller, and it should be possible 
to straightforwardly reuse
the code for the second approach.

Cheers,
Gregor


>
> 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
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150407/a8da1bdb/attachment.html>