Bug? Huge variance in solving time

Tr1ple-F commented 10 months ago

I am using Google OR-Tools as interface in Java for the following problem:

I have a number of loans and want to split them into two similar size portfolios with certain restrictions on the terms for portfolio composition.

When I use SCIP as a solver it takes anywhere between 25s and 75s. However, when I replace SCIP with CBC it either takes 3-4s or 300s+, sometimes as much as 600s+. I am not familiar with the details of the CBC implementation but this just seems like a bug to me. Maybe someone smarter could take a look.

Appendix

Code For Test Case:

public static void testCase2(int COUNT, String solverS) {
        MPSolver solver = MPSolver.createSolver(solverS); // SCIP or CBC
        if (solver == null) {
            System.out.println("Could not create solver SCIP"); // or CBC
            return;
        }

        final Random rand = new Random();

        double[] outstanding = new double[COUNT]; // Generate portfolio items
        int[] originalTerm = new int[COUNT];

        for (int i = 0; i < COUNT; i++) {
            outstanding[i] = rand.nextDouble(8000, 15000);
            originalTerm[i] = rand.nextInt(12, 120);
        }

        System.out.println("Finished the number generation: " + LocalDateTime.now());

        MPVariable[] vIncludeA = solver.makeBoolVarArray(COUNT,  "include1"); // Include in Portfolio A
        MPVariable[] vIncludeB = solver.makeBoolVarArray(COUNT, "include2"); // Include in Portfolio B
        MPVariable vSumA = solver.makeNumVar(0, Double.POSITIVE_INFINITY, "sumA"); // Sum of A
        MPVariable vSumB = solver.makeNumVar(0, Double.POSITIVE_INFINITY, "sumB"); // Sum of B
        MPVariable vSum = solver.makeNumVar(0, Double.POSITIVE_INFINITY, "absoluteSum"); // Sum of A + B

        // All the sum must be equal
        MPConstraint sumConstraint = solver.makeConstraint(0.0, 0.0, "sumConstraint");
        MPConstraint sumConstraintB = solver.makeConstraint(0.0, 0.0, "sumConstraintB");
        MPConstraint sumConstraintA = solver.makeConstraint(0.0, 0.0, "sumConstraintA");
        for (int i = 0; i < COUNT; i++) {
            sumConstraintA.setCoefficient(vIncludeA[i], outstanding[i]);
            sumConstraintB.setCoefficient(vIncludeB[i], outstanding[i]);
            MPConstraint exclusionConstraint = solver.makeConstraint(0.0, 1.0); // Either in A or B not both
            exclusionConstraint.setCoefficient(vIncludeA[i], 1);
            exclusionConstraint.setCoefficient(vIncludeB[i], 1);
        }
        sumConstraint.setCoefficient(vSum, -1.0);
        sumConstraint.setCoefficient(vSumA, 1.0);
        sumConstraint.setCoefficient(vSumB, 1.0);
        sumConstraintA.setCoefficient(vSumA, -1.0);
        sumConstraintB.setCoefficient(vSumB, -1.0);

        MPConstraint termConstraintA = solver.makeConstraint(Double.NEGATIVE_INFINITY, 0.0, "termConstraintA");
        MPConstraint termConstraintB = solver.makeConstraint(Double.NEGATIVE_INFINITY, 0.0, "termConstraintB");
        for (int i = 0; i < COUNT; i++) {
            if (originalTerm[i] >= 60) {
                termConstraintA.setCoefficient(vIncludeA[i], outstanding[i]); // Constraints on the terms of the portfolio components
                termConstraintB.setCoefficient(vIncludeB[i], outstanding[i]);
            }
        }
        termConstraintA.setCoefficient(vSumA, -0.5);
        termConstraintB.setCoefficient(vSumB, -0.5); // Not more than 50%

        MPConstraint relativeSizeConstraintA = solver.makeConstraint(0, Double.POSITIVE_INFINITY, "sizeAC");
        MPConstraint relativeSizeConstraintB = solver.makeConstraint(0, Double.POSITIVE_INFINITY, "sizeBC");
        relativeSizeConstraintA.setCoefficient(vSumA, 1);
        relativeSizeConstraintA.setCoefficient(vSum, -0.4);
        relativeSizeConstraintB.setCoefficient(vSumB, 1);
        relativeSizeConstraintB.setCoefficient(vSum, -0.4); // Portfolios A and B should not be so different in size

        MPObjective objective = solver.objective();
        objective.setCoefficient(vSum, 1);
        objective.setMaximization();

        System.out.println("Finished the solver configuration: " + LocalDateTime.now());
        MPSolver.ResultStatus resultStatus = solver.solve();
        System.out.println("Finished the solve: " + LocalDateTime.now());
        System.out.println("Stats: " + resultStatus);
        System.out.println("SUM: " + vSum.solutionValue());
        System.out.println("SIZE A: " + vSumA.solutionValue());
        System.out.println("SIZE B: " + vSumB.solutionValue());
    }

Time measurements:

Finished the number generation: 2024-01-16T15:47:03.778043800
Finished the solver configuration: 2024-01-16T15:47:03.813040300
Finished the solve: 2024-01-16T15:47:08.507054800
Stats: OPTIMAL
SUM: 5.025857018782688E7
SIZE A: 2.010353448819065E7
SIZE B: 3.0155035699636232E7
---------------
 5000 Loans took CBC: 4s
---------------
Finished the number generation: 2024-01-16T15:47:08.520015600
Finished the solver configuration: 2024-01-16T15:47:08.549045800
Finished the solve: 2024-01-16T15:48:31.860702900
Stats: OPTIMAL
SUM: 5.022811846041961E7
SIZE A: 2.0363479124655835E7
SIZE B: 2.986463933576377E7
---------------
 5000 Loans took CBC: 83s
---------------
Finished the number generation: 2024-01-16T15:48:31.861709200
Finished the solver configuration: 2024-01-16T15:48:31.883703200
Finished the solve: 2024-01-16T15:48:35.197332500
Stats: OPTIMAL
SUM: 5.145792351803147E7
SIZE A: 2.05904169786819E7
SIZE B: 3.0867506539349575E7
---------------
 5000 Loans took CBC: 3s
---------------
Finished the number generation: 2024-01-16T15:48:35.198297700
Finished the solver configuration: 2024-01-16T15:48:35.220325200
Finished the solve: 2024-01-16T15:48:38.423293500
Stats: OPTIMAL
SUM: 5.113107335257511E7
SIZE A: 2.045370225037004E7
SIZE B: 3.0677371102205068E7
---------------
 5000 Loans took CBC: 3s
---------------
Finished the number generation: 2024-01-16T15:48:38.424293600
Finished the solver configuration: 2024-01-16T15:48:38.447292800
Finished the solve: 2024-01-16T15:54:21.907679600
Stats: OPTIMAL
SUM: 5.113939325738532E7
SIZE A: 2.0479953544921048E7
SIZE B: 3.0659439712464273E7
---------------
 5000 Loans took CBC: 343s
---------------
Finished the number generation: 2024-01-16T15:54:21.908682900
Finished the solver configuration: 2024-01-16T15:54:21.969716500
Finished the solve: 2024-01-16T15:54:24.793678600
Stats: OPTIMAL
SUM: 5.165261625303138E7
SIZE A: 2.0672268282356866E7
SIZE B: 3.098034797067451E7
---------------
 5000 Loans took CBC: 2s
---------------
Finished the number generation: 2024-01-16T15:54:24.794689200
Finished the solver configuration: 2024-01-16T15:54:24.813676400
Finished the solve: 2024-01-16T16:04:41.905072300
Stats: OPTIMAL
SUM: 5.240186523507737E7
SIZE A: 2.096111128050165E7
SIZE B: 3.1440753954575725E7
---------------
 5000 Loans took CBC: 617s
---------------
Finished the number generation: 2024-01-16T16:04:41.907079200
Finished the solver configuration: 2024-01-16T16:04:41.927102300
Finished the solve: 2024-01-16T16:04:46.698105800
Stats: OPTIMAL
SUM: 5.0913348527482584E7
SIZE A: 2.039093146101451E7
SIZE B: 3.0522417066468082E7
---------------
 5000 Loans took CBC: 4s
---------------
Finished the number generation: 2024-01-16T16:04:46.699075200
Finished the solver configuration: 2024-01-16T16:04:46.717075200
Finished the solve: 2024-01-16T16:04:49.912078800
Stats: OPTIMAL
SUM: 5.1145378039196454E7
SIZE A: 2.0474037406364582E7
SIZE B: 3.0671340632831875E7
---------------
 5000 Loans took CBC: 3s
---------------

Code to run test:

        Loader.loadNativeLibraries();
        double[] timeInScip = new double[10];
        double[] timeInCBC = new double[10];
        for (int i = 0; i < 10; i+=1) {
            long tA = System.currentTimeMillis();
            // testCase2(5000, "SCIP"); // uncomment to compare with SCIP
            long d1 = System.currentTimeMillis()-tA;
            System.out.println("---------------");
            System.out.println(" " + 5000 + " Loans took SCIP: " + d1/1000 + "s");
            System.out.println("---------------");
        }
        for (int i = 0; i < 10; i+=1) {
            long tA = System.currentTimeMillis();
            testCase2(5000, "CBC");
            long d1 = System.currentTimeMillis()-tA;
            System.out.println("---------------");
            System.out.println(" " + 5000 + " Loans took CBC: " + d1/1000 + "s");
            System.out.println("---------------");
        }

System Specs

SDK: Java 17.0.9 DEV: Dell XPS 15 9560, Win 10 Home MEM: 16 GB RAM CPU: Intel i7-7700 HQ @ 2.8 GHz, 4 cores GPU: Nvidia GeForce GTX 1050

jjhforrest commented 10 months ago

Not a bug - more a feature of integer programming. I don't know java or or-tools, which makes it more difficult to investigate. I wrote out an mps file from the long running Cbc run. This slightly changes the accuracy - but in this case made it harder for a code to solve. I killed the Cbc run and let Scip run overnight! It took ten hours and the maximum depth was over 4000! Modifying your code to give exactly the same model to both Scip and Cbc, I can see a variation of up to 5000 in value of objective due to tolerances etc. It is probably mainly the need to prove absolute optimality that make some runs take a long time. I don't have enough knowledge of or-tools to know how to pass parameters to code - but if you can pass allowable gap and multiplerootpasses

allowableGap was changed from 1e-12 to 10000 multipleRootPasses was changed from 0 to 4

even the long running problem from mps file solved in a few seconds (at the root node). The multiple parameter just runs all the heuristics four times with slightly different parameters - I chose 4 as they are normally done in parallel.

Tr1ple-F commented 10 months ago

Thank you so much! The performance now is absolutely fantastic! I have another question though: it there any other resource you could recommend aside the user guide (https://coin-or.github.io/Cbc/)? I could not find any reference to multipleRootPasses in that documentation.

jjhforrest commented 10 months ago

There is not much documentation for the more exotic commands. You can do - cbc allcommands all ?

which will list all commands to see more enter multiple??

or other ones on list e.g. pumptune??

coin-or / Cbc