CODEWITHSUNDEEP
linear-programmingcplexbarriercrossover
Sophia Niu
Sophia Niu

Reputation: 1

Use exported sav to run barrier+crossover got different result

I have a large pure LP model and written by c# API. In c# API, we build the model and solve it with the following settings,

2024-09-19 12:03:42.608 +08:00 [INF] Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
2024-09-19 12:03:42.609 +08:00 [INF] CPXPARAM_LPMethod                                4
2024-09-19 12:03:42.609 +08:00 [INF] CPXPARAM_QPMethod                                4
2024-09-19 12:03:42.610 +08:00 [INF] CPXPARAM_Threads                                 8
2024-09-19 12:03:42.611 +08:00 [INF] CPXPARAM_Emphasis_Numerical                      1
2024-09-19 12:03:42.611 +08:00 [INF] CPXPARAM_SolutionType                            2
2024-09-19 12:03:42.612 +08:00 [INF] CPXPARAM_MIP_Strategy_StartAlgorithm             4
2024-09-19 12:03:42.613 +08:00 [INF] CPXPARAM_Barrier_Algorithm                       2
2024-09-19 12:03:42.614 +08:00 [INF] CPXPARAM_TimeLimit                               7200
2024-09-19 12:03:48.629 +08:00 [INF] Tried aggregator 1 time.
2024-09-19 12:03:59.064 +08:00 [INF] Aggregator has done 589525 substitutions...
2024-09-19 12:03:59.126 +08:00 [INF] LP Presolve eliminated 461174 rows and 720652 columns.
2024-09-19 12:03:59.127 +08:00 [INF] Aggregator did 589525 substitutions.
2024-09-19 12:03:59.190 +08:00 [INF] Reduced LP has 312004 rows, 775019 columns, and 8848968 nonzeros.
2024-09-19 12:03:59.282 +08:00 [INF] Presolve time = 16.66 sec. (31666.13 ticks)
2024-09-19 12:03:59.381 +08:00 [INF] Parallel mode: using up to 8 threads for barrier.
2024-09-19 12:04:06.873 +08:00 [INF] Number of nonzeros in lower triangle of A*A' = 17570222
2024-09-19 12:04:09.009 +08:00 [INF] Elapsed ordering time = 5.42 sec. (10000.00 ticks)
2024-09-19 12:04:25.836 +08:00 [INF] Using Approximate Minimum Degree ordering
2024-09-19 12:04:25.897 +08:00 [INF] Total time for automatic ordering = 22.31 sec. (35031.42 ticks)
2024-09-19 12:04:28.860 +08:00 [INF] Summary statistics for Cholesky factor:
2024-09-19 12:04:28.861 +08:00 [INF]   Threads                   = 8
2024-09-19 12:04:28.862 +08:00 [INF]   Rows in Factor            = 312004
2024-09-19 12:04:28.864 +08:00 [INF]   Integer space required    = 6338673
2024-09-19 12:04:28.865 +08:00 [INF]   Total non-zeros in factor = 307508700
2024-09-19 12:04:28.866 +08:00 [INF]   Total FP ops to factor    = 2177480483248

So basically using barrier algo, set emphasis numerical difficulty, use 8 threads, and bar alg to 2, do not do crossover.

The model encountered numerical difficulties after 85 iterations. and there is no solution yet. So we try to run crossover step, and add the setting of Simplex limiter lowerObj and upperObj to try to stop the crossover after any feasible solution was found.

2024-09-19 12:21:13.775 +08:00 [INF]   85   4.6287893e+05   4.6287893e+05  1.34e+03  3.31e-04  4.95e-02  2.01e+06
2024-09-19 12:21:13.783 +08:00 [INF]   *    4.6287892e+05   4.6287892e+05  4.02e+01  4.17e-03  6.69e-02  2.39e+05
2024-09-19 12:21:14.592 +08:00 [INF] Barrier time = 1051.86 sec. (3201448.16 ticks)
2024-09-19 12:21:14.594 +08:00 [INF] 
2024-09-19 12:21:14.596 +08:00 [INF] Total time on 8 threads = 1051.86 sec. (3201448.16 ticks)
2024-09-19 12:21:14.631 +08:00 [INF] Model solving did not get a solution
2024-09-19 12:21:14.635 +08:00 [INF] Model solving encountered numerical difficulties, cplex status is NumBest. Time spent is 1052.034021 seconds. Ticks is 3202126.423664093. Objective value is 462878.9196489909. Try to run crossover. 
2024-09-19 12:21:14.637 +08:00 [INF] Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
2024-09-19 12:21:14.638 +08:00 [INF] CPXPARAM_LPMethod                                4
2024-09-19 12:21:14.639 +08:00 [INF] CPXPARAM_QPMethod                                4
2024-09-19 12:21:14.640 +08:00 [INF] CPXPARAM_Threads                                 8
2024-09-19 12:21:14.641 +08:00 [INF] CPXPARAM_Emphasis_Numerical                      1
2024-09-19 12:21:14.643 +08:00 [INF] CPXPARAM_MIP_Strategy_StartAlgorithm             4
2024-09-19 12:21:14.650 +08:00 [INF] CPXPARAM_Barrier_Algorithm                       2
2024-09-19 12:21:14.651 +08:00 [INF] CPXPARAM_Simplex_Limits_LowerObj                 1.7976931348623157e+308
2024-09-19 12:21:14.652 +08:00 [INF] CPXPARAM_Simplex_Limits_UpperObj                 -1.7976931348623157e+308
2024-09-19 12:21:14.654 +08:00 [INF] CPXPARAM_TimeLimit                               7200
2024-09-19 12:21:14.665 +08:00 [INF] Parallel mode: deterministic, using up to 8 threads for concurrent optimization:
2024-09-19 12:21:14.667 +08:00 [INF]  * Starting dual Simplex on 1 thread...
2024-09-19 12:21:14.668 +08:00 [INF]  * Starting primal Simplex on 1 thread...

Then after around 40 minutes run, the crossover stopped, seems without any solution because cplex.solve() returned false.

2024-09-19 13:00:38.856 +08:00 [INF]    Elapsed crossover time = 2307.52 sec. (995147.44 ticks, 1123 PMoves)
2024-09-19 13:00:45.781 +08:00 [INF]        86 PMoves:  Infeasibility  2.18046767e+08  Objective  4.62878927e+05
2024-09-19 13:00:46.185 +08:00 [INF]         0 PMoves:  Infeasibility  2.18046276e+08  Objective  4.62878927e+05
2024-09-19 13:00:46.186 +08:00 [INF]   Primal:  Pushed 302635, exchanged 216508.
2024-09-19 13:00:52.450 +08:00 [INF] Total crossover time = 2377.38 sec. (1052759.86 ticks)
2024-09-19 13:00:52.451 +08:00 [INF] 
2024-09-19 13:00:52.453 +08:00 [INF] Total time on 8 threads = 2377.58 sec. (1052834.68 ticks)
2024-09-19 13:00:52.467 +08:00 [INF] Model solving failed, status is Error( AbortObjLim ). Time spent is 3429.8670417 seconds. Ticks is 4254973.646332741

I exported the same model to a .sav file, and read via interactive cplex. set the same parameter(threads, emphasis numerical, baralg=2) and run command "baropt stop", the log looks exactly same,

  85   4.6287893e+05   4.6287893e+05  1.34e+03  3.31e-04  4.95e-02  2.01e+06
  *    4.6287892e+05   4.6287892e+05  4.02e+01  4.17e-03  6.69e-02  2.39e+05
Barrier time = 1015.72 sec. (3201448.16 ticks)
 
Total time on 8 threads = 1015.72 sec. (3201448.16 ticks)
 
Barrier - Non-optimal:  Objective =  4.6287891965e+05
Solution time = 1015.73 sec.  Iterations = 85
Deterministic time = 3201452.06 ticks  (3151.86 ticks/sec)

The crossover's log also seems the same(only minus difference on ticks.) But this time, seesm a solution is found. objective value is also available. Things seems ok.

   Elapsed crossover time = 1874.17 sec. (995147.44 ticks, 1123 PMoves)
       86 PMoves:  Infeasibility  2.18046767e+08  Objective  4.62878927e+05
        0 PMoves:  Infeasibility  2.18046276e+08  Objective  4.62878927e+05
  Primal:  Pushed 302635, exchanged 216508.
Total crossover time = 1969.00 sec. (1052759.51 ticks)
 
Total time on 8 threads = 1969.17 sec. (1052834.34 ticks)
 
Dual simplex - Objective limit exceeded:  Objective =  4.6287892725e+05
Solution time = 1969.19 sec.  Iterations = 2 (0)
Deterministic time = 1052834.34 ticks  (534.65 ticks/sec)

So my questions are:

  1. Why the two way got different result?

  2. Is anything I did wrong in c# API? like I use cplex.Solve()'s return value to judge if there is a solution, is this always right?

  3. When I set the Simplex limits lowerObj and upperObj, what I'm trying to do is actually stop optimization after crossover find a feasible solution. Do I have better way to do this? Since by doing it, no matter a solution is found, the status is always Error which looks strange.

  4. Another strange thing is based on my understanding, when I set the Simplex limits upperObj to a very small number for a maximization problem, the crossover should stop after a feasible solution is found, but when I do this in interactive cplex, it seems continue to run the 2nd stage, and after over 2hours, I stopped the run. Do you know why?

    Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
CPXPARAM_Threads                                 8
CPXPARAM_Emphasis_Numerical                      1
CPXPARAM_Barrier_Algorithm                       2
CPXPARAM_Simplex_Limits_UpperObj                 -1.7976931348623157e+308
Parallel mode: deterministic, using up to 8 threads for concurrent optimization:
* Starting dual Simplex on 1 thread...
* Starting primal Simplex on 1 thread...

Dual crossover.
  Dual:  Fixing 104640 variables.
   104639 DMoves:  Infeasibility  2.21684044e+00  Objective  4.62879783e+05
   102021 DMoves:  Infeasibility  2.08403164e+00  Objective  4.62879588e+05

    ...

    Elapsed crossover time = 1845.67 sec. (995147.44 ticks, 1123 PMoves)
       86 PMoves:  Infeasibility  2.18046767e+08  Objective  4.62878927e+05
        0 PMoves:  Infeasibility  2.18046276e+08  Objective  4.62878927e+05
  Primal:  Pushed 302635, exchanged 216508.
Elapsed time = 1906.88 sec. (1047492.44 ticks, 1 iterations)

Iteration log . . .
Iteration:     1   Dual objective     =        462878.927253
Perturbation started.
Iteration:   101   Dual objective     =        462878.927253
Elapsed time = 1923.17 sec. (1057531.88 ticks, 200 iterations)
Elapsed time = 1940.36 sec. (1068658.54 ticks, 462 iterations)
Iteration:   462   Dual objective     =        462878.919037
Iteration:   935   Dual objective     =        462878.831552

    ...

    Iteration: 78932   Dual objective     =        462878.341915
    Elapsed time = 8970.41 sec. (6754583.17 ticks, 79111 iterations)
    Elapsed time = 8984.44 sec. (6768514.30 ticks, 79247 iterations)
    Iteration: 79247   Dual objective     =        462878.340341
    Removing perturbation.
    Total crossover time = 9000.72 sec. (6792088.87 ticks)

     

    Total time on 8 threads = 9000.89 sec. (6792165.06 ticks)

     

    Dual simplex - User aborted:  Objective =  4.6287892725e+05
    Solution time = 9000.92 sec.  Iterations = 79340 (0)
    Deterministic time = 6792165.06 ticks  (754.61 ticks/sec)

  5. Any hint or suggestions for avoiding the numerical difficulties? I tried to remove baralg=2, then no numerical difficulty, any possible explanation?

Thanks a lot!

Upvotes: 0

Views: 44

Answers (0)

Related Questions