我如何在c#中模拟Microsoft Excel的Solver功能(GRG非线性)?

I have a non-linear optimization problem with constraints. It can be solved in Microsoft Excel with the Solver add-in, but I am having trouble replicating that in C#.

我有一个有约束的非线性最优化问题。它可以在Microsoft Excel中使用Solver插件解决，但是我在c#中无法复制它。

My problem is shown in the following spreadsheet. I am solving the classic A x = b problem but with the caveat that all components of x must be non-negative. So instead of using standard linear algebra I use Solver with the non-negative constraint, minimizing the sum of the squared differences, and get a reasonable solution. I have tried to replicate this in C# using either Microsoft Solver Foundation or Solver SDK. However I can't seem to get anywhere with them because with MSF I can't figure out how to define the goal and with Solver SDK I always get back status "optimal" and a solution of all 0s which is definitely not even a local minimum.

我的问题显示在下面的电子表格中。我解的是经典x = b的问题，但需要注意的是，x的所有分量都必须是非负的。因此，我不使用标准线性代数，而是使用非负约束的求解方法，最小化平方差的和，得到一个合理的解。我已经尝试在c#中使用Microsoft Solver Foundation或Solver SDK来复制它。然而，我似乎无法与他们取得任何联系，因为MSF我不知道如何定义目标和Solver SDK，我总是能回到状态“最优”和所有0的解决方案，这绝对不是一个局部最小值。

Here is my code for Solver SDK:

这是我的Solver SDK代码:

static double[][] A = new double[][] { new double[] { 1, 0, 0, 0, 0 }, new double[] { 0.760652602, 1, 0, 0, 0 }, new double[] { 0.373419404, 0.760537565, 1, 0, 0 }, new double[] { 0.136996731, 0.373331934, 0.760422587, 1, 0 }, new double[] { 0.040625222, 0.136953801, 0.373244464, 0.76030755, 1 } };
static double[][] b = new double[][] { new double[] { 2017159 }, new double[] { 1609660 }, new double[] { 837732.8125 }, new double[] { 330977.3125 }, new double[] { 87528.38281 } };

static void Main(string[] args)
{
    using(Problem problem = new Problem(Solver_Type.Minimize, 5, 0))
    {
        problem.VarDecision.LowerBound.Array = new double[] { 0.0, 0.0, 0.0, 0.0, 0.0 };
        problem.VarDecision.UpperBound.Array = new double[] { Constants.PINF, Constants.PINF, Constants.PINF, Constants.PINF, Constants.PINF };

        problem.Evaluators[Eval_Type.Function].OnEvaluate += new EvaluateEventHandler(SumOfSquaredErrors);

        problem.ProblemType = Problem_Type.OptNLP;

        problem.Solver.Optimize();

        Optimize_Status status = problem.Solver.OptimizeStatus;

        Console.WriteLine(status.ToString());
        foreach(double x in problem.VarDecision.FinalValue.Array)
        {
            Console.WriteLine(x);
        }
    }
}

static Engine_Action SumOfSquaredErrors(Evaluator evaluator)
{
    double[][] x = new double[evaluator.Problem.Variables[0].Value.Array.Length][];
    for(int i = 0; i < x.Length; i++)
    {
        x[i] = new double[1] { evaluator.Problem.Variables[0].Value.Array[i] };
    }

    double[][] b_calculated = MatrixMultiply(A, x);

    double sum_sq = 0.0;
    for(int i = 0; i < b_calculated.Length; i++)
    {
        sum_sq += Math.Pow(b_calculated[i][0] - b[i][0], 2);
    }
    evaluator.Problem.FcnObjective.Value[0] = sum_sq;

    return Engine_Action.Continue;
}

static double[][] MatrixMultiply(double[][] left, double[][] right)
{
    if(left[0].Length != right.Length)
    {
        throw new ArgumentException();
    }

    double[][] sum = new double[left.Length][];
    for(int i = sum.GetLowerBound(0); i <= sum.GetUpperBound(0); i++)
    {
        sum[i] = new double[right[i].Length];
    }

    for(int i = 0; i < sum.Length; i++)
    {
        for(int j = 0; j < sum[0].Length; j++)
        {
            for(int k = 0; k < right.Length; k++)
            {
                sum[i][j] += left[i][k] * right[k][j];
            }
        }
    }

    return sum;
}

I don't have any code for Microsoft Solver Foundation because I don't think the goal function can be written in a single line and it doesn't allow for delegates like Solver SDK does.

我没有任何微软Solver基金会的代码，因为我不认为目标函数可以写在一行中，也不允许像Solver SDK这样的委托。

1 个解决方案

#1

One alternative would be to formulate this as an LP problem:

另一种选择是将此作为LP问题:

minimize sum of the elements in x

最小化x中元素的和。

subject to Ax >= b

服从Ax >= b。

This should be fairly simple to formulate using Solver Foundation, based on one of the LP samples.

这应该相当简单，根据一个LP样本，用Solver基金会来制定。

UPDATE JULY 5

更新7月5日

The above approach also looks overly complex, but maybe this is due to the Frontline Solver API. Using Microsoft Solver Foundation, and minimizing the sum of squared differences, the following program:

上面的方法看起来也过于复杂，但这可能是由于前线Solver API的缘故。使用Microsoft Solver Foundation，并最小化平方差异的和，下面的程序:

private static void Main(string[] args)
{
    var solver = SolverContext.GetContext();
    var model = solver.CreateModel();

    var A = new[,]
        {
            { 1, 0, 0, 0, 0 }, 
            { 0.760652602, 1, 0, 0, 0 }, 
            { 0.373419404, 0.760537565, 1, 0, 0 },
            { 0.136996731, 0.373331934, 0.760422587, 1, 0 },
            { 0.040625222, 0.136953801, 0.373244464, 0.76030755, 1 }
        };
    var b = new[] { 2017159, 1609660, 837732.8125, 330977.3125, 87528.38281 };

    var n = A.GetLength(1);
    var x = new Decision[n];
    for (var i = 0; i < n; ++i)
        model.AddDecision(x[i] = new Decision(Domain.RealNonnegative, null));

    // START NLP SECTION
    var m = A.GetLength(0);
    Term goal = 0.0;
    for (var j = 0; j < m; ++j)
    {
        Term Ax = 0.0;
        for (var i = 0; i < n; ++i) Ax += A[j, i] * x[i];
        goal += Model.Power(Ax - b[j], 2.0);
    }
    model.AddGoal(null, GoalKind.Minimize, goal);
    // END NLP SECTION

    var solution = solver.Solve();
    Console.WriteLine("f = {0}", solution.Goals.First().ToDouble());
    for (var i = 0; i < n; ++i) Console.WriteLine("x[{0}] = {1}", i, x[i].GetDouble());
}

generates the following solution, which should be in line with the solution from the linked Excel sheet:

生成以下解决方案，该解决方案应与连接的Excel表的解决方案一致:

f = 254184688.179922
x[0] = 2017027.31820845
x[1] = 76226.6063397686
x[2] = 26007.3375581303
x[3] = 1.00650383558278E-07
x[4] = 4.18546775823669E-09

If I am not mistaken, unlike GRG, Solver Foundation cannot support general non-linear constraints out-of-the-box, I believe you will need additional plug-ins to handle these. For your problem, this is of course not an issue.

如果我没有错，与GRG不同，Solver Foundation不能支持常规的非线性约束，我相信您将需要额外的插件来处理这些问题。对于你的问题，这当然不是问题。

For completeness, to formulate the LP problem instead, exchange the code between START NLP SECTION and END NLP SECTION with the following code:

为了完整起见，用下面的代码交换开始NLP部分和结束NLP部分之间的代码:

    var m = A.GetLength(0);
    var constraints = new Term[m];
    for (var j = 0; j < m; ++j)
    {
        Term Ax = 0.0;
        for (var i = 0; i < n; ++i) Ax += A[j, i] * x[i];
        model.AddConstraint(null, constraints[j] = Model.GreaterEqual(Ax, b[j]));
    }
    model.AddGoal(null, GoalKind.Minimize, Model.Sum(x));

which will yield the following output (note that objective functions are different in the two cases, hence the large differences in f):

这将产生以下输出(注意，在这两种情况下，目标函数是不同的，因此f):

f = 2125502.27815564
x[0] = 2017159
x[1] = 75302.7580022821
x[2] = 27215.9247379241
x[3] = 5824.5954154355
x[4] = 0

#1