Does the square of the sum of variables decrease the performance?

[priamoryki]

Hi,

I've created a model based on this example for scheduling nurses according to shift needs. However, the number of scheduled nurses varies dynamically based on the demand and scheduling costs.

To implement this, I use an objective function in which I have added the following term:
$-(1 - \frac{{\text{nurses in shift}}}{{\text{nurses needed}}})^2$
The parabolic shape helps avoid potential issues with an infinite number of nurses in a shift.

OR-Tools quickly finds a good solution and then attempts to prove its optimality.
Is the slowdown related to the square term in the objective function? Or is it due to an incorrect implementation?

Additionally, are there any other options for dynamically determining the number of scheduled nurses?

Here is my code:

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.IntStream;

/**
 * Nurses problem.
 */
public class ScheduleRequestsSat {
    private static final int NURSES_OVER_LIMIT_ACCEPTED_MULTIPLIER = 100;
    private static final int uniformityCoeff = 400;

    public static void main(String[] args) {
        Random random = new Random();
        random.setSeed(1000);
        Loader.loadNativeLibraries();
        final int numNurses = 150;
        final int numShifts = 4;

        final int[] allNurses = IntStream.range(0, numNurses).toArray();
        final int[] allShifts = IntStream.range(0, numShifts).toArray();

        final int[][] nursesCosts = new int[numNurses][numShifts];
        for (int n : allNurses) {
            for (int s : allShifts) {
                nursesCosts[n][s] = random.nextInt(100_000);
            }
        }

        final int[] nursesNeed = new int[]{90, 90, 90, 90};

        // Creates the model.
        CpModel model = new CpModel();

        // Creates shift variables.
        // shifts[(n, s)]: nurse 'n' works shift 's'.
        Literal[][] shifts = new Literal[numNurses][numShifts];
        for (int n : allNurses) {
            for (int s : allShifts) {
                shifts[n][s] = model.newBoolVar("shifts_n" + n + "s" + s);
            }
        }

        // Each nurse works at most one shift.
        for (int n : allNurses) {
            List<Literal> work = new ArrayList<>();
            for (int s : allShifts) {
                work.add(shifts[n][s]);
            }
            model.addAtMostOne(work);
        }

        LinearExprBuilder obj = LinearExpr.newBuilder();
        for (int n : allNurses) {
            for (int s : allShifts) {
                obj.addTerm(shifts[n][s], nursesCosts[n][s]);
            }
        }

        // Dynamic nurses need.
        for (int s : allShifts) {
            int nursesNeedCount = nursesNeed[s];

            Literal[] nurses = Arrays.stream(shifts)
                    .map(n -> n[s])
                    .toArray(Literal[]::new);

            LinearExpr nursesSum = LinearExpr.sum(nurses);

            // dividedWeight = sum * uniformityCoeff / nursesNeedCount
            long coeff = uniformityCoeff / nursesNeedCount;
            LinearExpr dividedWeight = LinearExpr.term(nursesSum, coeff);

            // shiftsWeight = uniformityCoeff - sum * uniformityCoeff / employeeNeedCount
            String shiftsWeightName = String.format("shiftsWeight_s%d", s);
            long lb = -NURSES_OVER_LIMIT_ACCEPTED_MULTIPLIER * uniformityCoeff;
            IntVar shiftsWeight = model.newIntVar(lb, uniformityCoeff, shiftsWeightName);
            model.addEquality(
                    shiftsWeight, LinearExpr.affine(dividedWeight, -1, uniformityCoeff)
            );

            // sqrWeight = (uniformityCoeff - sum * uniformityCoeff / nursesNeedCount) ^ 2
            String sqrWeightName = String.format("sqrShifts_s%d", s);
            long ubMultiplier = NURSES_OVER_LIMIT_ACCEPTED_MULTIPLIER * NURSES_OVER_LIMIT_ACCEPTED_MULTIPLIER;
            IntVar sqrWeight = model.newIntVar(0, ubMultiplier * uniformityCoeff * uniformityCoeff, sqrWeightName);
            model.addMultiplicationEquality(
                    sqrWeight, shiftsWeight, shiftsWeight
            );

            obj.addTerm(sqrWeight, -1);
        }

        model.maximize(obj);

        // Creates a solver and solves the model.
        CpSolver solver = new CpSolver();
        solver.getParameters().setMaxTimeInSeconds(5);
        solver.getParameters().setLogSearchProgress(true);

        CpSolverStatus status = solver.solve(model);
        if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
            System.out.printf("Solution:%n");
            for (int n : allNurses) {
                for (int s : allShifts) {
                    if (solver.booleanValue(shifts[n][s])) {
                        System.out.printf("  Nurse %d works shift %d.%n", n, s);
                    }
                }
            }
        } else {
            System.out.printf("No solution found!");
        }
        // Statistics.
        System.out.println("Statistics");
        System.out.printf("  conflicts: %d%n", solver.numConflicts());
        System.out.printf("  branches : %d%n", solver.numBranches());
        System.out.printf("  wall time: %f s%n", solver.wallTime());
    }

    private ScheduleRequestsSat() {
    }
}

[lperron]

you should simplify your equations. division + square is expensive and has poor propagation,relaxation.

instead of -(1 - n/k)^2, start by changing to -(k - n)^2, then you can scale the term of the objective.
You may need to use DoubleLinearExpr instead of LinearExpr, or scale everything up to integers.

[priamoryki]

As you can see I've done scaling in the code, and there is no division here, only multiplication. However, the square operation still seems to be quite expensive.

Do you happen to know any other options to implement what I want?

[lperron]

how many workers are you using ? Should be visible in the log. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le lun. 15 juil. 2024 à 16:25, Pavel Lymar ***@***.***> a écrit :

…

As you can see I've done scaling in the code, and there is no division here, only multiplication. However, the square operation still seems to be quite expensive. Do you happen to know any other options to implement what I want? — Reply to this email directly, view it on GitHub <#4314 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3MMUE7VRB6VQTQ645LZMPLUNAVCNFSM6AAAAABK4QNMPGVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTAMBVGE4DINY> . You are receiving this because you commented.Message ID: ***@***.***>

[priamoryki]

Log says Starting search at 0.03s with 16 workers.

[lperron]

OK, reasonable. Can you send me the model ? Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le lun. 15 juil. 2024 à 16:45, Pavel Lymar ***@***.***> a écrit :

…

Log says Starting search at 0.03s with 16 workers. — Reply to this email directly, view it on GitHub <#4314 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3L4QW4BX43YRA4CFMTZMPOCNAVCNFSM6AAAAABK4QNMPGVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTAMBVGIYTGNA> . You are receiving this because you commented.Message ID: ***@***.***>

[priamoryki]

The model is provided in the original thread

[orwant]

For the record, Google provides a workforce scheduling API.

[lperron]

yes, no. This is the code, not the model.
The model is a stand alone file that is easy to run..

model.exportToFile("issue4314.pb.txt");

I will generate it.