Topic
18 replies Latest Post - ‏2013-12-10T06:48:52Z by DanielJunglas
MarkusS.
MarkusS.
29 Posts
ACCEPTED ANSWER

Pinned topic C++: Get LP-relaxation value at root node without stopping branch-and-cut

‏2012-09-06T09:09:42Z |
Hello!

I need to get the objective value of the LP-relaxation at the root node (I only need the objective and not the values of the variables itself). I've seen some posts on this topic (i.e. https://www.ibm.com/developerworks/forums/thread.jspa?messageID=14475701&#14475701), however, in my case stopping the branch-and-cut at the root node is not an option.

Thank you for your help,
Markus
Updated on 2013-02-05T09:34:22Z at 2013-02-05T09:34:22Z by hllsen
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

    ‏2012-09-07T22:09:03Z  in response to MarkusS.
    You could attach a SolveCallback with an internal flag that is initially set true. It would call solve() and then, if the flag were true, call getObjValue(), record the result and set the flag to false.

    Paul

    Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

    ‏2012-09-17T20:39:04Z  in response to MarkusS.
    If you remove this line
    IloCplex::BranchCallbackI::abort();
    

    from the code example in the quoted thread then the solve does not stop at the root node. Like Paul suggested you should also add a flag that is initially true. If the callback's main() function is executed for the first time you set the flag to false and store the objective function value somewhere. In subsequent invocations of the main() function you just don't do anything. Notice however that adding a control callback (branch callback or solve callback) will disable dynamic search and may therefore hurt performance.
    What is the problem with interrupting the solve at the root node? Consider the following code sequence:
    cplex.setParam(IloCplex::IntParam::NodeLim, 0); // Stop after root node.
    if ( solve() ) {
       double rootObjective = cplex.getBestObjValue();
       cplex.setParam(IloCplex::IntParam::NodeLim, 210000000);
       solve(); // Continue solve.
    }
    

    This will interrupt the solve after the root node. You can query the dual bound and invoke solve() again. Since you did not modify the problem the second solve() will continue just where the first one stopped.
    Updated on 2014-03-24T22:52:26Z at 2014-03-24T22:52:26Z by iron-man
    • UserCplex
      UserCplex
      30 Posts
      ACCEPTED ANSWER

      Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

      ‏2012-09-27T13:19:03Z  in response to SystemAdmin
      Hi Daniel,

      This is precisely what I was looking for. My other thread can be cleaned up, if needed. However, I have a query. Your code reads:

      cplex.setParam(IloCplex::IntParam::NodeLim, 0); // Stop after root node.
      if ( solve() ) {
      double rootObjective = cplex.getBestObjValue();
      cplex.setParam(IloCplex::IntParam::NodeLim, 210000000);
      solve(); // Continue solve.
      }

      Now, what is the difference between the above and having the first line as:

      cplex.setParam(IloCplex::IntParam::NodeLim, 1);//Note the 1 instead of 0?

      Also, in your original code, is the getBestObjValue() function going to return the LP solution or any feasible integer solution that CPLEX found while preprocessing/applying heuristics, etc.?

      Thanks.
      • SystemAdmin
        SystemAdmin
        7929 Posts
        ACCEPTED ANSWER

        Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

        ‏2012-10-01T09:43:41Z  in response to UserCplex
        > This is precisely what I was looking for. My other thread can be cleaned up, if needed. However, I have a query. Your code reads:
        >
        > cplex.setParam(IloCplex::IntParam::NodeLim, 0); // Stop after root node.
        > if ( solve() ) {
        > double rootObjective = cplex.getBestObjValue();
        > cplex.setParam(IloCplex::IntParam::NodeLim, 210000000);
        > solve(); // Continue solve.
        > }
        >
        > Now, what is the difference between the above and having the first line as:
        >
        > cplex.setParam(IloCplex::IntParam::NodeLim, 1);//Note the 1 instead of 0?
        >
        The difference is subtle and not important in this case. NodeLim=1 stops after the root node is completely done, a first branching decision has been made, the next node is selected (but not yet processed) etc. NodeLim=0 just stops a little earlier.

        > Also, in your original code, is the getBestObjValue() function going to return the LP solution or any feasible integer solution that CPLEX found while preprocessing/applying heuristics, etc.?
        >
        getBestObjValue() returns the dual bound, which in this case (the root node) is the LP relaxation at the root node.
        Integer feasible solutions are accessed via getIncumbentObjValue() etc.
        • hllsen
          hllsen
          51 Posts
          ACCEPTED ANSWER

          Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

          ‏2013-01-22T18:49:11Z  in response to SystemAdmin
          Maybe out of the scope of this question however I am going to use the same method to obtain the root relaxation bound+time and I wondered what happens if the first solve() ends due to time limit.

          In the Cplex manual it says that subsequent calls to solve() have their own TiLim. Therefore, we need to check the solution status; otherwise if the first solve ends with a solution status 11, 107, or 108 (btw, are there any other easier way to check this? ) then we don't have a bound (probably it will give infinity as a bound or worse, an error; this is okay though) but the problem is that Cplex is going to try to solve the problem again, although the time we allow already passed, etc.

          This is a plausible scenario for me and my solution is the following, please correct me if anything is wrong:
          
          cplex.setParam(IloCplex::TiLim, My.TiLim); 
          // Original time limit cplex.setParam(IloCplex::NodeLim, 0);      
          // Stop after root node to get root relaxation time and objective 
          
          if ( cplex.solve() ) 
          { Root.Time = cplex.getTime(); Root.Status =  cplex.getCplexStatus(); Root.Bound = cplex.getBestObjValue();   
          // *Does this line produce an error if the time limit is reached?* 
          
          if ( Root.Status != IloCplex::AbortTimeLim || ( Root.Status == IloCplex::NodeLimInfeas || Root.Status == IloCplex::NodeLimFeas ) ) 
          { 
          // *Are there any other possible statuses to consider? Or what is the best way to check this?* Root.Bound = cplex.getBestObjValue();                   
          // Get Objective cplex.setParam(IloCplex::NodeLim, 210000000);           
          // Set Node limit to default value cplex.setParam(IloCplex::TiLim, My.TiLim - Root.Time ); 
          // Modify the time limit cplex.solve(); 
          // Continue solve. 
          } 
          }
          
          • SystemAdmin
            SystemAdmin
            7929 Posts
            ACCEPTED ANSWER

            Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

            ‏2013-01-25T09:36:10Z  in response to hllsen
            I think there are some flaws in your code:
            • cplex.solve() will only return true if an integer feasible solution is available. So if CPLEX does not find an integer feasible solution before the time limit expires or the root node is complete (whichever comes first) your code will probably not work as expected.
            • Since cplex.solve() returns true only if a feasible solution is available, status IloCplex::NodeLimInfeas cannot happen (at least not in the current state of your code).
            • cplex.getTime() does only return a timestamp, not the time CPLEX spent so far. So you need to do record the timestamp before you call solve() and then calculate the different of this time stamp to cplex.getTime() to get the elapsed time. In the current code My.TiLim - Root.Time will not produce the remaining time budget.
            Function IloCplex::getBestObjValue() should not throw an exception if the solve was terminated by a time limit. It should return a valid dual bound (which may be infinite).
            • hllsen
              hllsen
              51 Posts
              ACCEPTED ANSWER

              Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

              ‏2013-02-02T20:27:17Z  in response to SystemAdmin
              Thank you Daniel for the comments. It was a rough week so I couldn't find the time to write back and I already applied your suggestions. But, now I'm having a different problem with the cplex time limit: Although TiLim parameter set to 600 seconds, it takes 1495 seconds for cplex.solve() to stop and extra ~900 seconds to release the memory. I know the model is huge but is this kind of timing results expected?
              Presolve has eliminated 0 rows and 1 columns...
              Presolve has eliminated 0 rows and 28767 columns...
              Presolve has eliminated 222 rows and 28767 columns...
              Tried aggregator 1 time.
              Presolve has eliminated 222 rows and 28767 columns...
              MIP Presolve eliminated 222 rows and 28767 columns.
              Reduced MIP has 37903 rows, 3773734 columns, and 224162878 nonzeros.
              Reduced MIP has 3773734 binaries, 0 generals, 0 SOSs, and 0 indicators.
              Presolve time =  222.52 sec.
              Dual steepest-edge pricing selected.
               
                      Nodes                                         Cuts/ 
                 Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
               
                    0     0 -1.00000e+037     0                                    0
               
              Root node processing (before b&c):
                Real time             = 1495.41
              Parallel b&c, 7 threads:
                Real time             =    0.00
                Sync time (average)   =    0.00
                Wait time (average)   =    0.00
                                        -------
              Total (root+branch&cut) = 1495.41 sec.
              
              Updated on 2014-03-24T22:40:57Z at 2014-03-24T22:40:57Z by iron-man
              • hllsen
                hllsen
                51 Posts
                ACCEPTED ANSWER

                Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

                ‏2013-02-02T20:46:19Z  in response to hllsen
                I forgot to mention that while releasing the memory MyProgram.exe does not use that much CPU (may be this is usual?) and after some point CPU usage drops to zero but the memory usage fluctuates as if Cplex is solving/doing something and releases memory "slowly" packet by packet.

                Also, Cplex uses 15gigs during the pre-solve operation but even if the working memory limit is set to 15gigs and NodeFileInd is at its default, cplex claims more than 25gigs while starting the B&B.
                • SystemAdmin
                  SystemAdmin
                  7929 Posts
                  ACCEPTED ANSWER

                  Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

                  ‏2013-02-05T06:37:45Z  in response to hllsen
                  > hllsen wrote:
                  > I forgot to mention that while releasing the memory MyProgram.exe does not use that much CPU (may be this is usual?) and after some point CPU usage drops to zero but the memory usage fluctuates as if Cplex is solving/doing something and releases memory "slowly" packet by packet.
                  >
                  How does the code look that releases the memory? Do you release both the IloModel and the IloCplex instance? Or only one of them? If you release the IloModel instance, does it help to add
                  cplex.extract(IloModel(env));
                  

                  before calling model.end()? There is quite some notification going on between IloCplex and an extracted IloModel and this may slow down deletion of a model (you can search this forum or the FAQs for this issue). If you release the IloCplex and the IloModel instance then try to first release the IloCplex instance and then the IloModel instance.

                  > Also, Cplex uses 15gigs during the pre-solve operation but even if the working memory limit is set to 15gigs and NodeFileInd is at its default, cplex claims more than 25gigs while starting the B&B.
                  >
                  A potential reason for this may be that a copy of the model is created for each thread. How many threads do you use? Does the memory consumption go down if you use fewer threads?
                  Updated on 2014-03-24T22:40:49Z at 2014-03-24T22:40:49Z by iron-man
                  • SystemAdmin
                    SystemAdmin
                    7929 Posts
                    ACCEPTED ANSWER

                    Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

                    ‏2013-02-05T06:43:57Z  in response to SystemAdmin
                    Sorry, what I suggested results in a memory leak. Instead of
                    cplex.extract(IloModel(env));
                    

                    just try
                    cplex.clearModel();
                    

                    Both statements will "disconnect" the big model from the IloCplex instance so that the IloCplex instance is no longer notified of all the changes that are made to the model.
                    Updated on 2014-03-24T22:40:39Z at 2014-03-24T22:40:39Z by iron-man
                    • hllsen
                      hllsen
                      51 Posts
                      ACCEPTED ANSWER

                      Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

                      ‏2013-02-05T09:33:18Z  in response to SystemAdmin
                      Actually, I am releasing the memory by ending the environment. That is
                      env.end();
                      

                      I'll let you know the results when I'll be able to try the clearModel() trick and less number of threads.
                      Updated on 2014-03-24T22:40:34Z at 2014-03-24T22:40:34Z by iron-man
                    • hllsen
                      hllsen
                      51 Posts
                      ACCEPTED ANSWER

                      Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

                      ‏2013-02-05T09:34:22Z  in response to SystemAdmin
                      Actually, I am releasing the memory by ending the environment. That is
                      env.end();
                      

                      I'll let you know the results when I'll be able to try the clearModel() trick and less number of threads.
                      Updated on 2014-03-24T22:40:29Z at 2014-03-24T22:40:29Z by iron-man
              • SystemAdmin
                SystemAdmin
                7929 Posts
                ACCEPTED ANSWER

                Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

                ‏2013-02-05T06:34:16Z  in response to hllsen
                What version of CPLEX do you use? Overshooting the time limit by so much is not expected and sounds like a bug. Is it possible to attach a .SAV file for the model here or send to me daniel(dot)junglas(at)de(dot)ibm(dot)com?
                How many threads do you use? If you leave the threads parameter at its default value, how many CPUs do you have?
                • hllsen
                  hllsen
                  51 Posts
                  ACCEPTED ANSWER

                  Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

                  ‏2013-02-05T09:24:27Z  in response to SystemAdmin
                  The version is 12.4.0.1, and I will try to send the .SAV file during the day. I am using 7 threads on a Intel i7 920 (i.e. 4 core, 8 threads with Hyper-Threading).
    • semihatakan
      semihatakan
      2 Posts
      ACCEPTED ANSWER

      Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

      ‏2013-12-05T05:24:55Z  in response to SystemAdmin

      Hi,

      I have a question regarding your code below. The code works perfectly fine however when I fill the user cut pool of cplex with some valid inequalities, the second solve command gives an exception (bad access). Unless I give enough node limit (or time limit) so that the optimal solution is achieved, I cannot avoid the exception. 

      Is there a particular reason for that? (e.g., am I allowed to do this while using the cplex's user cut pool??) 

      
      cplex.setParam(IloCplex::IntParam::NodeLim, 0); 
      // Stop after root node. 
      
      if ( solve() ) 
      { 
      
      double rootObjective = cplex.getBestObjValue(); cplex.setParam(IloCplex::IntParam::NodeLim, 210000000); solve(); 
      // Continue solve. 
      }
      
      • DanielJunglas
        DanielJunglas
        1377 Posts
        ACCEPTED ANSWER

        Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

        ‏2013-12-05T06:39:28Z  in response to semihatakan

        Adding cuts to the user cut pool should not be a problem here. Do you have a stack trace for that bad access exception? How exactly do you add the user cuts? Is it possible that you end() one of the cuts before you start the second solve()?

        • semihatakan
          semihatakan
          2 Posts
          ACCEPTED ANSWER

          Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

          ‏2013-12-05T07:08:30Z  in response to DanielJunglas

          Hi Daniel, 

          Thanks a lot for the fast response.

          The code for adding the cuts are below, valid_inequalities is an IloConstraintArray:

                  cplex.addUserCuts( valid_inequalities );  

                  valid_inequalities.endElements();

                  valid_inequalities.end();

          I do end them just after adding them to cplex, but this is correct right? The cuts are added after the model is extracted to cplex. I do not use any usercut callbacks. Then, I call the following sequence of solves:

                  cplex.setParam(IloCplex::NodeLim, 0);

                  solved = cplex.solve();

                  cplex.solve();

          The second solve gives an exception unless I clear all the usercuts (or solve to optimality). There is nothing else between these solves (nothing is end()'ed). Also, the same number of user cuts is displayed in the CPLEX log for the second solve, but then the exception occurs. The last message I can see is the "Parallel Mode: none, ....".

          About the stack trace, I don't know what it means :/. However, I followed the location of the bug (maybe this is stack trace, again don't know..)

            IloBool solve() { return IloAlgorithm::solve(); }    // The message is: EXC_BAD_ACCESS (code=1, address=0x10572e888)

          Going deeper, the exception seemed to be in IloAlgorithm::callSolve() const:

          0x10002828c:  movq   %rax, %r14     // exception is at this line

          Do these help? There is one more step, but it doesn't seem human readable.

          Just to let you know, I managed to get the info that I want through MIPINFOCALLBACK, so this is not urgent. But still curious of what might have caused the exception...

          Thanks a lot

           

           

          Updated on 2013-12-05T07:10:39Z at 2013-12-05T07:10:39Z by semihatakan
          • DanielJunglas
            DanielJunglas
            1377 Posts
            ACCEPTED ANSWER

            Re: C++: Get LP-relaxation value at root node without stopping branch-and-cut

            ‏2013-12-10T06:48:52Z  in response to semihatakan

            So far I have failed to reproduce this problem here. Doing things like you described works without a flaw for me. If you still need to get to the bottom of that issue, could you create a minimal example that shows the crash and post that here or send it directly to daniel(dot)junglas(at)de(dot)ibm(dot)com?