"Comparison method violates its general contract" - I cannot detect any intransitivity

Question

Edit: why I think this is not a duplicate: As biziclop wrote, the problem here is not intransitivity (a>b & b>c => a>c) as in the other problems mentioned here, but that the clause a>b => -(b>a) is violated, so it's a different problem.

I am receiving the following error message:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(Unknown Source)
at java.util.TimSort.mergeAt(Unknown Source)
at java.util.TimSort.mergeForceCollapse(Unknown Source)
at java.util.TimSort.sort(Unknown Source)
at java.util.Arrays.sort(Unknown Source)
at construct.Repair.regretRepair(Repair.java:101)
at lns.One.repaired(One.java:122)
at lns.One.segment(One.java:68)
at lns.One.lnsSolution(One.java:35)
at lns.All.lnsSolutions(All.java:22)
at barter.Genetic.initialPopulation(Genetic.java:36)
at barter.Genetic.run(Genetic.java:26)
at program.Main.main(Main.java:22)

This is where it happens:

Arrays.sort(regretProfits, new Comparator<RegretProfit>(){
            @Override
            public int compare(RegretProfit first, RegretProfit second){
                if (first.possibleRoutes <= 0){
                    if (second.possibleRoutes > 0){
                        return 1;
                    }
                    return 0;
                }                   
                if (first.possibleRoutes < solution.schedule.size() - kay + 1){
                    if (first.possibleRoutes < second.possibleRoutes){
                        return -1;
                    }
                    if (first.possibleRoutes > second.possibleRoutes){
                        return 1;
                    }
                    if (first.profit > second.profit){
                        return -1;
                    }
                    if (first.profit < second.profit){
                        return 1;
                    }
                }
                if (first.regret > second.regret){
                    return -1;
                }
                if (first.regret < second.regret){
                    return 1;
                }
                return 0;
            }
        ;});

And this is the class where the object RegretProfit is defined:

public class RegretProfit {
    public int[] order;
    public double regret;
    public double profit;
    public int possibleRoutes;
}

The error occurs only every few thousand iterations. I would be really thankful if anybody had some ideas what the problem might be. I've read that intransitivity can cause this exception but I really couldn't figure out where I possibly went wrong.

Solved it, thanks to biziclop!

Arrays.sort(regretProfits, new Comparator<RegretProfit>(){
            @Override
            public int compare(RegretProfit first, RegretProfit second){
                if (first.possibleRoutes <= 0 && second.possibleRoutes > 0){
                    return 1;
                }
                if (first.possibleRoutes <= 0 && second.possibleRoutes <= 0){
                    return 0;
                }
                if (first.possibleRoutes > 0 && second.possibleRoutes <= 0){
                    return -1;
                }
                if (first.possibleRoutes < solution.schedule.size() - kay + 1 || second.possibleRoutes < solution.schedule.size() - kay + 1){
                    if (first.possibleRoutes < second.possibleRoutes){
                        return -1;
                    }
                    if (first.possibleRoutes > second.possibleRoutes){
                        return 1;
                    }
                    if (first.profit > second.profit){
                        return -1;
                    }
                    if (first.profit < second.profit){
                        return 1;
                    }
                }
                if (first.regret > second.regret){
                    return -1;
                }
                if (first.regret < second.regret){
                    return 1;
                }
                return 0;
            }
        ;});

Answer 1

It isn't transitivity that is the key problem here, the part of the contract violated is sgn(compare(x, y)) == -sgn(compare(y, x))

If you have these records for example:

 first.possibleRoutes = -1; first.regret = 1
 second.possibleRoutes = 1; second.regret = -1

Your comparator returns 1. But if you swap them:

 first.possibleRoutes = 1; first.regret = -1
 second.possibleRoutes = -1; second.regret = 1

Your comparator still possibly returns 1.

Looking at the code there are two suspicious, non-symmetric constructs:

            if (first.possibleRoutes <= 0){
                if (second.possibleRoutes > 0){
                    return 1;
                }
                return 0;
            } 

Here there's no matching -1 return if first and second are reversed. You also treat every item with possibleRoutes <= 0 as equal, which is probably not what you want.

            if (first.possibleRoutes < solution.schedule.size() - kay + 1){

Here you enter a branch based purely on the value of first, which means this branch can also potentially lead to sgn(compare(x, y)) != -sgn(compare(y, x)).

Of course it is possible that under the additional constraints of the full system the two problems cancel each other out (clearly they don't in this case), but it's a very brittle way of designing comparators and I'd advise you to make sure that all branches are symmetrical. It makes it a lot easier to reason about the correctness of your code.