Topic
  • 24 replies
  • Latest Post - ‏2013-01-02T20:29:32Z by T_O
T_O
T_O
448 Posts

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
    106 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-20T11:43:28Z  
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-20T12:10:00Z  
    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
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-20T12:23:10Z  
    • T_O
    • ‏2012-11-20T12:10:00Z
    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
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-20T13:29:56Z  
    • T_O
    • ‏2012-11-20T12:23:10Z
    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
    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

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-22T07:51:33Z  
    • T_O
    • ‏2012-11-20T13:29:56Z
    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
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-22T10:52:36Z  
    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.
    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

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-26T07:36:24Z  
    • T_O
    • ‏2012-11-22T10:52:36Z
    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
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-26T09:56:14Z  
    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.
    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

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-28T07:50:09Z  
    • T_O
    • ‏2012-11-26T09:56:14Z
    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
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-28T13:24:01Z  
    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 ...
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-28T13:28:42Z  
    • T_O
    • ‏2012-11-28T13:24:01Z
    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:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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 </pre>

    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
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-28T13:37:14Z  
    • T_O
    • ‏2012-11-28T13:28:42Z
    Case 1/2:
    <pre class="jive-pre"> 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 </pre>

    Case 3/4:
    <pre class="jive-pre"> 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 </pre>
    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

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-29T08:27:26Z  
    • T_O
    • ‏2012-11-28T13:24:01Z
    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:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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 </pre>

    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
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-29T09:55:03Z  
    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?
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-29T10:57:38Z  
    • T_O
    • ‏2012-11-29T09:55:03Z
    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
    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

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-29T16:06:50Z  
    • T_O
    • ‏2012-11-29T10:57:38Z
    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
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-11-29T19:38:25Z  
    One more question: Do you create a new environment for each solve or do you solve one or more models within the same environment?
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-12-03T13:39:34Z  
    • T_O
    • ‏2012-11-29T19:38:25Z
    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
    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

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-12-05T12:27:05Z  
    • T_O
    • ‏2012-12-03T13:39:34Z
    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:

    <pre class="jive-pre"> 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 } } </pre>

    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
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-12-05T13:08:57Z  
    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?
    Hi Daniel,

    yes, CPXXcompletelp is equivalent to cases a and b.

    Best regards,
    Thomas
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-12-11T12:24:43Z  
    • T_O
    • ‏2012-12-05T13:08:57Z
    Hi Daniel,

    yes, CPXXcompletelp is equivalent to cases a and b.

    Best regards,
    Thomas
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2012-12-12T12:46:33Z  
    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.
    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

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2013-01-02T16:53:51Z  
    • T_O
    • ‏2012-12-12T12:46:33Z
    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
    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
    448 Posts

    Re: How is the simplex refactoring frequency automatically determined?

    ‏2013-01-02T20:29:32Z  
    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.
    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