Choco Solver



The Pareto Front in Choco Solver 4.0

Through this tutorial, we will focus on the optimization of two variables using the Pareto Front.

It consists on simultaneously optimize two incomparable variables.

We will use the Knapsack constraint, two optimize two decision variables : the quantity of glucose, and the quantity of lipids.

            
import org.chocosolver.solver.Model;
import org.chocosolver.solver.ResolutionPolicy;
import org.chocosolver.solver.Solution;
import org.chocosolver.solver.objective.ParetoOptimizer;
import org.chocosolver.solver.variables.IntVar;

import java.util.List;

public class Pareto {

    public static void main(String[] args) {
        // We handle 4 types of food, described below
        int[] nbItems = new int[]{5, 2, 6, 7}; // number of items for each type
        int[] weights = new int[]{5, 8, 7, 8}; // weight of an item for each type
        int[] lipids  = new int[]{5, 9, 8, 1}; // quantity of lipids of the item
        int[] glucose = new int[]{9, 5, 7, 32}; // quantity of glucose of the item

        Model model = new Model("ParetoKnapsack");

        // For each type, we create a variable for the number of occurrences
        IntVar[] occurrences = new IntVar[nbItems.length];
        for (int i = 0; i < nbItems.length; i++) {
            occurrences[i] = model.intVar(0, nbItems[i]);
        }

        // Total weight of the solution.
        IntVar weight = model.intVar(0, 80);
        // Total of lipids
        IntVar totalLipids = model.intVar(0, 200);
        // Total of glucose
        IntVar totalGlucose = model.intVar(0, 200);

        // We add two knapsack constraints to the solver
        // Beware : call the post() method to save it
        model.knapsack(occurrences, weight, totalLipids, weights, lipids).post();
        model.knapsack(occurrences, weight, totalGlucose, weights, glucose).post();

		// Optimise independently two variables using the Pareto optimizer
        List<Solution> solutions = model.getSolver().findParetoFront(new IntVar[]{totalLipids, totalGlucose},true);
        for (Solution solution : solutions) {
            System.out.println("-----------------------------------");
            System.out.println("W: " + solution.getIntVal(weight) + "\t G:" + solution.getIntVal(totalGlucose) + "\t L: " + solution.getIntVal(totalLipids));
            System.out.println("Strawberry jam: " + solution.getIntVal(occurrences[0]));
            System.out.println("Bananas: " + solution.getIntVal(occurrences[1]));
            System.out.println("Apples: " + solution.getIntVal(occurrences[2]));
            System.out.println("Honey: " + solution.getIntVal(occurrences[3]));
        }
        System.out.println("There are "+solutions.size()+" Pareto-optimal solutions");
    }
}
            
        

Once the main() method executed, a set of incomparable solutions is output. It is called the Pareto Front.

Le front de Pareto : comparaison du total de lipides et de glucose

This chart represents all the solutions found by the Pareto Front, considering two decision variables to maximize. It doesn't exist any point such that its coordinates are better than any other point of the cloud.


3D generalisation

We now would like, in addition to maximising the total of glucose and lipids, minimize the total weight. Choco permits such an optimization, which we will do as follows :

        
// To minimize the weight in the same time, we take its opposite by using the choco's minus view
ParetoOptimizer pareto = new ParetoOptimizer(ResolutionPolicy.MAXIMIZE, new IntVar[]{totalLipids, totalGlucose, model.intMinusView(weight)});
model.getSolver().plugMonitor(pareto);
        
    
3D Front Pareto

The Pareto Fronts becomes more complex : it is composed of 485 Pareto optimal solutions. We can represent it using a 3D surface.