Originally posted by: BhavnaJha

Originally posted by: EdKlotz

      I don't know the dimensions of the largest LP any CPLEX user has solved, but I can provide a lower bound based on the models I have seen myself and those that reside in our internal LP test set.   Last year I solved one with 14 million constraints and 440 million  variables.   It took about 40 hours using the barrier method with 12 threads.   I also see a huge model in our test set with over 350 million constraints and 27 million variables.    But, it has "only" 640 million nonzeros, and CPLEX's presolve reduces the model dimensions down  to   5.8 million constraints, 7.6 million variables and 31 million nonzeros  , so the model optimizes pretty easily.   I'm rerunning it now and will post the run time when it's done, but it looks like it will solve within a couple of hours. 

       For a good set of publicly available large, challenging LPs go to http://miplib.zib.de/contrib/miplib2003-contrib/IPWS2008/.  These are relaxations from MIPs, but the LPs themselves are challenging.

      The difficulty of an LP does not really depend on just the size.   It depends on multiple factors, including

• How much does CPLEX's presolve reduce the model?
• Are the problem dimensions large in terms of constraints, variables or both?   If only one of those dimensions is huge, CPLEX will typically formulate and solve the dual model (but map the solution info back to the user's original, primal model).    Since the number of constraints influences run time more profoundly than the number of variables, the smaller of the number of constraints and variables is a more important metric than the overall problem size.
• Matrix nonzero count also plays an important role.   The zib05 model, available at the above URL, has relatively modest dimensions of about 10 thousand (yes thousand, not millioni)  constraints and 9 million variables.    But, it has 342 million nonzeros, making it quite dense compared to most problems.   I'd be more confident of CPLEX's chances to finish in a reasonable amount of time on a model with one hundred million constraints, one hundred million variables that is almost all network with some fairly easy side constraints (so that the total nonzero count is at most 300 million variables) than I would a much smaller model that had a few billion nonzeros.

In general you should need about 1 GB per million constraints.   If you have enough memory, solving models with 50 million constraints and 50 million variables is definitely possible.    Now if the LP has some characteristics that make it difficult to solve, maybe it won't solve fast enough for you.    But, the pure size of the model won't be the issue.   In general, the primary limit at this point is not problem size, but available memory and time.    Note that CPLEX's sparse arrays can handle more than 2.1 billion nonzeros, a key threshold because you cannot index more than that with 32 bit indices.

Perhaps an equally interesting question would be what is the smallest model CPLEX cannot solve within a specified number of hours (or days).   I'm not sure about the answer to that, because I don't think it comes from our internal test set.

Originally posted by: EdKlotz

Following up on my previous post, that 350 million constraint LP model I mentioned solved in just over an hour running barrier with 8 threads on a Linux box with Xeon E5-4650 2.7 GHz  chips and 384 GB of memory.

Originally posted by: BhavnaJha

I am trying to solve an MIP problem with 9 million variables ( only 5000 are binary ) and 35000 constraints on my system with the specifications : 

 Intel Core i3 1.9 GHz & 4GB RAM but it is showing an error MIP starts not constructed  because of Out of Memory? 

Even on a computer with 8 GB RAM it showed the same message. 

How do I estimate the memory requirements of my MIP problem ? And what do you think should the memory requirements be? 

Is a problem of such size solvable on the this system specifications? 

Originally posted by: EdKlotz

Unfortunately it is more difficult to predict the memory usage of a MIP model than an LP (or other type of continuous) model.   Specifically, the size of the branch and bound tree could be small, or it could be huge.   In addition, the size of some of CPLEX's internal MIP data structures (clique table, implication graph, cut table) can also very dramatically.

That being said, it may be possible to get some idea of how much memory CPLEX needs by looking at the node log of the 4 and 8 GB runs.   Specifically,

1)   How big is the presolved model?   The node log includes dimensions for the presolved model before the optimization starts.

2)   At what point does CPLEX run out of memory?   Is it still at the root node, or has it been branching for a while?   If the latter, what is the size of the branch and bound tree right before you get the out of memory messages.   The node log contains that info as well.

3)  How dense is the model?  You mentioned the number of constraints and variables, but the actual number of nonzeros in the constraint matrix can play a role as well.

While the number of constraints is more important than the number of variables, my initial reaction is that 4 GB probably would not be enough memory to solve a MIP model of the size you describe.   8 GB might be enough, but I would not be surprised if more was needed.   If you can provide some of the info I mention above, that may make it easier to assess how much memory is really needed here.

Ed

Originally posted by: BhavnaJha

This is the log file when I run the problem : 

<<< setup

<<< generate

Presolve has eliminated 9130 rows and 1711714 columns...
Tried aggregator 2 times.
MIP Presolve eliminated 45815 rows and 3130026 columns.
MIP Presolve modified 1224 coefficients.
Aggregator did 10277 substitutions.
Reduced MIP has 22630 rows, 5911055 columns, and 16120528 nonzeros.
Reduced MIP has 3420 binaries, 0 generals, 0 SOSs, and 2411 indicators.
Presolve time = 324.50 sec. (114555.08 ticks)
Probing time = 1613.31 sec. (6896.83 ticks)
Cover probing fixed 0 vars, tightened 1007 bounds.
Tried aggregator 2 times.
MIP Presolve eliminated 24 rows and 22566 columns.
MIP Presolve modified 2124 coefficients.
Aggregator did 1385 substitutions.
Reduced MIP has 21221 rows, 5887104 columns, and 16057938 nonzeros.
Reduced MIP has 2035 binaries, 0 generals, 0 SOSs, and 2411 indicators.
Presolve time = 181.35 sec. (8398.12 ticks)
Probing time = 206.44 sec. (2616.92 ticks)
Clique table members: 19.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 2229.43 sec. (679866.12 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0  2.14981e+011    84                2.14981e+011   132025         

Root node processing (before b&c):
  Real time             = 7909.31 sec. (824871.05 ticks)
Parallel b&c, 4 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) = 7909.31 sec. (824871.05 ticks)
Warning: MIP starts not constructed because of out-of-memory status.
### ENGINE exception: CPLEX Error  1001: Out of memory.

<<< no solution

Originally posted by: EdKlotz

Based on the output, you appear to be generating the model from OPL, so the OPL memory usage comes into play as well.   Now, those 9 million variables in the model play a more prominent role in the memory usage.    I think you need to assess how much memory OPL was using before the optimization began.   You could also export the SAV file from OPL and run it in interactive CPLEX to see how much memory CPLEX uses.   You could then use performance monitor or top to take a closer look at memory usage as the optimization progresses.    Finally, you are running on 4 threads, which will speed up performance, but also consumes more memory than one thread.

Given this output you posted, I'm not surprised that you ran out of memory with 4 and 8 GB.   You also should check your OPL modeling statements to make sure that they aren't using unnecessary extra amounts of memory (e.g. you create some extra, temporary expressions, or express your constraint matrix without taking advantage's of OPL constructs for expressing sparse constraints).   Note that the OPL IDE has a profiler tab that allows you to examine memory usage for the various aspects of the model generation; that may help you here.

Summarizing, find out how much memory goes towards model generation, and how much goes towards optimization.   That should give you some idea regarding how to proceed with this.   You may find a way to reduce memory usage and get this to run under 4 or 8 GB, or you may find that you need more memory.   In the latter case, by examining OPL's model generation memory usage and interactive CPLEX's optimization memory usage, you can probably get a better idea of just how much memory you need.

Originally posted by: suji248

Hello,

Is it possible to check the constraints that have been removed after presolve ?  Lets say for a problem I have added large number of constraints (like  some cuts)   but it may be removed  by CPLEX  after presolve.   Is there a way to export the LP/MPS files before and after Presolve ?