Solving Linear Program with Branch-and-Bound

Question

I am trying to solve a linear integer programming problem with Branch-and-Bound. Therefore, I calculated the optimal solution (relaxation) first and got 4 values:

x1: 84.949144123197641
x2: 80.6791757549221
x3: 0
x4: 38.459016105691269

My Target Function should be maximized and is:

Z = 0.236x1 + 0.485x2 + 0.679x3 + 0.863x4

I know from using the OR-Tools-Solver that for my problem there is an optimal solution in the End with variable values like this:

x1: 84
x2: 144
x3: 8
x4: 66

Normally, in a Branch-and-Bound, I would branch to the left and to the right and add new constraints with integer bounds, like <= and >= Constraints and the corresponding Integer boundaries.

Here, it was the Question of what Variable to select and if there is a solution for this choice in the end when optimizing further like this.

First of all, I took the variable with the largest fraction which was

x1: 84.949144123197641

to optimize with the following additional constraints:

Left node: x1 <= 84
Right node: x1 >= 85

But, when I do this and calculate these nodes like this with additional constraints it turns out after some steps that there are no further optimal solutions anymore and the algorithm terminates with less optimal solutions.

When I changed the order of my x1 ... x2 for the initial relaxation, I got other results for x1 ... x2 which, when optimized with the variable selection of the largest fraction, I came to the optimal solution.

Is there an algorithm that optimizes variable selection so that it brings my solutions more in the direction of the optimal solution and it can find the optimal solution in the end?

For me, it turns out that calculating the relaxation determines where further optimizations go so that it is based on the order of my x1 ... x4 for the initial matrix in which direction it looks further and if it can find the optimal solution.

Another question would be if there is a native C# Solver I can use for the calculation which can run on iOS in the end. Google-OR-Tools is great but does not provide the possibility to run it on iOS. MathNet.Numerics, I don't know if it can be used to run on iOS. Additionally, I don't know how I could calculate a MIP with it.

===== Additional information =======

I used the following TwoPhaseSimplexSolver within my branch and bound and get to a non-optimal solution for the following arrays:

https://algs4.cs.princeton.edu/65reductions/TwoPhaseSimplex.java.html

double[,] A = {
    {  0.09,  0.31,  0.21,  0.841 },
    { 0.069,  0.17,  0.02,  0.011 },
    {  0.52, 0.005, 0.006,  0.011 },
    {    -1,     0,     0,      0 },
    {     1,     0,     0,      0 },
    {     0,    -1,     0,      0 },
    {     0,     1,     0,      0 },
    {     0,     0,    -1,      0 },
    {     0,     0,     1,      0 },
    {     0,     0,     0,     -1 },
    {     0,     0,     0,      1 },
    {-0.679,-0.485,-0.236,-0.863 },
    { 0.679, 0.485, 0.236, 0.863 },
    {    -1,     0,     0,      0 }
};

double[] b = { 65, 20, 45, -60, 120, 0, 100, 0, 150, -1, 100, 0, 130, -85 };

double[] c = { 0.679, 0.485, 0.236, 0.863 };

But when I input the following constraints in the TwoPhase-Method-Solver on https://cbom.atozmath.com/CBOM/Simplex.aspx?q=tp I do get an optimal solution with the following results:

x1=85, x2=80.8182, x3=0, x4=35.9917

This can be copied and pasted like that to the solver in the link above:

max z = 0.679x1 + 0.485x2 + 0.236x3 + 0.863x4 
subject to
0.09x1 + 0.31x2 + 0.21x3 + 0.841x4 <= 65
0.069x1 + 0.17x2 + 0.02x3 + 0.011x4 <= 20
0.52x1 + 0.005x2 + 0.006x3 + 0.011x4 <= 45
x1 >= 60
x1 <= 120
x2 >= 0
x2 <= 100
x3 >= 0
x3 <= 150
x4 >= 1
x4 <= 100
0.679x1 + 0.485x2 + 0.236x3 + 0.863x4 >= 0
0.679x1 + 0.485x2 + 0.236x3 + 0.863x4 <= 130
x1 >= 85
and x1,x2,x3,x4 >= 0

Strangely enough, I do get the optimal solution values in array x of method isOptimal(...), but the check

if (Math.abs(value - value1) > EPSILON || Math.abs(value - value2) > EPSILON) { 
    StdOut.println("value = " + value + ", cx = " + value1 + ", yb = " + value2); 
    return false;
}

fails as value2 is really large and so the abs(value - value2) is not close enough to the EPSILON. But, I don't know why and why it is actually that far away even if we have the expected values in x

=========== Variable Selection ===============

When I use a Variable Selection Strategy like this, I can get better target function values with it and Performance is slightly better than with the FarthestFromIntegerSelectionStrategy

public class HighestFractionVariableSelectionStrategy : IVariableSelectionStrategy
{
    private readonly FractionalPartComparer fractionalPartComparer;

    public HighestFractionVariableSelectionStrategy()
    {
        fractionalPartComparer = new FractionalPartComparer();
    }

    /// <inheritdoc />
    public int SelectVariable(double[] solutionValues)
    {
        if (solutionValues == null)
        {
            throw new ArgumentNullException(nameof(solutionValues));
        }

        // Filter variables that are not an integer already
        var solutionForVariablesList = solutionValues.Where(x => (int)x != x).ToList();

        // Sort by highest fractional part
        solutionForVariablesList.Sort(fractionalPartComparer);


        // If we have at least 2 solutions in the list sorted by fractional part
        // we take the one with the highest integer value: e.g. 7.5 and 6.8 will return
        // the index of the variable with value 7.5
        int indexOfSelectedVariable = -1;
        int value = -1;
        double[] solutionsSortedByHighestFraction = solutionForVariablesList.ToArray();
        if (solutionsSortedByHighestFraction.Length >= 2)
        {
            var valueVariable1 = (int)solutionsSortedByHighestFraction[0];
            var valueVariable2 = (int)solutionsSortedByHighestFraction[1];

            value = valueVariable1 > valueVariable2 ? valueVariable1 : valueVariable2;
        }
        else
        {
            value = (int)solutionsSortedByHighestFraction[0];
        }

        // Find the index of the Variable with the highest integer and highest fractional part
        for (int i = 0; i < solutionValues.Length; i++)
        {
            if ((int)solutionValues[i] == value)
            {
                indexOfSelectedVariable = i;
                break;
            }
        }

        return indexOfSelectedVariable;
    }

    /// <summary>
    /// Comparer that will be used to sort the different Variables to select from.
    /// The Comparer will sort based on the Fractional Part of the Variables.
    /// The higher the factional part the lower the ranking.
    /// </summary>
    private class FractionalPartComparer : Comparer<double>
    {
        public override int Compare(double value1, double value2)
        {
            // Sort by highest fractional Part
            double fractionalPart1 = value1 - Math.Floor(value1);
            double fractionalPart2 = value2 - Math.Floor(value2);

            if (fractionalPart1 > fractionalPart2) return -1;
            if (fractionalPart1 < fractionalPart2) return 1;

            return 0;
        }
    }
}

Slightly slower, but provides less optimal target function values

public class FarthestFromIntegerSelectionStrategy : IVariableSelectionStrategy
{
    /// <inheritdoc />
    public int SelectVariable(double[] solutionValues)
    {
        if (solutionValues == null)
        {
            throw new ArgumentNullException(nameof(solutionValues));
        }

        var valueFarthestFromInteger = FindFarthestFromInteger(solutionValues);
        int index = Array.IndexOf(solutionValues, valueFarthestFromInteger);

        return index;
    }

    /// <summary>
    /// Determines the value in the given array that is farthest from an integer value
    /// 
    /// The maximum infeasibility rule chooses the variable with the value furtherest from an integer.
    /// It forces larger changes earlier in the tree of a Branch-and-Bound algorithm. 
    /// </summary>
    /// <param name="values"></param>
    /// <returns></returns>
    private static double FindFarthestFromInteger(double[] values)
    {
        double farthest = values[0];
        double distance = Math.Abs(values[0] - Math.Round(values[0]));

        for (int i = 1; i < values.Length; i++)
        {
            double currentDistance = Math.Abs(values[i] - Math.Round(values[i]));

            if (currentDistance > distance)
            {
                distance = currentDistance;
                farthest = values[i];
            }
        }

        return farthest;
    }
}