Nonlinear calculation gets stuck

[joelmontoy]

I'm trying to solve several non-linear problems with CLP. But sometimes, the solver gets stuck and never finishes the calculation, even when the problem should have a solution (CLP solves slightly different problems without any trouble).

I've found that the problem happens in ClpSimplexNonlinear.cpp. The process never exits the loop that starts at line 618: while (problemStatus == -1) {.

It seems that when the call to result = pivotColumn(... at line 653 returns a value of "1", the loop continues forever. When the solver works fine, this "result" gets a value of "0" for several iterations and finally it gets the value of "3" and exits the loop. But when it gets a value of "1", it usually gets stuck getting ones and more ones forever.

I fixed the problem adding a if (result == 1) result = 0; before line 656 and it seems that everything goes fine, but I don't really know what I'm doing...

Could you check if there's something that can be fixed to avoid the solver getting stuck? Or do you need more information to find the cause of the problem?

That's how the code looks like after my "fix" adding a line before 656:

652    pivotRow_ = -1;
653    result = pivotColumn(rowArray_[3], rowArray_[0],
654      columnArray_[0], rowArray_[1], pivotMode, solutionError,
655      array1);    
new    if (result == 1) result = 0;
656    if (result) {
657      if (result == 2 && sequenceIn_ < 0) {

The line numbers refer to commit 9442bf3 on Jul 6, 2021.

Thank you very much!

[jjhforrest]

Can you give me a sample problem which goes wrong without fix?

[joelmontoy]

Thank you, John!

Sorry, but I don't have a simple problem that goes wrong.

I've tried to export our real-case model to ".mps" and ".lp" formats (methods writeLp and writeMps), but it seems that CLP.EXE is ignoring the quadratic part in the LP file and the MPS files doesn't contain any information about the quadratic coefficients.

I'm attaching the problem files anyway, but they both run in CLP as a linear program (not quadratic), so everything goes fine! Problem.zip

Is there any way I can send you the problem so that you can try it? I even tried to add a QMATRIX block in the ".mps" file by hand, but CLP thows an error.

This is the log printed by CLP before it gets stuck, just in case it can help you:

Coin0506I Presolve 2427 (-2591) rows, 1646 (-813) columns and 12096 (-11765) elements
Clp0014I Perturbing problem by 0.001% of 0.24718693 - largest nonzero change 0.00016129315 ( 22.109214%) - largest zero change 0.00016116688
Clp0006I 0  Obj 0.026709306 Primal inf 16378.898 (241)
Clp0000I Optimal - objective value 10.913144
Coin0511I After Postsolve, objective 11.912082, infeasibilities - dual 0.044061385 (17), primal 0 (0)
Coin0512I Presolved model was optimal, full model needs cleaning up
Clp0006I 0  Obj 11.912082 Dual inf 1.4223971 (273)
Clp0006I 200  Obj 11.788442 Dual inf 0.10852728 (158)
Clp0006I 252  Obj 11.76512 Dual inf 0.033506306 (127)
Clp0006I 257  Obj 11.764243 Dual inf 0.022322808 (119)
Clp0006I 269  Obj 11.763977 Dual inf 0.019813376 (108)
Clp0006I 274  Obj 11.763884 Dual inf 0.12260461 (103)
Clp0006I 323  Obj 11.749753 Dual inf 0.012523024 (95)
Clp0006I 368  Obj 11.739441 Dual inf 0.11102489 (102)
Clp0006I 373  Obj 11.739258 Dual inf 2.894996 (93)
Clp0006I 374  Obj 11.739239 Dual inf 2.8897841 (92)
Clp0006I 375  Obj 11.73922 Dual inf 2.8847107 (91)
Clp0006I 383  Obj 11.739201 Dual inf 2.8795489 (91)
Clp0006I 384  Obj 11.739181 Dual inf 2.8745499 (92)
Clp0006I 385  Obj 11.739162 Dual inf 2.8691874 (91)
Clp0006I 386  Obj 11.739143 Dual inf 2.8642487 (90)
Clp0006I 387  Obj 11.739124 Dual inf 2.8591821 (90)
Clp0006I 388  Obj 11.739105 Dual inf 0.57226371 (90)
Clp0006I 389  Obj 11.739086 Dual inf 0.57157553 (89)
Clp0006I 390  Obj 11.739066 Dual inf 0.56973886 (88)
Clp0006I 396  Obj 11.735193 Dual inf 0.11214633 (84)
Clp0006I 448  Obj 11.726801 Dual inf 0.12985616 (86)
Clp0006I 455  Obj 11.723003 Dual inf 0.24868139 (72)
Clp0006I 458  Obj 11.722701 Dual inf 0.011807404 (68)
Clp0006I 462  Obj 11.722223 Dual inf 0.049360996 (64)
Clp0006I 463  Obj 11.722182 Dual inf 0.003611875 (54)
Clp0006I 471  Obj 11.720597 Dual inf 0.0078144207 (63)
Clp0006I 472  Obj 11.720154 Dual inf 0.12370963 (64)
Clp0006I 499  Obj 11.718556 Dual inf 0.32002772 (69)
Clp0006I 531  Obj 11.716544 Dual inf 3.0041133 (105)
Clp0006I 571  Obj 11.714745 Dual inf 0.2845234 (54)
Clp0006I 578  Obj 11.712995 Dual inf 0.0230757 (54)
Clp0006I 616  Obj 11.704164 Dual inf 35.626188 (63)
Clp0006I 620  Obj 11.704092 Dual inf 2.5988041 (153)

[jjhforrest]

I am a bit confused (if you are using clp.exe and not a modified version). Clp seems to export quadratic objective correctly for mps files. Cbc did not do so as the export went through OsiSolverInterface::writeMpsNative which did not do so. I have just updated OsiClpSolverInterface.cpp in master so that it's writeMpsNative has modified code (only if quadratic). It is a simple change so you can just cut and paste it if you don't want to use master.

How exactly are you using the writeMps?

[joelmontoy]

Sorry, it was my fault. Thanks to your comments, I've succeed to export the ".mps" for the quadratic problem.

Just to explain: I'm working in C# using SONNET, but with the latest version of CLP. Initially I used solver.OsiSolver.writeMps to export the problem, but now I did solver.OsiSolver.getModelPtr().writeMps instead, which exported the problem correctly. problem.zip

Then, I managed to reproduce the problem using CLP.EXE, compiled for windows (Coin LP version 1.17.7, build Jan 12 2022), and importing the ".mps" file. However, it only gets stuck in certain conditions. In my case, I had to follow the following steps in CLP:

Clp:import problem.mps
Clp:solve
Clp:presolve off
Clp:solve → STUCK

This is the output of CLP during this process: CLP output.txt

If I do only the "import" and "solve", it works fine. If I do "import", "presolve off" and "solve", it's fine as well. I just hope you will be able to reproduce the problem too following the previous steps.

[jjhforrest]

I have not been able to reproduce the bug (different compilers etc etc) but I did manage to get a return code of 1. It looks as if the code is testing which of two values is larger - but one is xxe-11 and the other xxe-13. I think your fix will work as it changes things a bit - it does not really matter how. If you wish to find out more, you could set loglevel 63 before final solve and see what the output is (you may have to kill job if it will produce an infinite amount of output).

[joelmontoy]

Thank you, John, for spending your time in this issue. I'm glad to know that my fix is not harmful. And, as you say, it seems to solve the problem so far. I'll try with loglevel 63 to see if I can see what's happening better.