Implement a new algorithm in sketch solver

Here's the place for discussion related to coding in FreeCAD, C++ or Python. Design, interfaces and structures.
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
_Nemo
Posts: 117
Joined: Sat Feb 06, 2021 8:25 am

Implement a new algorithm in sketch solver

Post by _Nemo »

The current solver PlaneGCS uses three traditional optimization algorithms to solve nonlinear equations.
I wonder if there are any defects in the use of these three algorithms.
Can intelligent optimization algorithm be used to solve these defects?
User avatar
adrianinsaval
Veteran
Posts: 5541
Joined: Thu Apr 05, 2018 5:15 pm

Re: Implement a new algorithm in sketch solver

Post by adrianinsaval »

what optimizations do you have in mind?
_Nemo
Posts: 117
Joined: Sat Feb 06, 2021 8:25 am

Re: Implement a new algorithm in sketch solver

Post by _Nemo »

adrianinsaval wrote: Tue May 30, 2023 2:59 pm what optimizations do you have in mind?
Such as initial value sensitivity, multiple solutions, solution stability and solution speed, etc.
User avatar
adrianinsaval
Veteran
Posts: 5541
Joined: Thu Apr 05, 2018 5:15 pm

Re: Implement a new algorithm in sketch solver

Post by adrianinsaval »

Initial values are the current positions of the geometry so I don't think there's much that can be done on that front. Can you be a little more explicit on what you are talking about? I'm not familiar with the term "intelligent optimization algorithm", to be expected since I'm not well versed in how the solver works.
_Nemo
Posts: 117
Joined: Sat Feb 06, 2021 8:25 am

Re: Implement a new algorithm in sketch solver

Post by _Nemo »

adrianinsaval wrote: Tue May 30, 2023 3:41 pm Initial values are the current positions of the geometry so I don't think there's much that can be done on that front. Can you be a little more explicit on what you are talking about? I'm not familiar with the term "intelligent optimization algorithm", to be expected since I'm not well versed in how the solver works.
I am actually looking for a research direction on geometric constraint solving, I need to write my master's thesis and I need to have some algorithmic innovation to meet the graduation requirements.
My question may be on the theoretical side, as the BFGS, LM and Dogleg algorithms currently used by PlaneGCS are all traditional optimisation algorithms, whereas intelligent optimisation algorithms include genetic algorithms, particle swarm algorithms and simulated annealing algorithms to name a few.
I now need to know what problems the current two-dimensional solver have and whether they can be solved by the algorithms.
Last edited by _Nemo on Wed May 31, 2023 7:03 am, edited 1 time in total.
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: Implement a new algorithm in sketch solver

Post by abdullah »

_Nemo wrote: Wed May 31, 2023 2:23 am I now need to know what problems the current two-bit solvers have and whether they can be solved by the algorithms.
Generally speaking the algorithms (mainly DogLeg and LM, which are the default and the alternative used by some users by default) work reasonably well. They converge and they do it in an acceptable number of iterations.

One general perception is that LM is more robust in "not flipping" the geometry. So basically, it tends to converge to local minima closer to the original solution. If you want to look at the geometric effect, you could see tickets (GH issues and/or bugtracker issues, included closed ones). I am not sure what can be done. Traditional approach of launching different methods, or a same method with different parameters to try to find several solutions (possibly in parallel for performance reasons), still hits the problem that the different local minima are mathematically compliant solutions, and it is not straightforward to tell which one is the "non-flipped" one, and thus the one acceptable by the user. I think that solving this issue has more to do with writing better constraints (directional, more stable that would not accept flipping as a solution) than to the algorithms themselves. However, you may find an alternative.

We do have another problem with large dimensions (kilometers), in which the frameworks precision is not scaled (continues to be in the order of nanometers, if I remember correctly) and this does lead to lack of convergence. However, IMO the blame is on the framework, not on the solver algorithm. I comment on this so that you have a broad idea of the issues, if you decide to walk your way in the issues.

Then one has corner cases (search for lack of convergence in GH issues/bugtracker). I think (but I do not remember every single case), often the reason is one of: a) the constraints are poorly written, b) the previous diagnostic algorithm (which prevents solving) failed to detect a conflicted situation. The solver cannot compensate for these issues.

On the bright side, if you implement another algorithm and want to test corner cases of benchmark, FreeCAD offers a very low energy entry point. Bear in mind only that constraints today provide you with the error and gradient. If any of your intended algorithms needs more information than that, then you will have to rewrite the constraints.
_Nemo
Posts: 117
Joined: Sat Feb 06, 2021 8:25 am

Re: Implement a new algorithm in sketch solver

Post by _Nemo »

abdullah wrote: Wed May 31, 2023 5:54 am On the bright side, if you implement another algorithm and want to test corner cases of benchmark, FreeCAD offers a very low energy entry point. Bear in mind only that constraints today provide you with the error and gradient. If any of your intended algorithms needs more information than that, then you will have to rewrite the constraints.
Thank you for your patient reply!

I have corrected the careless mistakes made by using translation software. :oops:

My undergraduate thesis was to implement the DFP algorithm in FreeCAD and tested it against three other built-in algorithms using the Test WB tool. Although there was no actual performance improvement, one data point was interesting: the LM method reported SuccessfulSolutionInvalid when solving the Curve test case. This means that the solving algorithm found a solution to the constraint system, but the geometry applied with this solution was not accepted by OCE (the community version of Open CASCADE) as being OCE-invalid. I am not sure if this issue has been resolved or not

You also mentioned the problem with diagnostic algorithms. Does this algorithm use graph theory to detect conflicts? Do you think it is feasible to study and improve this algorithm?
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: Implement a new algorithm in sketch solver

Post by abdullah »

_Nemo wrote: Wed May 31, 2023 7:27 am Although there was no actual performance improvement, one data point was interesting: the LM method reported SuccessfulSolutionInvalid when solving the Curve test case. This means that the solving algorithm found a solution to the constraint system, but the geometry applied with this solution was not accepted by OCE (the community version of Open CASCADE) as being OCE-invalid. I am not sure if this issue has been resolved or not
Could you point exactly to the specific test that is failing (link to GH would be best)?

A solution where convergence is achieved can be invalid geometrically speaking. For example, a zero radius circle can very well meet constraints but be undesirable.

In many of these cases, it is the constraints themselves that could be improved (for example by limiting the step size, see maxStep function, or by rewriting the constraint error/divergence differently).

I cannot rule out an issue with LM, but it scores lows within my expectations. Yet, we investigate cases when we do not know. That is what we should do here.
_Nemo wrote: Wed May 31, 2023 7:27 am You also mentioned the problem with diagnostic algorithms. Does this algorithm use graph theory to detect conflicts? Do you think it is feasible to study and improve this algorithm?
No graphs theory there. Diagnosis has two main steps:
1) The Jacobian matrix of the parameters and constraints is created and QR decomposed (SparseQR). QR is a rank revealing decomposition and the DoFs are obtained directly from the rank. From the many rank reveling matrix decompositions (LU, ...), QR has the advantage that R, which is an upper triangular matrix, contains information about which constraints are redundant/conflicting.
2) An heuristic algorithm called "Popularity contest" tries to identify the most likely culprit conflicting/redundant constraint to notify the user. A subsystem is solved it to identify whether it was redundant or conflicting.

I am under the impression that (1) is sound, but that (2) is the weakest link of the chain (and the source of no little amount of bugs/issues).

FreeCAD may certainly benefit from improvements in the latter. So yes, you have here a clear vector of improvement. Basically the R of the QR will give you groups of constraints that are "part of the problem". Each group forms a "problem" (e.g. linear dependency if redundant). It is possible to have several groups. If there are common constraints to several groups, it may be possible to satisfy several groups by removing just one common constraint. Constraint here is "solver constraint". What is generally removed is a sketcher constraint (what the user constraints). A Sketcher constraint may consist of several solver constraints. Each solver constraint takes away one DoF. To achieve the goal, a user may need to substitute one constraint taking several DoFs with another different one. Typical examples are substituting a symmetry constraint with a horizontal alignment constraint. Whether to use graph theory, or a combination of graph theory and iterative solvers,... well that is for you to decide. If you succeed users of FreeCAD would be chanting about the great _Nemo. :)

All the fun about diagnosis starts here:
https://github.com/FreeCAD/FreeCAD/blob ... .cpp#L4659

(2) starts here:
https://github.com/FreeCAD/FreeCAD/blob ... .cpp#L5270

Let me know if you need more information.
_Nemo
Posts: 117
Joined: Sat Feb 06, 2021 8:25 am

Re: Implement a new algorithm in sketch solver

Post by _Nemo »

abdullah wrote: Wed May 31, 2023 8:34 am Let me know if you need more information.
Thank you so much! You are truly a kind person! I will go study the problem with diagnostic algorithm, and will keep you updated if I make any progress! :D
_Nemo
Posts: 117
Joined: Sat Feb 06, 2021 8:25 am

Re: Implement a new algorithm in sketch solver

Post by _Nemo »

abdullah wrote: Wed May 31, 2023 8:34 am Let me know if you need more information.
Hello my dear friend!
Could you please provide me with a few issues in the bug tracker related to diagnostic algorithms? Or could you advise me on how to find such issues myself? I need them as test cases.
Here are two theoretical questions I would like to consult with you.
First, are there any constraint conflicts that current diagnostic algorithms cannot detect so that causes the convergence problems?
Second, can intelligent optimization algorithms be helpful in solving multi-solution problems? Is the current solver architecture convenient to extend for providing multiple solutions?
Post Reply