Originally posted by: sylviashen4

To whom it may concern,

         I generated some instances to test my algorithm. However, I found cplex had a hard time even to solve the LP relaxation problem. For the attached instance (.sav file of the LP relaxation), cplex does not solve the LP within half an hour using the default settings. Would you please help me to identify some reasons for this behavior or give me some suggestions on how to solve it?

Thanks very much,

Sylvia

Out of curiosity, I ran the automatic tuner on your problem (using CPLEX 12.6.3).  It recommended using the following parameter:

simplex dgradient 5

I've attached the corresponding parameter file for your convenience (param.prm).

This doesn't mean that this is absolutely the best parameter setting (the tuning tool doesn't test every possible combination), but it's an improvement.  On my computer it solved in ~8.5 minutes rather than ~12.5 minutes.

I can't give you insight into the behavior (or even it's unexpected), but in case this is useful for someone else who can, here are the problem stats:

Problem name         : T21_D1200_M60_F16_R75_S16_agg_pass0.sav
Objective sense      : Minimize
Variables            :  119004  [Nneg: 15,  Fix: 6,  Box: 118983]
Objective nonzeros   :       4
Linear constraints   :  452727  [Less: 347520,  Greater: 100800,  Equal: 3147,
                                 Range: 1260]
  Nonzeros           : 1374714
  RHS nonzeros       :  310620

Variables            : Min LB: 0.000000         Max UB: 25486.65       
Objective nonzeros   : Min   : 0.001000000      Max   : 1.000000       
Linear constraints   :
  Nonzeros           : Min   : 1.000000         Max   : 88272.00       
  RHS nonzeros       : Min   : 1.000000         Max   : 2000.000       
  Range values       : Min   : 302400.0         Max   : 907200.0

I'll attached the log using the parameters above.

I'm not sure, but I think your model might be a bit unstable numerically. I ran the barrier method on it, and the primal and dual bounds converged to 34,079.386 in about 97 seconds (this is on my home PC), but then CPLEX struggled with the crossover step. I then tried dual simplex, which within a minute or so had an objective value in excess of 34,600. I turned on the numerical emphasis parameter and repeated both trials, but the same thing happened with both methods. I also noticed that, on intermediate solutions (I wasn't patient enough to run to completion), the basis condition number for dual simplex was around 9e6 in one case and 8e7 in another. Those are not horrible, but they are a bit high. I gave primal simplex a shot, and it added perturbations and adjusted the Markowitz threshold early on, which I interpret as a sign of numerical problems. (Primal simplex was making very slow progress getting an initial feasible solution.)

There's an excellent tutorial by Dr. Ed Klotz of IBM on diagnosing and correcting numerical problems: Ed Klotz. Identification, Assessment, and Correction of Ill-Conditioning and Numerical Instability in Linear and Integer Programs. In INFORMS Tutorials in Operations Research. Published online: 27 Oct 2014; 54-108. http://dx.doi.org/10.1287/educ.2014.0130

I can make a couple of suggestions off the top of my head. One is to see if you can improve the scaling of your model (reduce the four orders of magnitude scale difference in your nonzero coefficients). This could be something as simple as changing units (from grams to kilograms, etc.). The other is to see if you have an common expressions that crop up more than once in constraints. If so, replacing them with new variables might help (by reducing density).

Considering Paul's comment, you may also find this technote useful.