<html>

  <head>

    <meta content="text/html; charset=windows-1252"

      http-equiv="Content-Type">

  </head>

  <body bgcolor="#FFFFFF" text="#000000">

    <div class="moz-cite-prefix">Dear Michael,<br>

      <br>

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

      <br>

      <br>

      Am 02.04.2015 um 20:13 schrieb Hewitt, Michael:<br>

    </div>

    <blockquote cite="mid:5E1D0A01-BF71-46A5-BDDC-9590AB214478@luc.edu"

      type="cite">

      <pre wrap="">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?</pre>

    </blockquote>

    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 <a

href="http://scip.zib.de/doc/html/scip_8h.php#ae0f9695c2985d240e1f09ec6a6fb640a">SCIPcopy()</a>.

    Cuts, eg, are then converted into linear constraints. Through

    hash-maps you can access the copied variables and constraints and

    apply your modifications.<br>

    <blockquote cite="mid:5E1D0A01-BF71-46A5-BDDC-9590AB214478@luc.edu"

      type="cite">

      <pre wrap="">

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?</pre>

    </blockquote>

    I guess it is possible through the use of a <a

      href="http://scip.zib.de/doc/html/RELAX.php">custom relaxation

      handler</a> 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 <br>

    take care of the result of the relaxed problem solution through the

    use of the BRANCHEXECEXT-callback.<br>

    <br>

    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<br>

    the code for the second approach.<br>

    <br>

    Cheers,<br>

    Gregor<br>

    <br>

    <br>

    <blockquote cite="mid:5E1D0A01-BF71-46A5-BDDC-9590AB214478@luc.edu"

      type="cite">

      <pre wrap="">

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

<a class="moz-txt-link-abbreviated" href="mailto:mhewitt3@luc.edu">mhewitt3@luc.edu</a>

_______________________________________________

Scip mailing list

<a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a>

<a class="moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip">http://listserv.zib.de/mailman/listinfo/scip</a>

</pre>

    </blockquote>

    <br>

  </body>

</html>