Finding all optimal solutions

[JLiangWaterloo]

In general, a problem can have more than one solution where the objective is optimal. Currently the library only finds the first. Is it possible to add functionality to find all the optimal solutions?

For example:

public static void main(String[] args) {
    Solver solver = new Solver();
    BoolVar a = VF.bool("a", solver);
    BoolVar b = VF.bool("b", solver);

    solver.post(ICF.arithm(a, "+", b, ">=", 1));

    solver.findOptimalSolution(ResolutionPolicy.MAXIMIZE, a);
    System.out.println(a + ":" + b);

    solver.findNextOptimalSolution();
    System.out.println(a + ":" + b);
}

would print

a=1:b=0
a=1:b=1

[jgFages]

Hi Jimmy,

What about using an ISolutionMonitor for this?

public static void main(String[] args) {
        final Solver solver = new Solver();
        final BoolVar a = VF.bool("a", solver);
        final BoolVar b = VF.bool("b", solver);
        solver.post(ICF.arithm(a, "+", b, ">=", 1));

        // list of solutions
        final LinkedList<Solution> optSols = new LinkedList<>();
        solver.getSearchLoop().plugSearchMonitor(new IMonitorSolution() {
            int bestObj=0;
            @Override
            public void onSolution() {
                System.out.println("solution "+a + ":" + b+" has been found");
                int currentObj = a.getValue();
                // try to get better or equal solutions
                solver.post(ICF.arithm(a,">=",currentObj));
                // only keeps the best solutions found so far
                if(bestObj<currentObj){
                    bestObj = currentObj;
                    optSols.clear();
                }
                Solution sol = new Solution();
                sol.record(solver);
                optSols.add(sol);
            }
        });
        solver.findAllSolutions();

        // access all optimal solutions
        System.out.println("Optimal solutions:");
        for(Solution s:optSols){
            System.out.println(s.getIntVal(a)+" : "+s.getIntVal(b));
        }
    }

It would print

solution a = 0:b = 1 has been found
solution a = 1:b = 0 has been found
solution a = 1:b = 1 has been found
Optimal solutions:
1 : 0
1 : 1

[JLiangWaterloo]

That looks good.

If I only wanted 1 optimal solution, is there a performance/memory penalty doing it this way instead of using findOptimalSolution?

Thanks.

[JLiangWaterloo]

I see one big issue with this strategy. Normally finding the next solution is done one the fly, ie. it doesn't find the 2nd, 3rd, 4th, 5th solution until it's asked for. Here all optimal the solutions are computed before even asked for it. So even if I really only wanted 5 optimal solutions, it might compute end up computing 5000 optimal solutions before it's finished solving. (If I only wanted 1 optimal solution, then I should fall back on findOptimalSolution for performance reasons.)

[jgFages]

Yes. Actually there is another overhead (which may be more important): usually each time a solution is computed, we look for a strictly better one, within this strategy, we look for better or equal solutions, so the entire search tree is bigger... It was more a workaround to answer you shortly than an optimum approach!

[chocotrust]

What about finding an optimal solution, resetting the search, restricting the domain of the objective variable to the optimal value and finding all solutions (or only the n first ones)?

[JLiangWaterloo]

@chocotrust

Suppose I have a search tree, and the solver goes down this search tree until it finds a solution at node B. Then it tries to find a better solution but the solver does not find one, so B is an optimal solution.

Now I want to find the next optimal solution. Does the search start at the root node or node B? If I start at the root again, then it is possible that I end up at node B again. So I would need a strategy to detect duplicate solutions, but that's doable. However, the solver wasted a lot of time to find B again when the solution is already known.

The second concern I have is that if B is an optimal solution, then there are likely other optimal solutions that are close to B in the search tree (this is true for my type of optimization problems, it might not be true for all problems). If the search restarts at the root node, then I would lose the advantage of locality of the solutions.

If @chocotrust 's strategy is the right way to go, then who should implement the strategy? Should the library implement it so that it secretly restarts the search behind the scenes when asked for the next optimal solution, and it's abstracted away from the user? Or should the user of the library be responsible in implementing the strategy on top of the library?

[chocotrust]

Hi Jimmy,

1. To know that B is the optimal solution, you have to close the search tree, ie ends the search. So, your first proposal (not starting at root node) is not possible as is. And you have to launch a second search with a fix objective variable, possibly finding B again (but filtering already known solution should not hard to do, using extension constraints or nogoods). I would not be that sure that the solver wastes lot of time finding B again, because you added a cut on the objective variable that reduces drastically the search space, and possibly a nogood (or a constraint) which avoids finding B again.

2. then there are likely other optimal solutions that are close to B in the search tree

That's clearly not true for all kind of problems. But once again, you have to prove the optimality of a value (ending the tree search, hence leaving region close to B), before iterating over equivalent solution. If you can say that a value is optimal without ending the tree search, that's another problem we need to think of.

1. If that's not a question of resolution time, you could do it right away. As far as I know, you are working with the source code. So simply change: this.search.setObjectivemanager(new IntObjectiveManager(objective, policy, this)); with: this.search.setObjectivemanager(new IntObjectiveManager(objective, policy, this,false)); This doesn't post a strict cut (next solution < Best found so far) but a relax one (next solution <= Best found so far). The issue is that you will dive to the optimal solution slowly.

Otherwise, I think the user should do it by himself, it is just a few lines of code:

int bestvalue = objective.getValue();
solver.getSearchLoop().reset();
solver.post(ICF.arithm(objective, "=", bestvalue));
solver.set(ISF.inputOrder_InDomainMin(objects));
solver.findAllSolutions();

Hope it helps CP

[JLiangWaterloo]

Is findAllSolutions the only possibility? I'd like to find these optimal solutions on demand using findSolution and findNextSolution.

public static void main(String[] args) {
    Solver s = new Solver();
    BoolVar b1 = VF.bool("b1", s);
    BoolVar b2 = VF.bool("b2", s);
    s.post(ICF.arithm(b1, "<=", b2));

    s.findOptimalSolution(ResolutionPolicy.MINIMIZE, b1);
    System.out.println(b1 + " " + b2);

    int bestvalue = b1.getValue();
    s.getSearchLoop().reset();
    s.post(ICF.arithm(b1, "=", bestvalue));
    s.set(ISF.inputOrder_InDomainMin(new BoolVar[]{b1, b2}));
    int count =0;
    if (s.findSolution()) {
        do {
            count++;
            System.out.println(b1 + " " + b2);
        } while (s.nextSolution());
    }
    System.out.println(count + " optimal solutions.");
}

The above code prints "1 optimal solutions" which is wrong. If I used findAllSolutions like in your example, it will find 2 optimal solutions.

but filtering already known solution should not hard to do, using extension constraints or nogoods

I'm not familiar with the terminology. Can you briefly explain what you mean?

Thanks a bunch!

[jgFages]

Hi

I think you should add this right after the reset:

solver.getSearchLoop().setObjectivemanager(new IntObjectiveManager(null, ResolutionPolicy.SATISFACTION, solver));

Otherwise the solver will try to find better each time it has a solution...

[JLiangWaterloo]

It didn't make a difference. In fact, that line of code is the first thing that Solver.findSolution does.

[chocotrust]

@jgFages the solver.getSearchLoop().reset() already erases the objective manager

[chocotrust]

Ok, I got it!! When one looks for the optimal solution, a search monitor is plugged in to store the last solution. However, it has an effect on the tree search: it forces the search tree the restore the root node and then force the last solution found so far to be set on root node. That's clearly an issue, because when the search is reset, the search monitor is not removed and it bugs the expected behavior... Well, I need to think about that before patching it...

[chocotrust]

Well, as you are kind of an expert in Choco3, the simplest way to do it is to change the call to

solver.findOptimalSolution(ResolutionPolicy.MINIMIZE, b1);

by

solver.getSearchLoop().setObjectivemanager(new IntObjectiveManager(b1, ResolutionPolicy.MINIMIZE, solver));
//search.plugSearchMonitor(new LastSolutionRecorder(new Solution(), true, solver));
if (solver.getEngine() == NoPropagationEngine.SINGLETON) {
    solver.set(new SevenQueuesPropagatorEngine(solver));
}
solver.getSearchLoop().getMeasures().setReadingTimeCount(System.nanoTime());
solver.getSearchLoop().launch(false);

Hope it helps CP

[JLiangWaterloo]

I tried the test case you wrote but it doesn't work. Without the LastSolutionRecorder, the solution that was found does not get restored. It only worked by chance that b1.getValue() returns b1.getLB() which happens to be 0 for the domain [0, 1].

public static void main(String[] args) {
    Solver solver = new Solver();
    BoolVar b1 = VF.bool("b1", solver);
    BoolVar b2 = VF.bool("b2", solver);
    solver.post(ICF.arithm(b1, "<=", b2));
    solver.getSearchLoop().setObjectivemanager(new IntObjectiveManager(b1, ResolutionPolicy.MINIMIZE, solver));
    //search.plugSearchMonitor(new LastSolutionRecorder(new Solution(), true, solver));
    if (solver.getEngine() == NoPropagationEngine.SINGLETON) {
        solver.set(new SevenQueuesPropagatorEngine(solver));
    }
    solver.getSearchLoop().getMeasures().setReadingTimeCount(System.nanoTime());
    solver.getSearchLoop().launch(false);
    System.out.println(b1 + " " + b2);
    if(!b1.instantiated() || !b2.instantiated()) {
        throw new Error(b1 + " and " + b2 + " are not instantiated");
    }
    int bestvalue = b1.getValue();
    solver.getSearchLoop().reset();
    solver.post(ICF.arithm(b1, "=", bestvalue));
    solver.set(ISF.inputOrder_InDomainMin(new BoolVar[]{b1, b2}));
    int count = 0;
    if (solver.findSolution()) {
        do {
            count++;
            System.out.println(b1 + " " + b2);
        } while (solver.nextSolution());
    }
}

I added the error checking. Running the code will throw "Exception in thread "main" java.lang.Error: b1 = [0,1] and b2 = [0,1] are not instantiated".

[jgFages]

Indeed. The problem of the LastSolutionRecorder is that it restores the last solution:

@Override
    public void afterClose() {
        if(restoreOnClose && solution.hasBeenFound()){
            try{
                solver.getSearchLoop().restoreRootNode();
                solver.getEnvironment().worldPush();
                solution.restore();
            }catch (ContradictionException e){
                throw new UnsupportedOperationException("restoring the last solution ended in a failure");
            }
            solver.getEngine().flush();
        }
    }

So if you simply want to have access to the best value, use a classical IMonitorSolution to store the best value. If you want to store the entire solution, copy the LastSolutionRecorder, but remove the restoration part.

[JLiangWaterloo]

I modified the example to so that the LastSolutionRecorder does not automatically restore on close.

public static void main(String[] args) throws ContradictionException {
    Solver solver = new Solver();
    BoolVar b1 = VF.bool("b1", solver);
    BoolVar b2 = VF.bool("b2", solver);
    solver.post(ICF.arithm(b1, "<=", b2));
    solver.getSearchLoop().setObjectivemanager(new IntObjectiveManager(b1, ResolutionPolicy.MAXIMIZE, solver));
    // Do not automatically restore on close
    LastSolutionRecorder recorder = new LastSolutionRecorder(new Solution(), false, solver);
    solver.getSearchLoop().plugSearchMonitor(recorder);
    if (solver.getEngine() == NoPropagationEngine.SINGLETON) {
        solver.set(new SevenQueuesPropagatorEngine(solver));
    }
    solver.getSearchLoop().getMeasures().setReadingTimeCount(System.nanoTime());
    solver.getSearchLoop().launch(false);
    // Manually restore
    recorder.getLastSolution().restore();
    System.out.println(b1 + " " + b2);
    if (!b1.instantiated() || !b2.instantiated()) {
        throw new Error(b1 + " and " + b2 + " are not instantiated");
    }
    int bestvalue = b1.getValue();
    // TODO: forbid the current solution from happening again.
    solver.getSearchLoop().reset();
    solver.post(ICF.arithm(b1, "=", bestvalue));
    solver.set(ISF.inputOrder_InDomainMin(new BoolVar[]{b1, b2}));
    int count = 0;
    if (solver.findSolution()) {
        do {
            count++;
            System.out.println(b1 + " " + b2);
        } while (solver.nextSolution());
    }
}

Unforunately, now I'm getting "b1 = 1 b2 = 0" as a solution now, which should not be possible.

[chocotrust]

That should do the job:

Solver solver = new Solver();                                                                              
final BoolVar b1 = VF.bool("b1", solver);                                                                  
BoolVar b2 = VF.bool("b2", solver);                                                                        
solver.post(ICF.arithm(b1, "<=", b2));                                                                     
solver.getSearchLoop().setObjectivemanager(new IntObjectiveManager(b1, ResolutionPolicy.MAXIMIZE, solver));
//LastSolutionRecorder recorder = new LastSolutionRecorder(new Solution(), false, solver);                 
final int[] bestValue = {-999};                                                                            
solver.getSearchLoop().plugSearchMonitor(new IMonitorSolution() {                                          
    @Override                                                                                              
    public void onSolution() {                                                                             
        bestValue[0] = b1.getValue();                                                                      
    }                                                                                                      
});                                                                                                        
//solver.getSearchLoop().plugSearchMonitor(recorder);                                                      
if (solver.getEngine() == NoPropagationEngine.SINGLETON) {                                                 
    solver.set(new SevenQueuesPropagatorEngine(solver));                                                   
}                                                                                                          
solver.getSearchLoop().getMeasures().setReadingTimeCount(System.nanoTime());                               
solver.getSearchLoop().launch(false);                                                                      
// TODO: forbid the current solution from happening again.                                                 
solver.getSearchLoop().reset();                                                                            
solver.post(ICF.arithm(b1, "=", bestValue[0]));                                                            
solver.set(ISF.inputOrder_InDomainMin(new BoolVar[]{b1, b2}));                                             
int count = 0;                                                                                             
if (solver.findSolution()) {                                                                               
    do {                                                                                                   
        count++;                                                                                           
        System.out.println(b1 + " " + b2);                                                                 
    } while (solver.nextSolution());                                                                       
}                                                                                                          

[JLiangWaterloo]

Should I be flushing the engine as well?

solver.getEngine().flush();

The problem is that reseting the search loop does not reset the propagators and their masks.

[JLiangWaterloo]

Here's the solution I think I'm going with.

public static void main(String[] args) throws ContradictionException {
    final Solver solver = new Solver();                                                                              
    final BoolVar b1 = VF.bool("b1", solver);                                                                  
    BoolVar b2 = VF.bool("b2", solver);                                                                        
    solver.post(ICF.arithm(b1, "<=", b2));                                                                     
    solver.getSearchLoop().setObjectivemanager(new IntObjectiveManager(b1, ResolutionPolicy.MINIMIZE, solver));
    //LastSolutionRecorder recorder = new LastSolutionRecorder(new Solution(), false, solver);                 
    final Solution sol = new Solution();
    solver.getSearchLoop().plugSearchMonitor(new IMonitorSolution() {                                          
        @Override                                                                                              
        public void onSolution() {                                                                             
            sol.record(solver);
        }                                                                                                      
    });                                                                                                        
    if (solver.getEngine() == NoPropagationEngine.SINGLETON) {                                                 
        solver.set(new SevenQueuesPropagatorEngine(solver));                                                   
    }
    solver.getSearchLoop().getMeasures().setReadingTimeCount(System.nanoTime());                               
    solver.getSearchLoop().launch(false);                                                                      
    sol.restore();
    System.out.println(b1 + " " + b2);
    int best = b1.getValue();
    // TODO: forbid the current solution from happening again.                                                 
    solver.getEngine().flush();
    solver.getSearchLoop().reset();
    solver.post(ICF.arithm(b1, "=", best));
    int count = 0;                                                                                             
    if (solver.findSolution()) {                                                                               
        do {                                                                                                   
            count++;                                                                                           
            System.out.println(b1 + " " + b2);                                                  
        } while (solver.nextSolution());                                                                       
    }                                                                                                          
}

I still want to record the first solution, rather than throwing it away because response time is important, especially since other objective solvers based on SAT/SMT do not throw them away. The code looks a bit messy but as long as it works.

[chocotrust]

I don't understand why you need to flush the engine. The reset instruction replaces the current engine by a VOID one.

[chocotrust]

When I comment solver.getEngine().flush(); i found no bug.

Anyway, there is no easy way to avoid finding the first solution while solving the problem twice. You can plug nogood store in, but that's tricky because, in our implementation, nogoods are recorded on restart, not on solution (see Nogood recording from restart and the classes). A nogood is a partial instantiation of the variables that couldn't be extended to a solution. In your case, the nogood will represent a complete instantiation (which is a solution), but that you don't want to find twice. The nogood store is a constraint, so it can filter forbidden values from variables domain.

But, you will need to extend the current one to monitor solutions, not restarts. And you will also have to change a little bit the way it compute nogood, because, to be valid a nogood computed on restart there must be a negated decision in the decision path...

As I write, I think that would be certainly clearer if you read the article first.

[JLiangWaterloo]

I don't understand why you need to flush the engine. The reset instruction replaces the current engine by a VOID one.

When I comment solver.getEngine().flush(); i found no bug.

Modify my previous examples in these 2 steps:

1. Change minimize to maximize
2. Comment out the flush line

Then there will find a wrong solution. The problem (I think) is that solution.restore() modifies some of the variables and the propagators get notified and updates their mask. Setting the engine to VOID does not reset the state of the propagators that changed during the solution's restore.

[chocotrust]

You're right, restoring the solution instantiates (using var.instantiateTo(..) method) variables to values. Then a propagation should be done to validate the modifications (or flushing it..).

[JLiangWaterloo]

Anyway, there is no easy way to avoid finding the first solution while solving the problem twice.

My plan is very primitive and it does not involve modifying the search algorithm to prune the duplicate. The idea is to keep the original solution around and if I ever find another solution that's the same, then I'll toss the other solution away. A solution is just a mapping of variables to values, so checking if two solutions are the same after the search is simple. This also works with set variables which are important for me.