分支定界法求解整数线性规划的变量选择与跨平台求解器问题

一、变量选择的核心困境 #

我用分支定界法求解整数线性规划问题，先计算松弛问题最优解，得到变量值：

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

目标函数为最大化：

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

已知OR-Tools给出的最终最优解是：

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

常规分支定界会选择变量添加整数约束分支，但这里遇到问题：选哪个变量分支才能找到最优解？

我最初选了小数部分最大的x1（84.949...），分支约束为：

左节点: x1 <= 84
右节点: x1 >= 85

但后续计算无法找到更优解，算法提前终止于非最优解。但调整初始松弛问题中x1、x2的顺序后，得到不同松弛解，此时按最大小数部分选变量分支，最终能找到最优解。

请问是否存在优化的变量选择算法，能引导求解过程趋近并找到最优解？初始松弛问题的变量顺序会影响求解方向和结果，这让我困惑。

另外，我需要一款能在iOS上运行的原生C#求解器：Google-OR-Tools无法适配iOS；MathNet.Numerics不确定是否支持iOS，也不清楚如何用它求解混合整数规划（MIP）问题。

二、补充：TwoPhaseSimplexSolver求解异常问题 #

我在分支定界中使用TwoPhaseSimplexSolver，针对以下数组求解得到非最优解：

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 };

但将等价约束输入在线两阶段单纯形求解器时，能得到最优解：x1=85, x2=80.8182, x3=0, x4=35.9917，约束内容如下：

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

奇怪的是，在isOptimal(...)方法的数组x中能得到预期的最优解值，但以下验证代码失败：

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

原因是value2数值过大，导致abs(value - value2)超出EPSILON范围，不清楚为何会出现这种情况。

三、自定义变量选择策略对比 #

1. HighestFractionVariableSelectionStrategy #

该策略能得到更优的目标函数值，且性能略优于后者：

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));
        }

        // 过滤已为整数的变量
        var solutionForVariablesList = solutionValues.Where(x => (int)x != x).ToList();

        // 按小数部分从大到小排序
        solutionForVariablesList.Sort(fractionalPartComparer);


        // 如果至少有2个变量，选择整数部分更大的那个（比如7.5和6.8选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];
        }

        // 找到对应整数部分最大且小数部分最大的变量索引
        for (int i = 0; i < solutionValues.Length; i++)
        {
            if ((int)solutionValues[i] == value)
            {
                indexOfSelectedVariable = i;
                break;
            }
        }

        return indexOfSelectedVariable;
    }

    /// <summary>
    /// 按变量小数部分排序的比较器，小数部分越大排序越靠前
    /// </summary>
    private class FractionalPartComparer : Comparer<double>
    {
        public override int Compare(double value1, double value2)
        {
            double fractionalPart1 = value1 - Math.Floor(value1);
            double fractionalPart2 = value2 - Math.Floor(value2);

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

            return 0;
        }
    }
}

2. FarthestFromIntegerSelectionStrategy #

该策略性能稍慢，得到的目标函数值优度更低：

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>
    /// 找到数组中距离整数最远的值（最大不可行性规则，迫使分支树早期产生更大变化）
    /// </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;
    }
}

内容的提问来源于stack exchange，提问作者OXO