Topic
  • 25 replies
  • Latest Post - ‏2012-05-01T23:14:46Z by EdKlotz
Eumpfenbach
Eumpfenbach
198 Posts

Pinned topic Ill Conditioned Problem

‏2012-04-12T00:47:44Z |
Pretty sure I have a linear programming that would fall under the category of "ill-conditioned". I want to solve it using column generation (so, with presolve off).

If I just solve with the standard cplex algorithm, there is a giant difference in solve time with presolve on/off. With Presolve on, I see this information printed (using Matlab API).

Tried aggregator 1 time.
MIP Presolve eliminated 394 rows and 101 columns.
MIP Presolve modified 59535 coefficients.
Reduced MIP has 67028 rows, 55287 columns, and 389241 nonzeros.
Reduced MIP has 255 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing time =    0.05 sec.
Tried aggregator 1 time.
Reduced MIP has 67028 rows, 55287 columns, and 389241 nonzeros.
Reduced MIP has 255 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time =    0.55 sec.
Found feasible solution after 0.64 sec.  Objective = -1.8148e+010


My question: Is there anything in this information that points to the likely cause of the performance gap? Is it scaling? Something else that presolve might be doing (I am assuming that removing 400 rows and 100 columns has little impact on the solution time, given the size of the problem)? Is there any way that I can make cplex presolve agree with column generation? (I tried setting presolve.reduce = 0. It no longer removed the rows or columns, but also got rid of the message "MIP Presolve modified 59535 coefficients", which I am assuming is the part that is greatly improving performance.).

Any advice would be greatly appreciated. Hopefully that can save me from having to do trial and error on my own. Thanks.
Updated on 2014-03-24T23:03:03Z at 2014-03-24T23:03:03Z by iron-man
  • T_O
    T_O
    445 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-12T12:05:27Z  
    Did you try to solve your model with presolver and then to resolve without presolver?

    Best regards,
    Thomas
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-12T13:35:18Z  
    • T_O
    • ‏2012-04-12T12:05:27Z
    Did you try to solve your model with presolver and then to resolve without presolver?

    Best regards,
    Thomas
    Yes, there is a VERY large performance gap. I clearly need to presolve, but am also doing column generation. Therefore I need to:

    1) Make cplex presolve compatible with CG (I was kinda hoping that maybe as long as I didn't remove any rows or columns it would be. I'm not sure if it says cplex "modified coefficients" whether this means the dual of my solution is not a proper dual of the original problem. Maybe this is wishful thinking).

    or

    2) Create my own presolve routine. In this case, I was hoping for expert opinion as to what is the presolve routine most likely to cause the giant performance gap (I know no one can tell me for sure, but just an educated guess) so that I can try and do it myself.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-12T18:15:50Z  
    I do not understand what you are trying to do. Apparently your are solving a MIP. How are you going to use column generation for this? You will not get duals!

    Or is it more like a rolling horizon application where you start with a small problem, and then use the solution of one period as a MIP start for the next solve?
    Tobias
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-12T19:05:03Z  
    I do not understand what you are trying to do. Apparently your are solving a MIP. How are you going to use column generation for this? You will not get duals!

    Or is it more like a rolling horizon application where you start with a small problem, and then use the solution of one period as a MIP start for the next solve?
    Tobias
    I have an MIP where the number of continuous variables is much, much greater than the number of binaries. Thus I am trying to use column generation to solve the subproblems efficiently. I have a separate branch-and-bound code and call cplex to solve the subproblems. I have had test trials where this approach was 5 times faster than cplex (due to greatly accelerated solving of the relaxations).
    Now I am using a different data set and believe it to be ill-conditioned. I need to do something to correct the problem.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-13T00:15:30Z  
    I have an MIP where the number of continuous variables is much, much greater than the number of binaries. Thus I am trying to use column generation to solve the subproblems efficiently. I have a separate branch-and-bound code and call cplex to solve the subproblems. I have had test trials where this approach was 5 times faster than cplex (due to greatly accelerated solving of the relaxations).
    Now I am using a different data set and believe it to be ill-conditioned. I need to do something to correct the problem.
    And where do those presolve logs come from? Those are for MIPs, but as far as I understand you are using CPLEX only to solve the LP relaxations inside your own branch-and-bound framework...
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-13T00:47:26Z  
    And where do those presolve logs come from? Those are for MIPs, but as far as I understand you are using CPLEX only to solve the LP relaxations inside your own branch-and-bound framework...
    Correct. It is the same problem. I just posted logs from when I solve the full MIP as a standard cplex problem, not one of the relaxations. If it makes a difference, here is a log from the initial LP relaxation of the same problem:

    Selected objective sense:  MINIMIZE
    Selected objective  name:  R67423
    Selected RHS        name:  B
    Selected bound      name:  BOUND
    Parallel mode: deterministic, using up to 2 threads for concurrent optimization.
    Tried aggregator 1 time.
    LP Presolve eliminated 190 rows and 101 columns.
    Reduced LP has 67232 rows, 55287 columns, and 426827 nonzeros.
    


    I still suspect it is scaling. Scaling is disabled when presolve is turned off, right? I'm trying to write my own script to rescale the problem.
    Updated on 2014-03-24T23:05:53Z at 2014-03-24T23:05:53Z by iron-man
  • EdKlotz
    EdKlotz
    244 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-13T15:54:53Z  
    Correct. It is the same problem. I just posted logs from when I solve the full MIP as a standard cplex problem, not one of the relaxations. If it makes a difference, here is a log from the initial LP relaxation of the same problem:

    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">Selected objective sense: MINIMIZE Selected objective name: R67423 Selected RHS name: B Selected bound name: BOUND Parallel mode: deterministic, using up to 2 threads for concurrent optimization. Tried aggregator 1 time. LP Presolve eliminated 190 rows and 101 columns. Reduced LP has 67232 rows, 55287 columns, and 426827 nonzeros. </pre>

    I still suspect it is scaling. Scaling is disabled when presolve is turned off, right? I'm trying to write my own script to rescale the problem.
    > Eumpfenbach wrote:
    > Correct. It is the same problem. I just posted logs from when I solve the full MIP as a standard cplex problem, not one of the relaxations. If it makes a difference, here is a log from the initial LP relaxation of the same problem:
    >
    >
    
    > Selected objective sense:  MINIMIZE > Selected objective  name:  R67423 > Selected RHS        name:  B > Selected bound      name:  BOUND > Parallel mode: deterministic, using up to 2 threads 
    
    for concurrent optimization. > Tried aggregator 1 time. > LP Presolve eliminated 190 rows and 101 columns. > Reduced LP has 67232 rows, 55287 columns, and 426827 nonzeros. >
    

    >
    > I still suspect it is scaling. Scaling is disabled when presolve is turned off, right? I'm trying to write my own script to rescale the problem.
    Scaling is not disabled when presolve is turned off. If you want to turn off
    scaling, set CPLEX's scale parameter to -1.

    I am speculating now, but when you say that you suspect your model is ill conditioned, and also show that presolve modified a large number of coefficients,
    and find that turning presolve off dramatically degrades performance despite the
    fact that the output you posted indicates presolve removed relatively few constraints and variables, I wonder if you have some constraints with a big M
    formulation, e.g. x continuous, z binary, and

    x - Mz <= 0

    Here, M is a really large number (e.g. 1e+8 or higher). If other constraints
    imply an upper bound an x much smaller than M, presolve will probably detect
    this. It will then modify the large M value to the much smaller upper bound value. In that case, the range of coefficient values for the presolved model may be much smaller than the range for the unpresolved model. Thus, the
    original model may be ill conditioned, while the presolved model might not be. That in turn could explain the big difference in performance. To assess this,
    compare the log files of the two runs. Also, try using CPLEX's MIP kappa feature on both the original and presolved model. This provides info on the
    condition numbers of the optimal node LP bases, and will help you determine if
    the conditioning of the presolved model is significantly better than the original
    model. You can also read in the original model into interactive CPLEX, then write out the presolved model:

    CPLEX> read mymodel.sav
    CPLEX> write mymodel.pre

    Then read in the .pre file and do 'display problem stats' to examine the numerical data.
    If you have additional questions on this, consider posting the log files of the CPLEX runs for the original and presolved model to this thread.
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-16T04:06:38Z  
    • EdKlotz
    • ‏2012-04-13T15:54:53Z
    > Eumpfenbach wrote:
    > Correct. It is the same problem. I just posted logs from when I solve the full MIP as a standard cplex problem, not one of the relaxations. If it makes a difference, here is a log from the initial LP relaxation of the same problem:
    >
    > <pre class="jive-pre"> > Selected objective sense: MINIMIZE > Selected objective name: R67423 > Selected RHS name: B > Selected bound name: BOUND > Parallel mode: deterministic, using up to 2 threads for concurrent optimization. > Tried aggregator 1 time. > LP Presolve eliminated 190 rows and 101 columns. > Reduced LP has 67232 rows, 55287 columns, and 426827 nonzeros. > </pre>
    >
    > I still suspect it is scaling. Scaling is disabled when presolve is turned off, right? I'm trying to write my own script to rescale the problem.
    Scaling is not disabled when presolve is turned off. If you want to turn off
    scaling, set CPLEX's scale parameter to -1.

    I am speculating now, but when you say that you suspect your model is ill conditioned, and also show that presolve modified a large number of coefficients,
    and find that turning presolve off dramatically degrades performance despite the
    fact that the output you posted indicates presolve removed relatively few constraints and variables, I wonder if you have some constraints with a big M
    formulation, e.g. x continuous, z binary, and

    x - Mz <= 0

    Here, M is a really large number (e.g. 1e+8 or higher). If other constraints
    imply an upper bound an x much smaller than M, presolve will probably detect
    this. It will then modify the large M value to the much smaller upper bound value. In that case, the range of coefficient values for the presolved model may be much smaller than the range for the unpresolved model. Thus, the
    original model may be ill conditioned, while the presolved model might not be. That in turn could explain the big difference in performance. To assess this,
    compare the log files of the two runs. Also, try using CPLEX's MIP kappa feature on both the original and presolved model. This provides info on the
    condition numbers of the optimal node LP bases, and will help you determine if
    the conditioning of the presolved model is significantly better than the original
    model. You can also read in the original model into interactive CPLEX, then write out the presolved model:

    CPLEX> read mymodel.sav
    CPLEX> write mymodel.pre

    Then read in the .pre file and do 'display problem stats' to examine the numerical data.
    If you have additional questions on this, consider posting the log files of the CPLEX runs for the original and presolved model to this thread.
    First of all, thank you very much for the responses.

    I don't really have big-m constraints of the typical form, but I definitely have similar problems. I am trying to solve a linear-fractional program which I transform into an MIP. I have coefficients on the order of e9 with variables and coefficients that are less than one. Without presolving, even the LP relaxation does not even solve (or at least, it takes so long I cancel before it does). I see the "Parallel mode: deterministic" message and then nothing. It just stops there for hours. With presolving, it solves in a couple minutes.

    I appreciate the information about how to test the conditioning of my problem, but I think it is pretty clear that whatever Cplex is doing to fix my numerical problems, I need it. If I can utilize presolve, I don't really need to get to the VERY bottom of the problem. If I couldn't utilize presolve, then I would need to dig. I just need to figure out how to presolve it with cplex, write to a file, and then load that file into Matlab. I am trying to use the Matlab API and have my problem stored in MPS format.

    Now, when I tried to write out the presolved model, this is what I encountered:

    
    CPLEX> read mnl_v2.mps Selected objective sense:  MINIMIZE Selected objective  name:  R116407 Selected RHS        name:  B Selected bound      name:  BOUND Problem 
    'mnl_v2.mps' read. Read time =    0.37 sec. CPLEX> write mymodel.pre Primal unbounded due to dual bounds, variable 
    'C0001'. CPLEX Error  1101: Presolve determines problem is infeasible or unbounded. No file written. CPLEX>
    


    This is the exact same MPS file that I load into Matlab. There, cplex presolves and then solves the model. Here it declares it infeasible. I will leave it to the experts to try and interpret what is going on.

    I have attached my mps file in case anyone wants to test anything with it.

    Thanks...
  • T_O
    T_O
    445 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-16T06:15:42Z  
    First of all, thank you very much for the responses.

    I don't really have big-m constraints of the typical form, but I definitely have similar problems. I am trying to solve a linear-fractional program which I transform into an MIP. I have coefficients on the order of e9 with variables and coefficients that are less than one. Without presolving, even the LP relaxation does not even solve (or at least, it takes so long I cancel before it does). I see the "Parallel mode: deterministic" message and then nothing. It just stops there for hours. With presolving, it solves in a couple minutes.

    I appreciate the information about how to test the conditioning of my problem, but I think it is pretty clear that whatever Cplex is doing to fix my numerical problems, I need it. If I can utilize presolve, I don't really need to get to the VERY bottom of the problem. If I couldn't utilize presolve, then I would need to dig. I just need to figure out how to presolve it with cplex, write to a file, and then load that file into Matlab. I am trying to use the Matlab API and have my problem stored in MPS format.

    Now, when I tried to write out the presolved model, this is what I encountered:

    <pre class="jive-pre"> CPLEX> read mnl_v2.mps Selected objective sense: MINIMIZE Selected objective name: R116407 Selected RHS name: B Selected bound name: BOUND Problem 'mnl_v2.mps' read. Read time = 0.37 sec. CPLEX> write mymodel.pre Primal unbounded due to dual bounds, variable 'C0001'. CPLEX Error 1101: Presolve determines problem is infeasible or unbounded. No file written. CPLEX> </pre>

    This is the exact same MPS file that I load into Matlab. There, cplex presolves and then solves the model. Here it declares it infeasible. I will leave it to the experts to try and interpret what is going on.

    I have attached my mps file in case anyone wants to test anything with it.

    Thanks...
    > I have attached my mps file in case anyone wants to test anything with it.

    Where?
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-16T13:19:38Z  
    • T_O
    • ‏2012-04-16T06:15:42Z
    > I have attached my mps file in case anyone wants to test anything with it.

    Where?
    Its a 21 MB file. Something must have gone wrong with the attachment. Trying again...
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-16T13:22:40Z  
    Its a 21 MB file. Something must have gone wrong with the attachment. Trying again...
    Looks like it failed again. Email Eumpfenbach at wayne dot edu and I will send the mps file (if anyone wants to experiment with it).
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-16T13:44:04Z  
    Looks like it failed again. Email Eumpfenbach at wayne dot edu and I will send the mps file (if anyone wants to experiment with it).
    This should work:

    http://www.mediafire.com/?zff86wp19ryfekl
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-16T20:13:48Z  
    This should work:

    http://www.mediafire.com/?zff86wp19ryfekl
    The LP relaxation of your problem is indeed unbounded, and this means that the MIP is infeasible or unbounded.

    To analyze the reason, I did the following in the interactive:
    1. Read in the model, optimize it - unbounded error.
    2. Change problem type to LP, optimize again - still unbounded.
    3. Write out the dual formulation ("write mnl.dua"), read it back in, optimize - infeasible.
    4. Run the conflict refiner ("conflict") to find a minimal infeasible subset - result is a single constraint and one bound.
    5. Display the conflict.
    Minimal conflict:    1 linear constraint(s)
                         1 lower bound(s)
                         0 upper bound(s)
    Conflict computation time =    0.02 sec.  Iterations = 1
     
    CPLEX> disp conf all
    Minimize
     obj:
    Subject To
     C0001: - 300000 R37661 >= 100000000
    Bounds
     The variable is >= 0.
    


    This conflict shows the infeasibility of the dualized model, i.e., the existence of an unbounded ray in the primal formulation.
    Indeed, if one looks at the original model, variable C0001 has a negative objective coefficient (in a minimization problem), an infinite upper bound, and increasing it will not make any constraint infeasible (the only coefficient is negative and appears in a smaller-or-equal constraint). Consequently, the unit vector with a 1 at the position of C0001 is an unbounded ray.
    Tobias
    Updated on 2014-03-24T23:05:38Z at 2014-03-24T23:05:38Z by iron-man
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-16T20:40:22Z  
    The LP relaxation of your problem is indeed unbounded, and this means that the MIP is infeasible or unbounded.

    To analyze the reason, I did the following in the interactive:
    1. Read in the model, optimize it - unbounded error.
    2. Change problem type to LP, optimize again - still unbounded.
    3. Write out the dual formulation ("write mnl.dua"), read it back in, optimize - infeasible.
    4. Run the conflict refiner ("conflict") to find a minimal infeasible subset - result is a single constraint and one bound.
    5. Display the conflict.
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">Minimal conflict: 1 linear constraint(s) 1 lower bound(s) 0 upper bound(s) Conflict computation time = 0.02 sec. Iterations = 1 CPLEX> disp conf all Minimize obj: Subject To C0001: - 300000 R37661 >= 100000000 Bounds The variable is >= 0. </pre>

    This conflict shows the infeasibility of the dualized model, i.e., the existence of an unbounded ray in the primal formulation.
    Indeed, if one looks at the original model, variable C0001 has a negative objective coefficient (in a minimization problem), an infinite upper bound, and increasing it will not make any constraint infeasible (the only coefficient is negative and appears in a smaller-or-equal constraint). Consequently, the unit vector with a 1 at the position of C0001 is an unbounded ray.
    Tobias
    Yikes. I made a very careless error in my posting. My model is a maximization problem. When I read the mps file into Matlab, I then multiply the objective by -1.

    When I correct this error, I am able to save the presolved model, load it back in, and write an mps file (for export to Matlab). I will test and see if this eliminates all of my numerical difficulties.

    Thanks.
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-16T21:16:28Z  
    Yikes. I made a very careless error in my posting. My model is a maximization problem. When I read the mps file into Matlab, I then multiply the objective by -1.

    When I correct this error, I am able to save the presolved model, load it back in, and write an mps file (for export to Matlab). I will test and see if this eliminates all of my numerical difficulties.

    Thanks.
    I am still seeing inconsistent numerical behavior. I use interactive cplex to write the presolved model, load it back into interactive cplex, then write an mps file.

    I solve this presolved mps file (both with Cplex/Matlab's presolve on and off, this doesn't make a difference), and it gives me a different objective function value than if I had just taken my original MPS file, loaded into Matlab, presolved, and then solved. The answers differ by a magnitude of 100.

    Unfortunately I do not know the optimal solution to my problem so I cannot determine which way is correct. Any thoughts on this behavior?
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-17T07:37:45Z  
    I am still seeing inconsistent numerical behavior. I use interactive cplex to write the presolved model, load it back into interactive cplex, then write an mps file.

    I solve this presolved mps file (both with Cplex/Matlab's presolve on and off, this doesn't make a difference), and it gives me a different objective function value than if I had just taken my original MPS file, loaded into Matlab, presolved, and then solved. The answers differ by a magnitude of 100.

    Unfortunately I do not know the optimal solution to my problem so I cannot determine which way is correct. Any thoughts on this behavior?
    What do you mean by "different objective function value"? You are not able to solve this model to optimality, right? So, are you talking about the incumbent objective value or the global dual bound? And at which point do you measure them? After some time limit is exceeded?

    Tobias
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-17T13:09:12Z  
    What do you mean by "different objective function value"? You are not able to solve this model to optimality, right? So, are you talking about the incumbent objective value or the global dual bound? And at which point do you measure them? After some time limit is exceeded?

    Tobias
    Note: this uses slightly different problem data than the file I posted on Mediafire. It is the same model with the same problems though.

    1) Original MPS file in Matlab, no presolve:

    
    Selected objective sense:  MINIMIZE Selected objective  name:  R116407 Selected RHS        name:  B Selected bound      name:  BOUND Parallel mode: deterministic, using up to 2 threads 
    
    for concurrent optimization.
    


    Then it just freezes. No iterations shown. I don't know if it will eventually solve but not anytime soon.

    2) Original MPS file in Matlab, with presolve:

    
    Selected objective sense:  MINIMIZE Selected objective  name:  R116407 Selected RHS        name:  B Selected bound      name:  BOUND Parallel mode: deterministic, using up to 2 threads 
    
    for concurrent optimization. Tried aggregator 1 time. LP Presolve eliminated 111 rows and 101 columns. Reduced LP has 116295 rows, 55318 columns, and 525009 nonzeros. Using devex.   Iteration log . . . Iteration:     1    Objective     =    2787758391.255035   ----Removing a bunch of intermediate iterations 
    
    for readability ----------   Markowitz threshold set to 0.5 Switched to devex. Iteration:    77    Objective     =    2787758391.254920   obj =   2.7878e+009
    


    3) Original MPS presolved in interactive Cplex, saved as MPS, loaded into Matlab, Matlab/cplex Presolve off

    
    >> miptest Selected objective sense:  MINIMIZE Selected objective  name:  obj Selected RHS        name:  rhs Selected bound      name:  bnd Parallel mode: deterministic, using up to 2 threads 
    
    for concurrent optimization.   obj =   2.5456e+011
    


    4) Original MPS presolved in interactive Cplex, saved as MPS, loaded into Matlab, Matlab/cplex Presolve on

    
    Selected objective sense:  MINIMIZE Selected objective  name:  obj Selected RHS        name:  rhs Selected bound      name:  bnd Parallel mode: deterministic, using up to 2 threads 
    
    for concurrent optimization. Tried aggregator 1 time. LP Presolve eliminated 78647 rows and 88 columns. Reduced LP has 37648 rows, 55230 columns, and 367440 nonzeros.   obj =   2.5456e+011
    
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-17T13:55:10Z  
    Note: this uses slightly different problem data than the file I posted on Mediafire. It is the same model with the same problems though.

    1) Original MPS file in Matlab, no presolve:

    <pre class="jive-pre"> Selected objective sense: MINIMIZE Selected objective name: R116407 Selected RHS name: B Selected bound name: BOUND Parallel mode: deterministic, using up to 2 threads for concurrent optimization. </pre>

    Then it just freezes. No iterations shown. I don't know if it will eventually solve but not anytime soon.

    2) Original MPS file in Matlab, with presolve:

    <pre class="jive-pre"> Selected objective sense: MINIMIZE Selected objective name: R116407 Selected RHS name: B Selected bound name: BOUND Parallel mode: deterministic, using up to 2 threads for concurrent optimization. Tried aggregator 1 time. LP Presolve eliminated 111 rows and 101 columns. Reduced LP has 116295 rows, 55318 columns, and 525009 nonzeros. Using devex. Iteration log . . . Iteration: 1 Objective = 2787758391.255035 ----Removing a bunch of intermediate iterations for readability ---------- Markowitz threshold set to 0.5 Switched to devex. Iteration: 77 Objective = 2787758391.254920 obj = 2.7878e+009 </pre>

    3) Original MPS presolved in interactive Cplex, saved as MPS, loaded into Matlab, Matlab/cplex Presolve off

    <pre class="jive-pre"> >> miptest Selected objective sense: MINIMIZE Selected objective name: obj Selected RHS name: rhs Selected bound name: bnd Parallel mode: deterministic, using up to 2 threads for concurrent optimization. obj = 2.5456e+011 </pre>

    4) Original MPS presolved in interactive Cplex, saved as MPS, loaded into Matlab, Matlab/cplex Presolve on

    <pre class="jive-pre"> Selected objective sense: MINIMIZE Selected objective name: obj Selected RHS name: rhs Selected bound name: bnd Parallel mode: deterministic, using up to 2 threads for concurrent optimization. Tried aggregator 1 time. LP Presolve eliminated 78647 rows and 88 columns. Reduced LP has 37648 rows, 55230 columns, and 367440 nonzeros. obj = 2.5456e+011 </pre>
    And anticipating a possible question, I did change my problem type to LP before I presolved in interactive cplex. Everything I am showing results for is the initial LP relaxation of the MIP.
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-18T13:30:59Z  
    And anticipating a possible question, I did change my problem type to LP before I presolved in interactive cplex. Everything I am showing results for is the initial LP relaxation of the MIP.
    I am sure someone will get to my other question but in the meantime, is it possible to set "aggressive scaling" in cplex for Matlab? I cannot find the parameter in the guide or by creating an object and looking through cplex.Param.
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-18T23:05:59Z  
    I am sure someone will get to my other question but in the meantime, is it possible to set "aggressive scaling" in cplex for Matlab? I cannot find the parameter in the guide or by creating an object and looking through cplex.Param.
    Another thought. I did some googling and found this:

    http://groups.google.com/group/ampl/browse_thread/thread/7e24843742d14aa9/66d7db390a5ece1c?lnk=gst&q=mps#66d7db390a5ece1c

    Per Paul's statement, what are the chances that the conversion to .mps file is causing problems? This is maybe why using interactive cplex to presolve is resulting in answers that are drastically superoptimal (ie because I am writing an mps, reading it, writing another mps, and then solving).

    I only use an MPS file because I first learned modeling with AMPL. I am assuming I could convert it into ILOG language relatively easy. I am just looking for confirmation that this would have value before I put in the effort. Please let me know what the experts think...
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-27T07:27:14Z  
    Another thought. I did some googling and found this:

    http://groups.google.com/group/ampl/browse_thread/thread/7e24843742d14aa9/66d7db390a5ece1c?lnk=gst&q=mps#66d7db390a5ece1c

    Per Paul's statement, what are the chances that the conversion to .mps file is causing problems? This is maybe why using interactive cplex to presolve is resulting in answers that are drastically superoptimal (ie because I am writing an mps, reading it, writing another mps, and then solving).

    I only use an MPS file because I first learned modeling with AMPL. I am assuming I could convert it into ILOG language relatively easy. I am just looking for confirmation that this would have value before I put in the effort. Please let me know what the experts think...
    Is it possible that you use the .sav file format instead .mps? The .sav format is a binary format and preserves every single bit of model data.

    Tobias
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-04-28T22:17:36Z  
    Is it possible that you use the .sav file format instead .mps? The .sav format is a binary format and preserves every single bit of model data.

    Tobias
    I transferred my code to ILOG and am using a .lp format. I no longer see poor results (meaning that when I presolve using interactive cplex and import into matlab, the problem isn't "corrupted").

    Thanks. I still have some trouble with what I am trying to do but will use an appropriate thread for the other questions.
  • EdKlotz
    EdKlotz
    244 Posts

    Re: Ill Conditioned Problem

    ‏2012-05-01T00:20:57Z  
    I transferred my code to ILOG and am using a .lp format. I no longer see poor results (meaning that when I presolve using interactive cplex and import into matlab, the problem isn't "corrupted").

    Thanks. I still have some trouble with what I am trying to do but will use an appropriate thread for the other questions.
    I don't have any answers for the most recent questions in the thread. But, regarding the general question about the ill conditioning in the problem,
    I had a quick look at the model and have a few comments.

    1) Setting CPLEX's scaling parameter significantly improved the basis condition
    numbers during the MIP solve. This can be seen by using the recently added
    MIP kappa feature that accumulates statistics on the basis condition numbers during
    a MIP solve ('set mip strategy kappastats 1' (or 2) when using interactive CPLEX).

    2) Regarding the higher level of ill conditioning when presolve is turned off,
    consider a constraint like the following in the model:

    
    R37660:  103.28 C0102 + 103.28 C0103 + 103.28 C0104 + 102.13 C0105 + 102.13 C0106 + 102.13 C0107 + 114.49 C0108 + 114.49 C0109 + 114.49 C0110 + 113.315 C0111 + 113.315 C0112 + 113.315 C0113   ...   + 128.9702 C36975 + 110.128 C36976 + 128.9702 C36977 + 55.064 C36978 + 64.4851 C36979 + 55.064 C36980 + 64.4851 C36981 + 55.064 C36982 + 64.4851 C36983 <= 1000000000000
    


    This large right hand side value, particularly when coupled with potentially
    high basis condition numbers, could introduce significant round off error
    into various calculations, leading to inconsistent results. CPLEX's
    presolve managed to delete this constraint, which could improve the numerics
    significantly. This does not surprise me; given the modest coefficients of
    the variables in this constraint, if CPLEX can derive any sort of modest finite
    upper bounds on this variable, this constraint will be redundant. Are you sure
    you really need this constraint in the model? If you could remove it yourself,
    that might help.

    3) I also notice a wide range of objective coefficients in the model. Also,
    based on some MIP runs, it really looks like the coefficients of the largest
    order of magnitude dominate until their variables can all be set to 0. In such
    cases, we often recommend using a goal programming approach where you first
    optimize over the really large objective coefficients, then constrain them based
    on that result. This will enable you to avoid using such large coefficients,
    which can create numerical problems that you could otherwise avoid.
    More information on this can be found at
    http://www-01.ibm.com/support/docview.wss?uid=swg21399935
    Hopefully one or more of these will help with your original question.
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: Ill Conditioned Problem

    ‏2012-05-01T12:35:14Z  
    • EdKlotz
    • ‏2012-05-01T00:20:57Z
    I don't have any answers for the most recent questions in the thread. But, regarding the general question about the ill conditioning in the problem,
    I had a quick look at the model and have a few comments.

    1) Setting CPLEX's scaling parameter significantly improved the basis condition
    numbers during the MIP solve. This can be seen by using the recently added
    MIP kappa feature that accumulates statistics on the basis condition numbers during
    a MIP solve ('set mip strategy kappastats 1' (or 2) when using interactive CPLEX).

    2) Regarding the higher level of ill conditioning when presolve is turned off,
    consider a constraint like the following in the model:

    <pre class="jive-pre"> R37660: 103.28 C0102 + 103.28 C0103 + 103.28 C0104 + 102.13 C0105 + 102.13 C0106 + 102.13 C0107 + 114.49 C0108 + 114.49 C0109 + 114.49 C0110 + 113.315 C0111 + 113.315 C0112 + 113.315 C0113 ... + 128.9702 C36975 + 110.128 C36976 + 128.9702 C36977 + 55.064 C36978 + 64.4851 C36979 + 55.064 C36980 + 64.4851 C36981 + 55.064 C36982 + 64.4851 C36983 <= 1000000000000 </pre>

    This large right hand side value, particularly when coupled with potentially
    high basis condition numbers, could introduce significant round off error
    into various calculations, leading to inconsistent results. CPLEX's
    presolve managed to delete this constraint, which could improve the numerics
    significantly. This does not surprise me; given the modest coefficients of
    the variables in this constraint, if CPLEX can derive any sort of modest finite
    upper bounds on this variable, this constraint will be redundant. Are you sure
    you really need this constraint in the model? If you could remove it yourself,
    that might help.

    3) I also notice a wide range of objective coefficients in the model. Also,
    based on some MIP runs, it really looks like the coefficients of the largest
    order of magnitude dominate until their variables can all be set to 0. In such
    cases, we often recommend using a goal programming approach where you first
    optimize over the really large objective coefficients, then constrain them based
    on that result. This will enable you to avoid using such large coefficients,
    which can create numerical problems that you could otherwise avoid.
    More information on this can be found at
    http://www-01.ibm.com/support/docview.wss?uid=swg21399935
    Hopefully one or more of these will help with your original question.
    First of all, thank you very much for looking at my problem in so much detail!

    1) I want to use Cplex/Matlab. I still haven't found the scaling parameter control in this API.

    2) this constraint is sort of necessary. I purposely set the right hand side so large that the constraint will never be binding. Later, on sensitivity runs, I will reduce it and observe the effect on the objective. I did reduce it by several orders of magnitude without it becoming binding, improving the conditioning.

    3) I have not considered watching which variables cplex attacks first and trying your approach of creating constraints with them. Given that there are 2 problems here (the first was about numerical accuracy with mps files and the other is how to solve efficiently), I can't be sure that the solution you saw is a proper one. I do have a large difference in the magnitude of some of my coefficients (fixed costs for building a manufacturing plant vs. unit costs to produce products). I will have to think about this and experiment.

    Thanks again!