CPLEX 20.1.0.0: unrecoverable failure: singular basis

[John Marcelo]

Hi everyone!

 I am running some scenarios of a MIQP problem in AMPL, but in one of them I get the termination "unrecoverable failure: singular basis". As a comment I can say that before of that I solved the relaxed problem normally and get a feasible solution. Can someone known if I can solve this problem fixing something? (for more details I am sharing the progress report). Thanks in advance.

[AMPL Google Group]

Since you are setting mipstartalg=4, CPLEX is solving the relaxation of the your MIQP using the barrier algorithm, probably followed by a crossover phase to get a basic solution. Thus the singular basis would be expected to occur in the crossover phase. To get more information about what's happening, replace mipdisplay=2 by mipdisplay=4 bardisplay=1 lpdisplay=2 (leaving other options as before) and post the resulting output. (You can copy all the output and paste it into your reply.)

Also when you "solved the relaxed problem" what options did you choose?

--
Robert Fourer
am...@googlegroups.com

{#HS:1846249389-109565#}

[John Marcelo]

Dear Robert,

Thanks for your answer. Excuse me to reply late, this is because I changed some parameters of my model, but the problem "unrecoverable failure: singular basis" continue for some cases. I set mipdisplay=4, bardisplay=1 and lpdisplay=2, as you told me. The mainly parts of the resulting output are showed bellow (as the  output is very large for the window, I attached all the content in a txt file). Please, help me to understand the output and tell me if we can set something in order to solve the singular basis problem. Thanks

(For relaxed problem I didn´t set any options).

**********************************************************************************************

TRANSITION 4

Presolve eliminates 27511 constraints and 73367 variables.
Adjusted problem:
68076 variables:
    760 binary variables
    1192 integer variables
    35916 nonlinear variables
    30208 linear variables
74568 constraints, all linear; 386871 nonzeros
    50585 equality constraints
    23983 inequality constraints
1 nonlinear objective; 49274 nonzeros.

CPLEX 20.1.0.0: mipgap=5e-2

mipdisplay=4

bardisplay=1

lpdisplay=2

rinsheur=10

integrality=1e-3

branch=-1

Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68

Processing 1 MIP starts.

MIP start 'm1' defined no solution.

Retaining values of one MIP start for possible repair.

MIQP Presolve eliminated 1039 rows and 1379 columns.

MIQP Presolve modified 2449 coefficients.

Reduced MIQP has 70753 rows, 63921 columns, and 381216 nonzeros.

Reduced MIQP has 520 binaries, 808 generals, 0 SOSs, and 0 indicators.

Reduced MIQP objective Q matrix has 35916 nonzeros.

Probing fixed 0 vars, tightened 26179 bounds.

Probing changed sense of 47 constraints.

Probing time = 0.58 sec. (150.84 ticks)

MIQP Presolve eliminated 47 rows and 35 columns.

MIQP Presolve modified 58 coefficients.

Reduced MIQP has 70706 rows, 63886 columns, and 381099 nonzeros.

Reduced MIQP has 485 binaries, 808 generals, 0 SOSs, and 0 indicators.

Reduced MIQP objective Q matrix has 35916 nonzeros.

Classifier predicts products in MIQP should be linearized.

Probing fixed 0 vars, tightened 6521 bounds.

Probing time = 0.53 sec. (53.19 ticks)

Clique table members: 2178.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 12 threads.

Reduced presolve eliminated 0 rows and 12 columns.

Reduced QP has 70706 rows, 63874 columns, and 381087 nonzeros.

Reduced QP objective Q matrix has 35916 nonzeros.

Parallel mode: using up to 12 threads for barrier.


***NOTE: Found 361 dense columns.


Number of nonzeros in lower triangle of A*A' = 529574

Using Approximate Minimum Degree ordering

Total time for automatic ordering = 0.03 sec. (26.79 ticks)

Summary statistics for Cholesky factor:

  Threads                   = 12

  Rows in Factor            = 71067

  Integer space required    = 356300

  Total non-zeros in factor = 4230515

  Total FP ops to factor    = 2505515849

 Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf          

   0   2.7350361e+09  -2.7880487e+09  1.52e+06  5.00e+06  1.10e+08

   1   1.1025009e+09  -1.1601805e+09  9.66e+05  3.17e+06  6.98e+07

   2   7.5454117e+08  -8.2160252e+08  8.00e+05  2.63e+06  5.78e+07

   3   4.9856639e+08  -5.7405238e+08  6.52e+05  2.14e+06  4.71e+07

   4   3.2958353e+08  -4.1460325e+08  5.31e+05  1.74e+06  3.84e+07

   5   1.2627237e+08  -2.3045936e+08  3.29e+05  1.08e+06  2.37e+07

   6   4.6819636e+06  -1.0552899e+08  5.03e+04  1.65e+05  3.63e+06

   7   2.3014604e+06  -1.0707953e+08  2.43e+04  7.99e+04  1.76e+06

   8   1.5368599e+06  -7.9956809e+07  4.90e+03  1.61e+04  3.54e+05

   9   1.2477914e+06  -3.2162809e+07  7.86e+02  2.58e+03  5.68e+04

  10   8.2788179e+05  -1.4103676e+07  2.05e+02  6.75e+02  1.48e+04

  11   5.5051114e+05  -7.8715280e+06  1.03e+02  3.37e+02  7.42e+03

  12   2.2464663e+05  -1.6225344e+06  1.46e+01  4.79e+01  1.05e+03

  13   1.6168913e+05  -9.0668687e+05  7.19e+00  2.36e+01  5.19e+02

  14   9.5607899e+04  -3.4016048e+05  3.07e-08  1.73e-12  4.07e-03

  15   3.4988042e+04  -6.9149987e+04  1.46e-08  1.67e-12  1.98e-02

  16   2.2162901e+04  -4.4581136e+04  9.28e-09  1.78e-12  1.17e-02

  17   6.3495507e+03  -6.2101165e+03  4.60e-08  1.78e-12  4.05e-03

  18   5.9544931e+03  -5.1564434e+03  4.66e-08  2.32e-12  3.72e-03

  19   4.3233207e+03  -7.4175695e+02  4.02e-08  1.77e-12  1.74e-03

  20   4.2109379e+03  -4.2579141e+02  4.00e-08  2.44e-12  1.60e-03

  21   3.6347672e+03   1.1926763e+03  5.50e-08  1.88e-12  8.87e-04

  22   3.4351338e+03   1.7580033e+03  3.87e-08  1.99e-12  6.13e-04

  23   3.2210193e+03   2.3740504e+03  5.46e-08  1.70e-12  3.16e-04

  24   3.1623928e+03   2.5329028e+03  5.53e-08  1.98e-12  2.94e-04

  25   3.1130627e+03   2.6721473e+03  4.10e-08  2.08e-12  2.10e-04

  26   3.0881635e+03   2.7402274e+03  3.85e-08  2.23e-12  1.77e-04

  27   3.0543193e+03   2.8354994e+03  2.57e-08  1.95e-12  1.60e-04

  28   3.0459756e+03   2.8577311e+03  2.20e-08  2.36e-12  2.53e-04

  29   3.0313166e+03   2.8968290e+03  1.59e-08  2.23e-12  5.82e-04

  30   3.0194253e+03   2.9294679e+03  1.06e-08  2.08e-12  8.20e-04

  31   3.0188140e+03   2.9312219e+03  1.03e-08  2.63e-12  8.28e-04

  32   3.0115703e+03   2.9521662e+03  7.20e-09  2.25e-12  1.17e-03

  33   3.0058155e+03   2.9693195e+03  4.26e-09  2.00e-12  8.54e-04

  34   3.0012278e+03   2.9832484e+03  2.85e-09  1.70e-12  4.95e-04

  35   3.0010265e+03   2.9838880e+03  2.57e-09  2.41e-12  4.76e-04

  36   2.9987717e+03   2.9910483e+03  1.70e-09  1.72e-12  2.48e-04

  37   2.9986122e+03   2.9915700e+03  1.33e-09  2.34e-12  2.28e-04

  38   2.9974964e+03   2.9951858e+03  5.29e-09  1.58e-12  8.44e-05

  39   2.9974715e+03   2.9952720e+03  4.76e-09  2.29e-12  8.05e-05

  40   2.9973162e+03   2.9957767e+03  7.29e-08  2.25e-12  5.73e-05

  41   2.9970912e+03   2.9965129e+03  3.06e-08  1.57e-12  2.20e-05

  42   2.9970435e+03   2.9966712e+03  2.06e-08  1.87e-12  1.42e-05

  43   2.9970052e+03   2.9967977e+03  1.32e-08  1.75e-12  7.92e-06

  44   2.9969758e+03   2.9968962e+03  9.27e-09  1.62e-12  3.04e-06

  45   2.9969685e+03   2.9969204e+03  4.74e-09  1.81e-12  1.84e-06

  46   2.9969673e+03   2.9969242e+03  4.39e-09  2.31e-12  1.65e-06

  47   2.9969621e+03   2.9969418e+03  4.44e-09  1.75e-12  7.73e-07

  48   2.9969583e+03   2.9969543e+03  3.85e-09  1.64e-12  1.53e-07

  49   2.9969575e+03   2.9969569e+03  4.03e-09  1.66e-12  2.28e-08

  50   2.9969574e+03   2.9969574e+03  3.62e-09  1.82e-12  1.92e-09

  51   2.9969574e+03   2.9969574e+03  4.34e-07  5.89e-10  1.28e-09

Barrier time = 2.92 sec. (3479.29 ticks)


QP crossover.

  Primal and Dual:  Fixing 41783 variables.

   Elapsed crossover time = 10.20 sec. (10001.87 ticks, 27576 Superbasics left)

     Infeasibility:    Primal  9.96075462e-07     Dual  0.00000000e+00

   Elapsed crossover time = 17.69 sec. (20005.14 ticks, 22401 Superbasics left)

     Infeasibility:    Primal  2.49163817e-06     Dual  2.82150463e+00

   Elapsed crossover time = 24.31 sec. (30005.81 ticks, 22092 Superbasics left)

     Infeasibility:    Primal  1.64843608e-05     Dual  2.82150245e+00

   Elapsed crossover time = 31.34 sec. (40008.77 ticks, 21673 Superbasics left)

     Infeasibility:    Primal  1.64843608e-05     Dual  2.82149785e+00

   Elapsed crossover time = 38.27 sec. (50152.16 ticks, 17461 Superbasics left)

     Infeasibility:    Primal  1.64843608e-05     Dual  3.12227783e+01

   Elapsed crossover time = 45.53 sec. (60191.76 ticks, 16579 Superbasics left)

     Infeasibility:    Primal  1.64843608e-05     Dual  3.12228149e+01

   Elapsed crossover time = 52.81 sec. (70192.62 ticks, 14196 Superbasics left)

     Infeasibility:    Primal  1.64843608e-05     Dual  3.12228096e+01

   Elapsed crossover time = 59.72 sec. (80196.07 ticks, 11344 Superbasics left)

     Infeasibility:    Primal  1.64843608e-05     Dual  3.12228554e+01

   Elapsed crossover time = 66.34 sec. (90197.36 ticks, 8634 Superbasics left)

     Infeasibility:    Primal  1.64843608e-05     Dual  3.12229489e+01

   Elapsed crossover time = 72.03 sec. (100198.73 ticks, 2674 Superbasics left)

     Infeasibility:    Primal  1.64843608e-05     Dual  1.83402001e+02

  Primal:  Pushed 95, exchanged 19924.

  Dual  :  Pushed 4762, exchanged 18080.

Elapsed time = 75.89 sec. (105895.05 ticks, 0 iterations)



Iteration           Objective            In Variable           Out Variable

     1  I         2997.061956                x268609                x245090

     2  I         2997.061956                 x39804                x245479

     3  I         2997.061956                 x40193                x245186

.....

.....

.....

 2920      2648375510.965550                x336487                x131102

  2921      1063638058.813854                x336388                x128319

  2922       428781525.221638                x333605                x129517

  2923       351371174.191988                x334803                x129513

  2924       351371174.191988                x334799                x132875

Root relaxation solution time = 89.66 sec. (129793.28 ticks)

Root node processing (before b&c):

  Real time             =   91.80 sec. (131083.66 ticks)

Parallel b&c, 12 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) =   91.80 sec. (131083.66 ticks)

CPLEX 20.1.0.0: unrecoverable failure: singular basis
0 MIP simplex iterations
0 branch-and-bound nodes
No basis.
*************************************************************************

[AMPL Google Group]

The log indicates that CPLEX is using the barrier method to solve the continuous (root) relaxation of your problem. Eventually, CPLEX reports "Root relaxation solution time = 89.66 sec. (129793.28 ticks)" which indicates that it has finished working on the relaxation problem. But then immediately after that, CPLEX indicates that the whole solve run has finished, by displaying this timing summary:

Root node processing (before b&c):
  Real time             =   91.80 sec. (131083.66 ticks)
Parallel b&c, 12 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) =   91.80 sec. (131083.66 ticks)

Finally, the AMPL interface to CPLEX displays a brief summary of the results:

CPLEX 20.1.0.0: unrecoverable failure: singular basis
0 MIP simplex iterations
0 branch-and-bound nodes
No basis.

You might be able to avoid this failure by adding qtolin=1 to the cplex_options string. This tells CPLEX to linearize the objective as much as possible. If you try that, do you get a better result from CPLEX?

If you do not get a better result from CPLEX using qtolin=1, then can you send some files that we can use to reproduce the "singular basis" problem? That will make it possible to run a few tests to determine whether the cause is in the AMPL-CPLEX interface or in the CPLEX solver. Depending on the results of the tests, it may be possible to suggest some ways to avoid the problem.

--
Robert Fourer
am...@googlegroups.com

{#HS:1846249389-109565#}

[url=]am...@googlegroups.com

On Wed, Apr 13, 2022 at 8:50 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Since you are setting mipstartalg=4, CPLEX is solving the relaxation of the your MIQP using the barrier algorithm, probably followed by a crossover phase to get a basic solution. Thus the singular basis would be expected to occur in the crossover phase. To get more information about what's happening, replace mipdisplay=2 by mipdisplay=4 bardisplay=1 lpdisplay=2 (leaving other options as before) and post the resulting output. (You can copy all the output and paste it into your reply.)

Also when you "solved the relaxed problem" what options did you choose?

--
Robert Fourer
am...@googlegroups.com

[John Marcelo]

Hi Robert,

Thanks for your previous answer.

I tried qtlin, but there was no difference in the results. I think because my objective does not include the product of variables, only squares and linear terms. I suspect that the problem is in the crossover process performed by cplex, which doesn't converge and get a singular basis. Another point is that this problem  happens litlle, depending on my input data and solver/solution technique parameters.  Anyway, I attached my code files (I use ampl with Notepad). I will appreciate it if you can give me some suggestions about it.

Note: singular basis problem occurs in transition 14 of the code (after 2 or 3 minutes).

Thanks in advance

Regards

Atte.

Jonathan Ayala Marcelo

--
You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/M9mBZ5GjpD0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-1846249389-5931453792-1662143240-362797999%40helpscout.net.

[AMPL Google Group]

When I run your example on my computer, the first solve with integer variables is at transition 15, and the continuous relaxation is solved successfully. This is not surprising, however, since solving on a computer that has different hardware characteristics can result in a different iteration path, and since the "singular basis" error occurs only rarely (as you have observed).

I am going to run some more tests on a computer that has more cores, to see whether the error appears, and whether there are some other option settings that you should try.

--
Robert Fourer
am...@googlegroups.com

{#HS:1846249389-109565#}

On Fri, Dec 2, 2022 at 4:04 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hi Robert,
Thanks for your previous answer.
I tried qtlin, but there was no difference in the results. I think because my objective does not include the product of variables, only squares and linear terms. I suspect that the problem is in the crossover process performed by cplex, which doesn't converge and get a singular basis. Another point is that this problem happens litlle, depending on my input data and solver/solution technique parameters. Anyway, I attached my code files (I use ampl with Notepad). I will appreciate it if you can give me some suggestions about it.

Note: singular basis problem occurs in transition 14 of the code (after 2 or 3 minutes).

Thanks in advance
Regards

Atte.
Jonathan Ayala Marcelo

El vie, 2 sept 2022 a las 15:27, AMPL Google Group (<am...@googlegroups.com>) escribió:

On Fri, Sep 2, 2022 at 6:27 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

The log indicates that CPLEX is using the barrier method to solve the continuous (root) relaxation of your problem. Eventually, CPLEX reports "Root relaxation solution time = 89.66 sec. (129793.28 ticks)" which indicates that it has finished working on the relaxation problem. But then immediately after that, CPLEX indicates that the whole solve run has finished, by displaying this timing summary:

Root node processing (before b&c):
  Real time             =   91.80 sec. (131083.66 ticks)
Parallel b&c, 12 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) =   91.80 sec. (131083.66 ticks)

Finally, the AMPL interface to CPLEX displays a brief summary of the results:

CPLEX 20.1.0.0: unrecoverable failure: singular basis
0 MIP simplex iterations
0 branch-and-bound nodes
No basis.

You might be able to avoid this failure by adding qtolin=1 to the cplex_options string. This tells CPLEX to linearize the objective as much as possible. If you try that, do you get a better result from CPLEX?

If you do not get a better result from CPLEX using qtolin=1, then can you send some files that we can use to reproduce the "singular basis" problem? That will make it possible to run a few tests to determine whether the cause is in the AMPL-CPLEX interface or in the CPLEX solver. Depending on the results of the tests, it may be possible to suggest some ways to avoid the problem.

--
Robert Fourer
am...@googlegroups.com

[John Marcelo]

Thanks a lot Robert,

For the first time I hope that this error occurs (in your tests) in order to have your feedback.

Regards

Atte.

Jonathan Ayala Marcelo

--
You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/M9mBZ5GjpD0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-1846249389-6214266986-1670358382-1800686467%40helpscout.net.

[AMPL Google Group]

Running on a computer with more cores, I observed that the first solve with integer variables occurred at transition 14, but as in my earlier test, the continuous relaxation was solved successfully. So it appears that you will have to run some tests on your computer. There are a number of different settings you could try, which might offer greater reliability:

• Add mipstartalg=4 so that CPLEX solves the initial continuous relaxation using only the barrier algorithm, without running primal and dual simplex algorithms in parallel.
• Try threads=8 or even a smaller number, to see whether the barrier solver is more reliable when there is less parallelism.
• Try numericalemphasis=1 to request computations with more accuracy (though less speed).
• Try some different settings for the barrier algorithm, particularly baralg=1 or 2, barstart = 2, 3, or 4, and crossover=2. Also ordering = 1, 2, or 3 can affect barrier performance, but is less likely to affect reliability. (It is best to try different options separately at first.)

Maybe you will find an alternative setting that doesn't fail at all. Or you might find one that also fails occasionally, but on different runs. So then you can use your original setting, but on the runs that fail, you can try again with the alternative setting.

--
Robert Fourer
am...@googlegroups.com

{#HS:1846249389-109565#}

On Wed, Dec 7, 2022 at 1:45 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Thanks a lot Robert,
For the first time I hope that this error occurs (in your tests) in order to have your feedback.
Regards

Atte.
Jonathan Ayala Marcelo

El mar, 6 dic 2022 a las 21:26, AMPL Google Group (<am...@googlegroups.com>) escribió:

On Tue, Dec 6, 2022 at 8:26 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

When I run your example on my computer, the first solve with integer variables is at transition 15, and the continuous relaxation is solved successfully. This is not surprising, however, since solving on a computer that has different hardware characteristics can result in a different iteration path, and since the "singular basis" error occurs only rarely (as you have observed).

I am going to run some more tests on a computer that has more cores, to see whether the error appears, and whether there are some other option settings that you should try.

--
Robert Fourer
am...@googlegroups.com

[John Marcelo]

Thanks Robert,

I tried most of the options that you give me. The results were the following: 

- Adding mipstartalg=4 does not solve the problem.

- Curiously, setting baralg to 1 or 2 solved the error in iteration 14, but then the singular basis reappeared in iteration 15. 

- Setting barstar to 2 does not solve the problem.

- Setting barstar to 3 or 4 solved the problem. So, apparently using "primal estimate" for the initial starting point can give solutions for which the crossover phase can get a basis , but I really don't know if there is a relationship between them . 

Regards

Atte.

Jonathan Ayala Marcelo

--
You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/M9mBZ5GjpD0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-1846249389-6221234739-1670526555-1772222189%40helpscout.net.