Constraint Programming Bin Packing example

Task2Sessions.java

package com.ajira.chocosolver;

import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solution;
import org.chocosolver.solver.search.loop.monitors.CPProfiler;
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.solver.variables.Variable;

import java.io.IOException;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Task2Sessions {

    static class Task {
        public final String taskName;
        public final Integer durationMinutes;
        public final Integer id;
        public Integer sessionIndex;

        public Task(String taskName, Integer durationMinutes, Integer id) {
            this.taskName = taskName;
            this.durationMinutes = durationMinutes;
            this.id = id;
        }

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Task{");
            sb.append("taskName='").append(taskName).append('\'');
            sb.append(", durationMinutes=").append(durationMinutes);
            sb.append(", id=").append(id);
            sb.append(", sessionIndex=").append(sessionIndex);
            sb.append('}');
            return sb.toString();
        }
    }

    private List<Task> generateTasks(int count) {
        Random random = new Random(System.currentTimeMillis());
        return IntStream.range(1, count + 1)
                .mapToObj(i -> new Task("T" + i, random.nextInt(15) + 1, i))
                .collect(Collectors.toList());
    }

    private void printSessionSummary(Map<Integer, List<Task>> sessions) {
        String sessionFormat = "| %-15d | %-12d | %-17d | %-65s |%n";
        System.out.println("----------------------------SESSIONS--------------------------");
        System.out.format("+-----------------+--------------+-------------------+--------------------------------------------------------%n");
        System.out.format("| Session Index   | Task Count   |  Duration(Minutes)| Tasks                                                  |%n");
        System.out.format("+-----------------+--------------+-------------------+--------------------------------------------------------%n");
        sessions.entrySet().forEach(sessionData -> {
            System.out.format(sessionFormat, sessionData.getKey(), sessionData.getValue().size(),
                    sessionData.getValue().stream().mapToInt(t -> t.durationMinutes).sum(),
                    sessionData.getValue().stream().map(t -> t.taskName + '=' + t.durationMinutes)
                            .collect(Collectors.joining(",")));
        });
        System.out.format("+-----------------+--------------+-------------------+--------------------------------------------------------%n");
    }


    private void group2Sessions(int taskCount) {
        Model model = new Model("Tasks to Sessions grouping model");
        List<Task> tasks = generateTasks(30);
        String taskFormat = "| %-15s | %-4d |%-18d|%n";
        System.out.println("-------------------TASKS---------------------");
        System.out.format("+-----------------+------+-------------------%n");
        System.out.format("| Task name       | ID   | Duration(Minutes)|%n");
        System.out.format("+-----------------+------+-------------------%n");
        tasks.forEach(t -> System.out.format(taskFormat, t.taskName, t.id, t.durationMinutes));
        System.out.format("+-----------------+------+-------------------%n");
        int maxSessionCount = taskCount;
        int minSessionTimeMinutes = 0;
        int maxSessionTimeMinutes = 60;
        IntVar[] taskVars = tasks.stream().map(t ->
                model.intVar(t.taskName, 0, maxSessionCount, false))
                .toArray(IntVar[]::new);
        IntVar[] sessionVars =  IntStream.range(0, maxSessionCount)
                .mapToObj(Integer::new)
                .map(i -> model.intVar("Session:" + i, minSessionTimeMinutes, maxSessionTimeMinutes, true))
                .toArray(IntVar[]::new);
        Map<String, IntVar> taskVarMap = Arrays.stream(taskVars)
                .collect(Collectors.toMap(Variable::getName, Function.identity()));
        IntVar sessionCountVar = model.intVar("sessionCount", 0, maxSessionCount);
        model.max(sessionCountVar, taskVars).post();
        model.binPacking(taskVars, tasks.stream().mapToInt(t -> t.durationMinutes).toArray(), sessionVars, 0).post();

        model.setObjective(Model.MINIMIZE, sessionCountVar);
        model.getSolver().limitTime(5 * 60 * 1000);
        Solution solution = new Solution(model);
        //set run time limit to 2 minutes for this solver
        //dont find more than 500 solutions
        model.getSolver().limitSolution(500);
        while (model.getSolver().solve()) {
            solution.record();
        }

        boolean solved = model.getSolver().getSolutionCount() > 0;

        if(solved) {
            tasks.forEach(t -> t.sessionIndex = solution.getIntVal(taskVarMap.get(t.taskName)));
            Map<Integer, List<Task>> grouped = tasks.stream().collect(Collectors.groupingBy(t -> t.sessionIndex));
            System.out.println();
            System.out.println();
            this.printSessionSummary(grouped);
        } else {
            System.out.println("No solution found");
        }
    }

    public static void main(String[] args) {
        new Task2Sessions().group2Sessions(30);
    }
}