Topic
24 replies Latest Post - ‏2013-01-02T20:29:32Z by T_O
T_O
T_O
438 Posts
ACCEPTED ANSWER

Pinned topic How is the simplex refactoring frequency automatically determined?

‏2012-11-20T11:21:51Z |
We have a strange problem.

We wrote 2 different programs that (hopefully) build and modify the same linear program using the C API. First of all: We use dual simplex only, no barrier/concurrent.

Both CPLEX instances do exactly the same (we do some bound-modifications and reoptimize) until we add a row. After adding the row, the refactorings happen after a different number of iterations, if we don't set CPX_PARAM_REINV. This leads to different results (both results are ok but different). We wrote sav-files and compared all coefficients, rhs-values, etc.. The values are exactly the same. We also compared the parameters, the bases and basis headers before adding the row, there are no differences.

This does not seem to be machine dependant as it happens on a Mac with CPLEX 12.4.0.0 and on a 64-bit Linux machine with CPLEX 12.5.0.0. As long as we do not add the row, the simplex pivots are the same. They differ after some time when the refactoring frequency seems to change.

When we set CPX_PARAM_REINV to 10, this does not happen.

So what does CPX_PARAM_REINV == 0 mean? How is the frequency determined?

Best regards,
Thomas
Updated on 2013-01-02T20:29:32Z at 2013-01-02T20:29:32Z by T_O
  • RWunderling
    RWunderling
    98 Posts
    ACCEPTED ANSWER

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-20T11:43:28Z  in response to T_O
    Hi Thomas,

    if everything were identical, CPLEX should also reproduce the exact same solution paths. Thus it would really seem as if the added row differ (even if only in one bit) in both runs you are comparing, or both programs might be using different parameter settings.

    To your question: CPLEX compares the expected cost of a fresh factorization against the cost of solving the linear systems in a Simplex iteration. A fresh LU factorization is bound to have fewer non-zeros thus leading to faster solution times for the linear systems. In addition CPLEX may decide to trigger a fresh factorization due to numerical reasons.

    Regards,

    Roland
    • T_O
      T_O
      438 Posts
      ACCEPTED ANSWER

      Re: How is the simplex refactoring frequency automatically determined?

      ‏2012-11-20T12:10:00Z  in response to RWunderling
      Hi Roland,

      thank you for your fast answer. I just had a look at the sav-files and they contain the additional row. So, if I read them into CPLEX and compare the doubles, I should not lose any precision, should I?

      We exported the parameters as prm-file. Here they are:
      CPX_PARAM_SIMDISPLAY 2
      CPX_PARAM_PREIND 0
      CPX_PARAM_SCRIND 1
      CPX_PARAM_LPMETHOD 2
      CPX_PARAM_NUMERICALEMPHASIS 1

      We used CPX_PARAM_SIMDISPLAY = 1 in another run to see the factorization interval. The result was the same.

      One thing that my differ are the names of the rows and the columns (some might also be empty). I guess this should not have any influence as long as I use sav-files?

      Best regards,
      Thomas
      • T_O
        T_O
        438 Posts
        ACCEPTED ANSWER

        Re: How is the simplex refactoring frequency automatically determined?

        ‏2012-11-20T12:23:10Z  in response to T_O
        Hi,

        we just found out that this does not happen when every constraint has a (unique) name. Can there be a problem, when the name is the empty string?

        Best regards,
        Thomas
        • T_O
          T_O
          438 Posts
          ACCEPTED ANSWER

          Re: How is the simplex refactoring frequency automatically determined?

          ‏2012-11-20T13:29:56Z  in response to T_O
          Ok, we just found out that the difference seems to be depending on whether the last argument of CPXXaddrows is NULL or something else. Is there any reason for this?

          Best regards,
          Thomas
          • SystemAdmin
            SystemAdmin
            7929 Posts
            ACCEPTED ANSWER

            Re: How is the simplex refactoring frequency automatically determined?

            ‏2012-11-22T07:51:33Z  in response to T_O
            Yes, this can happen :-(
            CPLEX only guarantees to do the exact same things if the input is the exact same (including row and column names).
            I agree that this is not helpful here and will file a user wish to change that.
            • T_O
              T_O
              438 Posts
              ACCEPTED ANSWER

              Re: How is the simplex refactoring frequency automatically determined?

              ‏2012-11-22T10:52:36Z  in response to SystemAdmin
              Hi Daniel,

              thank you for the information.

              Is there any obvious / trivial explanation for this behaviour? Or is this something top secret?

              Best regards,
              Thomas
              • SystemAdmin
                SystemAdmin
                7929 Posts
                ACCEPTED ANSWER

                Re: How is the simplex refactoring frequency automatically determined?

                ‏2012-11-26T07:36:24Z  in response to T_O
                It turns out that I was wrong, sorry :-( What I had in mind as potential reason for the difference in behavior cannot happen here.
                Would it be possible to provide the two SAV files, the exact parameter settings (as PRM file) and an exact machine specification so that we can try to reproduce the problem here? If you don't want to attach the files here you can send them directly to me: daniel(dot)junglas(at)de(dot)ibm(dot)com.
                • T_O
                  T_O
                  438 Posts
                  ACCEPTED ANSWER

                  Re: How is the simplex refactoring frequency automatically determined?

                  ‏2012-11-26T09:56:14Z  in response to SystemAdmin
                  Hi Daniel,

                  this is a litte difficult as we thought that the problem was solved. I do not have all files at hand and we would have to create them again. I found 2 files that were created using the 2 different codes. I think they were created before the row was added that caused different solution values. You see that the final bases are already different (seems degenerate as in one case, x2 is basic and at upper bound). I just saw that in one file 2 constraints have the same name (c1). In the other file one of them does not have a name.

                  My colleague told me again that he was able to reduce the problem to the question whether you use NULL or something different as last argument of CPXXaddrows.

                  Best regards,
                  Thomas
                  • SystemAdmin
                    SystemAdmin
                    7929 Posts
                    ACCEPTED ANSWER

                    Re: How is the simplex refactoring frequency automatically determined?

                    ‏2012-11-28T07:50:09Z  in response to T_O
                    Sorry, so far I could not reproduce the issue here.
                    I get consistent solutions for both files, no matter whether I use a name in CPXXaddrows() or not. I will keep trying ...
                    • T_O
                      T_O
                      438 Posts
                      ACCEPTED ANSWER

                      Re: How is the simplex refactoring frequency automatically determined?

                      ‏2012-11-28T13:24:01Z  in response to SystemAdmin
                      Hi Daniel,

                      I am now able to reproduce the issue. The code creates the problem, then changes some bounds, reoptimizes a few times and then adds a new row and reoptimizes.

                      There are four cases:
                      1. Use an array as last argument of CPXXaddrows when creating the problem and when adding the row.
                      2. Use NULL as last argument of CPXXaddrows when creating the problem and when adding the row.
                      3. Use an array as last argument of CPXXaddrows when creating the problem and NULL when adding the row.
                      4. Use NULL as last argument of CPXXaddrows when creating the problem and an array when adding the row.

                      Everything else in the codes is now exactly the same.

                      1 and 2 behave exactly the same way and 3 and 4 behave exactly the same way. Strange!

                      I am not able to reproduce this in the interactive optimizer using sav and prm files.

                      Here is the prm file that I used now:
                      CPLEX Parameter File Version 12.5.0.0
                      CPX_PARAM_ITLIM                  1410065408
                      CPX_PARAM_PREIND                 0
                      CPX_PARAM_SCRIND                 1
                      CPX_PARAM_TILIM                  1.00000000000000e+06   
                      CPX_PARAM_DATACHECK              1
                      CPX_PARAM_LPMETHOD               2
                      CPX_PARAM_NUMERICALEMPHASIS      1
                      


                      If you have any further questions, please let me know. At the moment, I cannot provide the code, but I could provide sav, lp, prm, ... files.

                      Best regards,
                      Thomas
                      Updated on 2014-03-24T22:44:46Z at 2014-03-24T22:44:46Z by iron-man
                      • T_O
                        T_O
                        438 Posts
                        ACCEPTED ANSWER

                        Re: How is the simplex refactoring frequency automatically determined?

                        ‏2012-11-28T13:28:42Z  in response to T_O
                        Case 1/2:
                        
                        Reinitializing dual norms . . . Computed 1 
                        
                        new norms.   Iteration log . . . Iteration:     1   Dual objective     =         34864.000000 Iteration:   101   Dual objective     =         53219.500000 Iteration:   179   Dual objective     =         53935.580302 Iteration:   254   Dual objective     =         54247.194863 Iteration:   327   Dual objective     =         54504.450865 Iteration:   398   Dual objective     =         54914.001882 Iteration:   472   Dual objective     =         55106.559203 Iteration:   542   Dual objective     =         55231.481572 Iteration:   614   Dual objective     =         55288.040178 Iteration:   684   Dual objective     =         55354.848349 Iteration:   751   Dual objective     =         55438.607284 Iteration:   819   Dual objective     =         55475.761687 Iteration:   884   Dual objective     =         55512.701847 Iteration:   961   Dual objective     =         55532.056986
                        


                        Case 3/4:
                        
                        Reinitializing dual norms . . . Computed 1 
                        
                        new norms.   Iteration log . . . Iteration:     1   Dual objective     =         34864.000000 Iteration:    97   Dual objective     =         53008.003971 Iteration:   170   Dual objective     =         53600.113545 Iteration:   241   Dual objective     =         53946.767065 Iteration:   315   Dual objective     =         54389.202548 Iteration:   380   Dual objective     =         54807.014316 Iteration:   449   Dual objective     =         55105.116988 Iteration:   515   Dual objective     =         55247.793773 Iteration:   583   Dual objective     =         55345.401762 Iteration:   655   Dual objective     =         55433.628455 Iteration:   729   Dual objective     =         55489.569901 Iteration:   796   Dual objective     =         55524.939165
                        
                        • T_O
                          T_O
                          438 Posts
                          ACCEPTED ANSWER

                          Re: How is the simplex refactoring frequency automatically determined?

                          ‏2012-11-28T13:37:14Z  in response to T_O
                          With CPX_PARAM_SIMDISPLAY = 2, only interesting part:

                          Case 1/2:
                          
                          40           51890.000000                  x5712                     x3 41           51911.000000                  x8377                  x7927 42           51917.000000                  x4607                  x5747 43           51953.000000                  x4199                  x5751 44           51964.000000                  x3000                  x3013 45           51988.500000                  x3294                  x5070 46           51990.500000                  x5032                  x5028 47           52080.000000                  x2415                  x8104 48           52174.000000                  x8636                  x8094 49           52232.500000                  x4360                  x4878 50           52238.000000                  x5827                  x5409 51           52251.500000                    x84                  x6250 52           52255.000000                   x576                  x7232 53           52261.000000                  x6250                  x2746 54           52263.500000                  x1268                  x3662 55           52273.000000                  x7184                  x6593 56           52305.500000                  x1156                  x8586 57           52322.000000                  x4483 x6937 58           52335.000000                  x4702                    x31 59           52344.000000                  x4685                  x3673 60           52383.000000                  x1106                  x2903
                          


                          Case 3/4:
                          
                          40           51890.000000                  x5712                     x3 41           51911.000000                  x8377                  x7927 42           51917.000000                  x4607                  x5747 43           51953.000000                  x4199                  x5751 44           51964.000000                  x3000                  x3013 45           51988.500000                  x3294                  x5070 46           51990.500000                  x5032                  x5028 47           52080.000000                  x2720                  x8104 48           52188.500000                  x8636                  x8094 49           52196.500000                  x5827                  x5409 50           52241.166667                   x329                  x4878 51           52251.666667                  x1146                  x6250 52           52255.200000                    x84                  x5952 53           52261.533333                  x5952                  x3500 54           52283.033333                  x3118                  x1155 55           52295.033333                  x1268                  x3662 56           52306.633333                  x4483                  x8586 57           52386.633333                  x6488                     x9 58           52393.166667                  x4088                  x5827 59           52435.283333                  x5043                  x5952 60           52447.816667                  x4304                  x5879
                          
                      • SystemAdmin
                        SystemAdmin
                        7929 Posts
                        ACCEPTED ANSWER

                        Re: How is the simplex refactoring frequency automatically determined?

                        ‏2012-11-29T08:27:26Z  in response to T_O
                        Could you please provide SAV files for the cases 1 through 4?
                        Are you able to reproduce the problem in the interactive starting from those SAV files or does the problem only occur with the callable library?
                        When you build your problem (before adding the row), do you create all rows in one shot or do you invoke CPXXaddrows() multiple times?
                        • T_O
                          T_O
                          438 Posts
                          ACCEPTED ANSWER

                          Re: How is the simplex refactoring frequency automatically determined?

                          ‏2012-11-29T09:55:03Z  in response to SystemAdmin
                          Hi Daniel,

                          I will provide the sav files later. Concering your last question: CPXXaddrows is called one time to create the complete problem. Later, it is called one time to add the constraint.

                          Best regards,
                          Thomas
                          • T_O
                            T_O
                            438 Posts
                            ACCEPTED ANSWER

                            Re: How is the simplex refactoring frequency automatically determined?

                            ‏2012-11-29T10:57:38Z  in response to T_O
                            Hi Daniel,

                            here are the sav files and a prm file.

                            The number of iterations in the interactive optimizer is different from the number of iterations in the callable library, but they also differ between 1/2 and 3/4.

                            But nevermind. I just found out, that the problem must have happened before. The status of one of the nonbasic-variables differs (2 vs. 0). Sorry, that I did not notice this before. So maybe, I'll have to reinvestigate / provide earlier sav files.

                            Best regards,
                            Thomas
                            • SystemAdmin
                              SystemAdmin
                              7929 Posts
                              ACCEPTED ANSWER

                              Re: How is the simplex refactoring frequency automatically determined?

                              ‏2012-11-29T16:06:50Z  in response to T_O
                              One more question: Do you create a new environment for each solve or do you solve one or more models within the same environment?
                              • T_O
                                T_O
                                438 Posts
                                ACCEPTED ANSWER

                                Re: How is the simplex refactoring frequency automatically determined?

                                ‏2012-11-29T19:38:25Z  in response to SystemAdmin
                                Hi Daniel,

                                inside the program, one model is modified and solved multiple times. The 4 cases were created compiling the program differently.

                                By the way: I did some further investigations today. The problem actually appears before the row is added. There, lots of bounds are changed (without reoptimizing immediately). One of these changes causes a nonbasic-variable to have status 0 in one case and 2 in the other case. I could not finish my investigations today and will try to continue tomorrow.

                                Best regards,
                                Thomas
                                • T_O
                                  T_O
                                  438 Posts
                                  ACCEPTED ANSWER

                                  Re: How is the simplex refactoring frequency automatically determined?

                                  ‏2012-12-03T13:39:34Z  in response to T_O
                                  Hi Daniel,

                                  I did some further investigations. In the program, a lot of bounds are changed. After a certain number of bound changes, I added the following lines of code:

                                  
                                  
                                  
                                  if( solveCounter == GRRNUM - 2 )
                                  { 
                                  
                                  char a; std::cout << 
                                  "Debug (a/b/c)? " << std::endl; std::cin >> a; 
                                  
                                  if( a == 
                                  'a' ) 
                                  { CPXXwriteprob( iloEnvCl, iloLpCl, 
                                  "/tmp/debugUnused.sav", NULL ); 
                                  } 
                                  
                                  else 
                                  
                                  if( a == 
                                  'b' ) 
                                  { std::vector<int> cstat( CPXXgetnumcols( iloEnvCl, iloLpCl ) ); std::vector<int> rstat( CPXXgetnumrows( iloEnvCl, iloLpCl ) ); CPXXgetbase( iloEnvCl, iloLpCl, cstat.data(), rstat.data() ); 
                                  } 
                                  
                                  else 
                                  { 
                                  // do nothing 
                                  } 
                                  }
                                  


                                  In the cases a and b, the program behaves differently than in the else-case (where one of the nonbasic variable switches its status). I would expect, that none of these operations could modify the problem, so it might be a memory problem in our code?

                                  I also attached the sav file but I think it won't help.

                                  Please let me know if you have any further ideas.

                                  Best regards,
                                  Thomas
                                  • SystemAdmin
                                    SystemAdmin
                                    7929 Posts
                                    ACCEPTED ANSWER

                                    Re: How is the simplex refactoring frequency automatically determined?

                                    ‏2012-12-05T12:27:05Z  in response to T_O
                                    I am not exactly sure but from what you report I think the problem may be caused by the CPLEX cache. For sake of performance CPLEX internally caches updates to the problem and only applies them when required (applying a bunch of modifications in one shot is faster than applying all of them individually).
                                    If you write out the problem or query the number of rows/columns then this will/may trigger a flushing of the internal cache.
                                    Flushing the cache can also be explicitly triggered by calling CPXXcompletelp. So the cases a and b in your example should be equivalent to explicitly calling CPXXcompletelp() at that place. Could try if that is the case?
                                    • T_O
                                      T_O
                                      438 Posts
                                      ACCEPTED ANSWER

                                      Re: How is the simplex refactoring frequency automatically determined?

                                      ‏2012-12-05T13:08:57Z  in response to SystemAdmin
                                      Hi Daniel,

                                      yes, CPXXcompletelp is equivalent to cases a and b.

                                      Best regards,
                                      Thomas
                                      • SystemAdmin
                                        SystemAdmin
                                        7929 Posts
                                        ACCEPTED ANSWER

                                        Re: How is the simplex refactoring frequency automatically determined?

                                        ‏2012-12-11T12:24:43Z  in response to T_O
                                        Just to keep you up to date: I am still working on this but so far have failed to reproduce the problem here.
                                        I was running several variations of the following scheme (because I understand that is essentially what your code is doing):
                                        1. Read one of the SAV files you provided.
                                        2. Copy everything but the last row into a new problem (either with or without assigning names to the rows).
                                        3. Solve the problem.
                                        4. Perform some bound changes, optionally call CPXXcompletelp() after some changes.
                                        5. Add the last row from the problem read in 1 to the problem (either with or without a row name).
                                        6. Solve the problem again.
                                        In step 4 I basically change bounds for a random set of variables and finally reset all bounds to their original value.
                                        As long as I perform the same bound changes in the same order I never get different results. In order to get different results (and the difference usually is a change of basis status from 0 to 2 or vice versa) I have to perform different bound changes in different runs (although the final model is the same since I always reset to original bounds). But in that case I think one cannot expect the same results anyway.

                                        I also had a look at the CPLEX source code but could find anything obvious that would explain the behavior you observe.

                                        I will keep working on this.
                                        • T_O
                                          T_O
                                          438 Posts
                                          ACCEPTED ANSWER

                                          Re: How is the simplex refactoring frequency automatically determined?

                                          ‏2012-12-12T12:46:33Z  in response to SystemAdmin
                                          Daniel,

                                          thank you very much. I tried to create a minimal example, but this basically ended up in extracting all CPLEX-calls from our code. I attached the code. There are 3 cases (see occurences of variable "mycase") which should produce equivalent sav files (up to row-names). Case 0 is my base case. Case 1 uses NULL as last argument of CPXXaddrows. Case 2 calls CPXXcompletelp after a certain amount of steps.
                                          In case 0, the base status of column 5034 is different than in cases 1 and 2. I cannot see any other differences (up to row-names).

                                          Best regards,
                                          Thomas
                                          • SystemAdmin
                                            SystemAdmin
                                            7929 Posts
                                            ACCEPTED ANSWER

                                            Re: How is the simplex refactoring frequency automatically determined?

                                            ‏2013-01-02T16:53:51Z  in response to T_O
                                            Thomas,

                                            thanks a lot for your patience and persistence in this issue.
                                            Using your example code I was finally able to reproduce the problem here and figure out what is going wrong.
                                            As we already guessed, the problem is within the caching mechanism of CPLEX. Without going too much into details (the issue is really subtle) here is roughly what happens:
                                            • If an internal starting basis is available then usually CPXXchgbds() attempts to update that basis when bounds are changed (by adjusting the basis status of variables). This update is performed only if a certain internal flag is set.
                                            • If you call CPXXaddrows() with a non-NULL row name then this internal flag may get set to a different value than in the case in which you call CPXXaddrows() with rownames=NULL.
                                            So depending on the name array being NULL or not CPXXchgbds() will update the starting basis or not. This explains why there are differences in the basis in the cases 0 and 1 in your code and I think the differences in the basis can explain the rest of the problems you described in this thread.
                                            We consider this a bug and will try to fix that.
                                            IMO the best way to avoid this issue is to always use rowname=NULL. If you use rowname!=NULL then the internal flag may again be changed, depending on whether internal name arrays need reallocation or not.
                                            • T_O
                                              T_O
                                              438 Posts
                                              ACCEPTED ANSWER

                                              Re: How is the simplex refactoring frequency automatically determined?

                                              ‏2013-01-02T20:29:32Z  in response to SystemAdmin
                                              Daniel,

                                              happy new year and thanks for your investigations! I think we will use NULL, if we do not need the row names.

                                              Best regards,
                                              Thomas