Multi-objective optimization

[JLiangWaterloo]

I would like to implement multi-objective optimization (https://en.wikipedia.org/wiki/Multi-objective_optimization) with Choco to find all pareto optimal solutions. It's a common problem in software engineering. I'm not sure what's the best way to go about implementing or whether it's possible to implement a new ObjectiveManager to do it.

[jgFages]

Hi jimmy,

This should be quite easy to do I believe. To me, you need to work on two DISTINCT things: 1) Managing the optimization process to skip worse or equal solutions 2) Storing only the best (incomparable) solutions

For step 1), I believe you can simply call "findAllSolutions" (no objective manager) but plug an ISolutionMonitor which posts a new permanent constraint to forbid worse solutions (I think it is solver.postCut()). This might be easier to do than implementing your own objective manager (which is of course an alternative).

For step 2), you need to somehow manage the solution pool. You can do that externally, or by implementing yourself a SolutionRecorder. A priori, such a recorder should extend the AllSolutionRecorder and delete worse solutions each time a new solution is found. This will save memory. From runtime considerations, it might be more efficient to filter worse solutions once and for all after the search process (if memory does not crash before!).

In case you take the first option (removing worse solutions on the fly) and still encounter some memory issues, I see several improvement leads:

• recycle Solution objects which have been created
• replace the Java LinkedList of solutions which *\ with a homemade one which will be able to recycle Cell objects (cells of the list). If this remains insufficient, then I suggest to perform some kind of sampling, i.e. to remove pareto solutions which are too close from one another. I believe this makes sense in a lot of applications, but of course, you will not get the full set of solutions.

Have fun!

[JLiangWaterloo]

Thanks for the advice, I'll take a crack at it and see how it goes. I'm thinking of implementing the "Guided Improvement Algorithm" (http://dspace.mit.edu/handle/1721.1/46322) which is the same as suggestion 1) except it will try to look for "strictly better" solutions until it can't (in which case it's optimal). Then it will pop the "strictly better" constraints and add new ones based on the newest optimal solution to avoid solutions that are strictly worse. I think it should work fine with the current library.

[JLiangWaterloo]

I thought I should share my sollution for anyone in the future who is also interested. Here is proof of concept (implementation of the guided improvement algorithm):

public static void main(String[] args) {
    // Objectives are to maximize "a" and maximize "b".
    Solver solver = new Solver();
    IntVar a = VF.enumerated("a", 0, 2, solver);
    IntVar b = VF.enumerated("b", 0, 2, solver);
    IntVar c = VF.enumerated("c", 0, 2, solver);

    solver.post(ICF.arithm(a, "+", b, "<", 3));

    // START extra variables/constraints for guided improvement algorithm
    List<Constraint> stack = new ArrayList<>();
    IntVar lbA = VF.enumerated("lbA", 0, 2, solver);
    IntVar lbB = VF.enumerated("lbB", 0, 2, solver);
    BoolVar aSBetter = ICF.arithm(a, ">", lbA).reif();
    BoolVar bSBetter = ICF.arithm(b, ">", lbB).reif();
    BoolVar aBetter = ICF.arithm(a, ">=", lbA).reif();
    BoolVar bBetter = ICF.arithm(b, ">=", lbB).reif();
    push(ICF.arithm(lbA, "=", a), stack, solver);
    push(ICF.arithm(lbB, "=", b), stack, solver);
    Constraint strictlyBetter
            = LCF.or(
                    LCF.and(aSBetter, bBetter),
                    LCF.and(aBetter, bSBetter));
    // END extra variables/constraints for guided improvement algorithm

    while (solver.findSolution()) {
        int bestA;
        int bestB;
        do {
            bestA = a.getValue();
            bestB = b.getValue();

            popAll(stack, solver);
            push(ICF.arithm(lbA, "=", bestA), stack, solver);
            push(ICF.arithm(lbB, "=", bestB), stack, solver);
            push(strictlyBetter, stack, solver);
        } while (solver.nextSolution());

        popAll(stack, solver);

        push(ICF.arithm(a, "=", bestA), stack, solver);
        push(ICF.arithm(b, "=", bestB), stack, solver);
        push(ICF.arithm(lbA, "=", bestA), stack, solver);
        push(ICF.arithm(lbB, "=", bestB), stack, solver);

        solver.getEngine().flush();
        solver.getSearchLoop().reset();

        if (solver.findSolution()) {
            do {
                System.out.println("Found pareto optimal solution: " + a + ", " + b + ", " + c);
            } while (solver.nextSolution());
        }

        popAll(stack, solver);

        solver.getEngine().flush();
        solver.getSearchLoop().reset();

        solver.post(LCF.or(
                        ICF.arithm(a, ">", bestA),
                        ICF.arithm(b, ">", bestB)));
    }
}

This will output:

Found pareto optimal solution: a = 1, b = 1, c = 0
Found pareto optimal solution: a = 1, b = 1, c = 1
Found pareto optimal solution: a = 1, b = 1, c = 2
Found pareto optimal solution: a = 0, b = 2, c = 0
Found pareto optimal solution: a = 0, b = 2, c = 1
Found pareto optimal solution: a = 0, b = 2, c = 2
Found pareto optimal solution: a = 2, b = 0, c = 0
Found pareto optimal solution: a = 2, b = 0, c = 1
Found pareto optimal solution: a = 2, b = 0, c = 2

Note that this requires a special constraint

[JLiangWaterloo]

I forgot to include the two helper functions in the above comment.

private static void popAll(List<Constraint> stack, Solver solver) {
    for (Constraint constraint : stack) {
        solver.unpost(constraint);
    }
}

private static void push(Constraint constraint, List<Constraint> stack, Solver solver) {
    stack.add(constraint);
    solver.post(constraint);
}

[JLiangWaterloo]

Update: The above code is incorrect. To see why, change the domain of variables A and B to be [-2,-1,...,2] and the solver will find incorrect solutions. I believe this is due to popping/unposting constraints when not in the root node of the search tree. Unposting a constraint does not "undo" all the propagations it caused while travelling down to the current node. I rewrote the algorithm to avoid this issue and it seems to work. The code is below.

public static void main(String[] args) {
    // Objectives are to maximize "a" and maximize "b".
    Solver solver = new Solver();
    IntVar a = VF.enumerated("a", -2, 2, solver);
    IntVar b = VF.enumerated("b", -2, 2, solver);
    IntVar c = VF.enumerated("c", 0, 2, solver);

    solver.post(ICF.arithm(a, "+", b, "<", 3));

    // START extra variables/constraints for guided improvement algorithm
    List<Constraint> stack = new ArrayList<>();
    IntVar lbA = VF.enumerated("lbA", -2, 2, solver);
    IntVar lbB = VF.enumerated("lbB", -2, 2, solver);
    BoolVar aSBetter = ICF.arithm(a, ">", lbA).reif();
    BoolVar bSBetter = ICF.arithm(b, ">", lbB).reif();
    solver.post(ICF.arithm(a, ">=", lbA));
    solver.post(ICF.arithm(b, ">=", lbB));
    Constraint strictlyBetter
            = LCF.or(aSBetter, bSBetter);
    // END extra variables/constraints for guided improvement algorithm

    while (solver.findSolution()) {
        int bestA;
        int bestB;

        push(strictlyBetter, stack, solver);

        do {
            bestA = a.getValue();
            bestB = b.getValue();

            push(ICF.arithm(lbA, ">=", bestA), stack, solver);
            push(ICF.arithm(lbB, ">=", bestB), stack, solver);

        } while (solver.nextSolution());

        popAll(stack, solver);

        push(ICF.arithm(a, "=", bestA), stack, solver);
        push(ICF.arithm(b, "=", bestB), stack, solver);
        push(ICF.arithm(lbA, "=", bestA), stack, solver);
        push(ICF.arithm(lbB, "=", bestB), stack, solver);

        solver.getEngine().flush();
        solver.getSearchLoop().reset();

        if (solver.findSolution()) {
            do {
                System.out.println("Found pareto optimal solution: " + a + ", " + b + ", " + c);
            } while (solver.nextSolution());
        }

        popAll(stack, solver);

        solver.getEngine().flush();
        solver.getSearchLoop().reset();

        solver.post(LCF.or(
                ICF.arithm(a, ">", bestA),
                ICF.arithm(b, ">", bestB)));
    }
}

private static void popAll(List<Constraint> stack, Solver solver) {
    assert solver.getSearchLoop().getCurrentDepth() == 0;
    for (Constraint constraint : stack) {
        solver.unpost(constraint);
    }
    stack.clear();
}

private static void push(Constraint constraint, List<Constraint> stack, Solver solver) {
    stack.add(constraint);
    solver.post(constraint);
}