chocoteam / choco-solver

An open-source Java library for Constraint Programming
http://choco-solver.org/
BSD 4-Clause "Original" or "Old" License
687 stars 137 forks source link

Optimize ParetoMaximizer.computeTightestPoint calculation #1026

Closed jsimomaa closed 1 year ago

jsimomaa commented 1 year ago

Currently unnecessary and expensive Stream.of()-streams are created and executed in ParetoMaximizer.computeTightestPoint() when computing the tightest point with an empty paretoFront-list:

Source:

    /**
     * Compute tightest point for objective i
     * i.e. the point that dominates DP_i and has the biggest obj_i
     *
     * @param i index of the variable
     */
    private void computeTightestPoint(int i) throws ContradictionException {
        int tightestPoint = Integer.MIN_VALUE;
        int[] dominatedPoint = computeDominatedPoint(i);
        for (int[] sol : paretoFront) {
            int dominates = dominates(sol, dominatedPoint, i);
            if (dominates > 0) {
                int currentPoint = dominates == 1 ? sol[i] : sol[i] + 1;
                if (tightestPoint < currentPoint) {
                    tightestPoint = currentPoint;
                }
            }
        }
        if (tightestPoint > Integer.MIN_VALUE) {
            objectives[i].updateLowerBound(tightestPoint, this);
        }
    }

    /**
     * Compute dominated point for objective i,
     * i.e. DP_i = (obj_1_max,...,obj_i_min,...,obj_m_max)
     *
     * @param i index of the variable
     * @return dominated point
     */
    private int[] computeDominatedPoint(int i) {
        int[] dp = Stream.of(objectives).mapToInt(IntVar::getUB).toArray();
        dp[i] = objectives[i].getLB();
        return dp;
    }