Bug 100916 - Solver does not find the optimal solution
Summary: Solver does not find the optimal solution
Status: NEW
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
(earliest affected) release
Hardware: x86-64 (AMD64) Linux (All)
: medium normal
Assignee: Not Assigned
Depends on:
Blocks: Solver
  Show dependency treegraph
Reported: 2016-07-14 21:42 UTC by MatthiasRw
Modified: 2022-08-24 14:06 UTC (History)
3 users (show)

See Also:
Crash report or crash signature:
Regression By:

File with optimization problem (14.59 KB, application/vnd.oasis.opendocument.spreadsheet)
2016-07-14 21:42 UTC, MatthiasRw
Solver data (76.91 KB, image/png)
2016-07-18 12:05 UTC, MatthiasRw
Print screen of test data setup. (113.48 KB, image/png)
2019-05-02 15:58 UTC, Todor Balabanov
SolverErrorSuccess.ods (16.26 KB, application/vnd.oasis.opendocument.spreadsheet)
2020-08-18 07:31 UTC, LE GARREC Vincent
SuccessSolverOption.png (24.00 KB, image/png)
2020-08-18 07:32 UTC, LE GARREC Vincent

Note You need to log in before you can comment on or make changes to this bug.
Description MatthiasRw 2016-07-14 21:42:50 UTC
Created attachment 126212 [details]
File with optimization problem

Hi all!

I have calculated a simple optimization problem:

    A cylinder should have a volume of 1000cm³.
    How big must be height and radius to ensure that the surface is minimal?

In Excel we get after two seconds the (right) solution with radius = 5,42cm and height = 10,84cm.

But Calc gives me (after more than 15 seconds):
Radius = 3,65cm, height = 23,90cm (see attachment).

The calculation was made with DEPS Evolutionary Algorithm.

What's the problem?

Thanks for your help and best regards
Comment 1 Buovjaga 2016-07-18 06:16:18 UTC
So what should I do with the file? Lay it down like I'm some trained monkey. Go to Tools - Solver, input this into field x etc..

Change back to UNCONFIRMED after you have provided the information.
Comment 2 MatthiasRw 2016-07-18 12:05:18 UTC
Created attachment 126277 [details]
Solver data

sorry - you're right. I assumed that the solver data remain stored in the file.
Here the necessary information.
Thanks for your help.
Best regards
Comment 3 Tomaz Vajngerl 2016-07-21 01:39:24 UTC

Still, there is not guarantee that a evolutionary algorithm will find the optimal solution to the problem so I would say the result is something that could be expected. If you tune the parameters and add additional constraints you will arrive at a better solution - I could even match the one from excel.

No wonder excel writes a better solution as they bought their solver from the experts ;) 

I'm working on a simple evolutionary solver so we can have a NLP solver that can be included in LO without the need to have Java. I'll try to tune it so that it can find simple problems better but I'm not an expert and the solver is still a WIP.
Comment 4 MatthiasRw 2016-07-21 05:38:59 UTC
Hi Tomaz,

that should not be a fundamental critique. The solver is good in principle.
Thanks for that!

I just wanted to know what settings I need to change, to obtain (if appropriate) a better or the best result.

Maybe comes there still some mathematical geniuses together and create an even better tool ... ;-)

Thanks and best regards
Comment 5 QA Administrators 2017-09-01 11:15:24 UTC Comment hidden (obsolete)
Comment 6 MatthiasRw 2017-09-13 18:55:44 UTC
The bug remains - also in version  :-/

Calc does not find any solution at all, which is even close to the right result.
Either it stops immediately because of reaching a stagnation or iteration limit or the results are completely absurd.

The test was performed with the standard settings of the DEPS Evolutionary Algorithm.
What can I do?
Comment 7 QA Administrators 2018-10-23 02:49:45 UTC Comment hidden (obsolete)
Comment 8 Todor Balabanov 2019-05-02 15:58:22 UTC
Created attachment 151135 [details]
Print screen of test data setup.

Two more constraints.
Comment 9 Todor Balabanov 2019-05-02 15:59:43 UTC
I would like to suggest two more constraints in the example. Radius and height should be positive numbers.
Comment 10 Todor Balabanov 2019-05-02 17:00:44 UTC
DEPS solver is hybrid heuristic optimizer. It is based on Differential Evolution and Particle Swarm Optimization. 

If you look a little bit more of DE's chart-flow diagram you will see that DE works well with high dimensional spaces:


The example given in this bug report has only two variables (radius and height), which means that this is two-dimensional space. The constraint of 1000 volume makes the situation even worse. We call this kind of constraints "hard constraints", because usually they are difficult to be satisfied. 

DE is in the group of the genetic algorithms. It has crossover operation:


When you have only two variables your chromosomes have only two components. Literally you do not have what to crossover. It is absolutely expected that DE will perform bad in such situations. 

I am not good in PSO part of the solver, but PSO is an optimization heuristics in the rank of DE. Even if you check the source code you will see that PSO has pretty similar implementation to DE. This means that PSO also is not proper for low-dimensional problems.

I am not using Microsoft Excel (generally I am not using Windows) and it is difficult for me to test this example in Excel, but there is no direct correspondence between Excel solvers and Calc solvers. It does not matter that Excel solves this example efficiently. First of all most of the source code in Microsoft's products is closed. May be they are using some kind of DE, GA, PSO or something else, but may be they are using also something extra, which is particularly implemented for low-dimensional cases.
Comment 11 Luiz 2020-03-30 18:05:50 UTC
Excel's Sover uses a deterministic method to estimate a solution and Calc's does not (DEPS uses heuristics). Well, how I circunvented the problem? My limit conditions were $B$9 >= 999.9999 and $B$9 <= 1000.0001. For initial guess I forced radius value 5 and height was guessed with a GoalSeek to V = 1000. Why that? Because even an excelent "root finder" depends on the initial guesses. And the same solution was found with a bit more higher number of interations when compared to Excel.
Comment 12 LE GARREC Vincent 2020-08-18 07:31:13 UTC
Created attachment 164396 [details]

Personally, I always try to reduce constrains by computing the mean square root.

Please find enclosed the example that always success. I removed the constrain "volume must be 1000" by computing the following value : (1000-volume calculated)^2+surface. The goal is to have the minimum (subtract must be zero and surface must be the lowest possible).

But it's true it does not solve the initial problem.
Comment 13 LE GARREC Vincent 2020-08-18 07:32:09 UTC
Created attachment 164397 [details]
Comment 14 QA Administrators 2022-08-19 03:42:57 UTC Comment hidden (obsolete)
Comment 15 LE GARREC Vincent 2022-08-24 14:06:20 UTC
LibreOffice still can't find the right solution.

Version: (x64) / LibreOffice Community
Build ID: e93b7f6a5c5f9ee86546d95d7fe70ecc26b71b91
CPU threads: 16; OS: Windows 10.0 Build 22000; UI render: Skia/Vulkan; VCL: win
Locale: fr-FR (fr_FR); UI: fr-FR
Calc: CL

I tried to use ceres-solver library to find the solution. Library didn't find the right solution. I think it's not an easy problem.