options.iterations_suffice is not working

[thomasnield]

Sorry it took so long to file this issue.

I don't think the iterations_suffice option is doing anything. Here is a working example:

https://github.com/thomasnield/kotlin-sudoku-solver

I made this Sudoku app where you can punch in a few numbers and then choose to have the solver do the rest at any point.

If I solve a completely empty grid, it churns for a long time. I'm assuming it is looking for all possible solutions. If I give it enough fixed numbers, it will solve fairly quickly due to the constraints limiting the space.

[thomasnield]

In the interim, I added this logic to impose a few random constraints to reduce the search space.

https://github.com/thomasnield/kotlin-sudoku-solver/blob/master/src/main/kotlin/Model.kt#L29-L33

[apete]

Most likely it's the iterations counter that is broken. (An iteration is not very well defined between the various solvers.) I'll have a look at this. May remove this functionality from the convex and linear solvers and only keep the functionality for the integer solver and keep track of the number of evaluated nodes (subproblems).

Don't hold your breath for this...

[thomasnield]

Okay. So help me understand... ojAlgo finds all possible solutions that meet the optimal result? Or does it stop on the first one it finds?

For cases without an optimization objective, is there a way to accommodate that?

[apete]

It will stop when:

1) Found optimal solution (the algorithm knows there cannot be a better solution) 2) Found at least 1 feasible solution, and time_suffice (iterations_suffice) is reached 3) time_abort (iterations_abort) is reached

If you have no objective function then (1) may never happen (will have to check details in code). Even if you do have one, it is not always "easy" to know that it is not possible to find a better solution. The integer solver often continues long after it actually found the optimal solution because it simply cannot derive/conclude that it's not possible to find a better solution.

[thomasnield]

Okay, so if I don't set the objective... that should stop churning on the first feasible solution then?

I'm taking a lengthy Coursera class on Discrete Optimization to build optimizers from scratch. Hoping I can dive into this code in the future and explore what you did. I noticed some branch and bound stuff in there.

[apete]

As far as I can see options.iterations_suffice is working.

Turn on options.debug(IntegerSolver.class) or options.progress(IntegerSolver.class) to get some info about what happening.

[simonzz]

Hi all,

I have the same problem when I try to

1. Use ConvexSolver to solve a QP
2. with Inequality constraint (therefore underlying it uses IterativeASS)
3. Set a lower precision in Options.feasibility and Options.solution

At some point the solver gets stuck - from debug log it looks like it's spending too long in one of the cycles, probably due to some numerical precision issues. And even when I set iterations_abort or time_abort in Options, they are not enforced.

I propose following fix: https://github.com/optimatika/ojAlgo/compare/develop...simonzz:patch-1?diff=split&name=patch-1#diff-6c49463507f1a716864f8ca93fd7c4be

[apete]

@simonzz Those changes you propose are probably good, but can we have a look at your actual problem before we apply them? Is it possible to get a PR with a test case that demonstrates the problem you have?

[apete]

Just merged a PR based on the patch from @simonzz.

Recently there has also been other changes related to this.

If there is (still) some problem I need a test case that demonstrates the problem.