Bug? Huge variance in CBC solver

[Tr1ple-F]

What version of OR-Tools and what language are you using?
Version: main
Language: Java

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
CBC

What operating system (Linux, Windows, ...) and version?
Windows 10 Home

What did you do?
I am modelling an portfolio selection problem with exclusionary boolean variables (see more details below) and have discovered a HUGE variance in solving time. Not sure if this is a bug or my own stupidity. I also opened a bug report on the CBC page here. Note: this issue is not present in the SCIP solver (more details below).

What did you expect to see
No specific expectations regarding time but some bounds on variance.

What did you see instead?
Solving time of 3s or 600s+.

Anything else we should know about your project / environment
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. I could understand if it takes 300s+ for everything but that some (random!) problems miraculously take just 3s while others are at over 5 minutes is too strange to believe. 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

[Mizux]

tips: using bullet issue is nicely rendered

• Bug? Huge variance in solving time coin-or/Cbc#633

[sschnug]

Without even looking at your data: this phenomenon is not uncommon and it is typically not considered a bug!
(it's basically an effect of NP-hardness)

• https://coral.ise.lehigh.edu/mip-2008/talks/danna.pdf
• Lodi, Andrea, and Andrea Tramontani. "Performance variability in mixed-integer programming." Theory driven by influential applications. INFORMS, 2013. 1-12.

You can try to dampen the effects by relaxing the MIPgap (don't run until proven to be within 0.01% or such but only 0.5%). It's much easier to get a 99.5% solution robustly compared to a 99.99% solution.

Two additional remarks:

• In 99.99% of all cases, asking or-tools for help is wrong as it's only a wrapper (but as mentioned: Cbc devs won't see this as bug either)
• It's not easy to explain, but i would claim that errors on modelling-side often effect in increased performance-variability
  • e.g. you think that those instances are equally hard, but there is some hidden phase-transition because of bugs or wrong assumptions
  • as two different solvers search differently (with lots of perf-variance), one might be more affected than the other