Jak mogę emulować funkcję Solver programu Microsoft Excel (GRG Nonlinear) w języku C#?

Question

Mam nieliniową optymalizację problemu z ograniczeniami. Można go rozwiązać w programie Microsoft Excel za pomocą dodatku Solver, ale mam problem z jego replikacją w języku C#.

Mój problem jest wyświetlany w following spreadsheet. Rozwiązuję problem klasyczny, ale z zastrzeżeniem, że wszystkie komponenty x muszą być nieujemne. Zamiast więc używać standardowej algebry liniowej, używam Solvera z ograniczeniem nieujemnym, minimalizując sumę kwadratów i uzyskując rozsądne rozwiązanie. Próbowałem replikować to w języku C# przy użyciu Microsoft Solver Foundation lub Solver SDK. Jednak nie mogę się z nimi nigdzie dostać, ponieważ przy MSF nie mogę wymyślić, jak zdefiniować cel, a przy SDK Solvera zawsze otrzymuję status "optymalny" i rozwiązanie wszystkich 0, co z pewnością nie jest nawet lokalne. minimum.

Oto mój kod 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; 
} 

nie mam żadnego kodu dla Microsoft Solver Fundacji, bo nie sądzę, aby funkcja celu może być zapisana w jednej linii i nie robi” • Pozwól delegatom takim jak Solver SDK.

Answer 1

Jedną alternatywą byłoby sformułować jako problem LP:

minimalizacji sumy elementów w x

zastrzeżeniem ax> = B

powinien być stosunkowo prosty sformułować za pomocą Solvera Foundation, opartego na jednej z próbek LP.

UPDATE 05 lipca

Powyższe podejście również wygląda zbyt skomplikowane, ale być może jest to spowodowane API Frontline Solver. Za pomocą programu Microsoft Solver Foundation, i minimalizacji sumy kwadratów różnic, następujący program:

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

generuje następujące rozwiązanie, które powinny być zgodne z roztworu z połączonego arkusza 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 

Jeśli się nie mylę, w przeciwieństwie do GRG, Solver Foundation nie może obsługiwać ogólnych nieliniowych ograniczeń po wyjęciu z pudełka, uważam, że do ich obsługi potrzebne będą dodatkowe wtyczki. Dla twojego problemu to oczywiście nie jest problem.

Dla kompletności sformułowanie problemu PR Zamiast wymieniać kodu między START NLP SEKCJI i END NLP SEKCJI z następującym kodu:

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

które otrzymano następujące wyniki (uwaga funkcje obiektywne są różne w obu przypadkach, stąd duże różnice w f):

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