高效的方法如何解決線性規劃

Question

我做了線性規劃的研究，我需要解決一個複雜的（數百個變量和約束）問題。如何在一個獨立的解算器中解決LP（這不是問題）有很多方法。但是，我需要從C＃應用程序解決它。 我盡我所能找到任何方式如何解決在C＃代碼內的LP，但我發現（並可用）唯一的東西是CPLEX，它是.NET音樂庫庫。這看起來相當不錯（實際上我現在使用它並且工作良好），但是制定一些大型複雜問題是一個真正的噩夢！在10行中可以用AMPL編寫什麼，對於任何人都是可以理解的，在C＃中需要大約200行。

你知道C＃的任何庫，它允許以某種高效（友好）的方式提供問題模型定義嗎？ （CPLEX接受LP格式，但當您試圖解決許多變量的問題，然後該算法運行多年時，它可能會增長至數百兆字節）或者我聽說過將AMPL轉換爲LP格式然後求解它由CPLEX C＃庫提供，但效果不佳:-)

總之，我有C＃項目。我需要解決LP問題。我需要非常有效地解決這個問題......所有這些都是以一種相當簡單的方式（不是數百條混沌線在循環中添加變量和約束等）。

Answer 1

也許這不是你正在尋找的答案，但是Concert for .NET是模擬線性程序的好方法。我認爲你只是誇大了AMPL和Concert for .NET之間的差異。 AMPL書中的示例是AMPL中的SteelT.mod，隨後是CPLEX中包含的steel.cs的一部分。這大致對應於相同的代碼。缺少一些東西，比如數據讀取和調用解算器，但必須在AMPL中的單獨文件中寫入。這是122線。

是的，它比AMPL更困難，因爲它是一種通用編程語言的API。如果您需要使用C＃並且您有權訪問CPLEX，則這可能會足夠好。它也比AMPL更強大，比如在整數程序中訪問分支和綁定樹。

CPLEX本身包含很多很好的Concert例子。

set PROD;  # products 
param T > 0; # number of weeks 

param rate {PROD} > 0;   # tons per hour produced 
param inv0 {PROD} >= 0;   # initial inventory 
param avail {1..T} >= 0;  # hours available in week 
param market {PROD,1..T} >= 0; # limit on tons sold in week 

param prodcost {PROD} >= 0;  # cost per ton produced 
param invcost {PROD} >= 0;  # carrying cost/ton of inventory 
param revenue {PROD,1..T} >= 0; # revenue per ton sold 

var Make {PROD,1..T} >= 0;  # tons produced 
var Inv {PROD,0..T} >= 0;  # tons inventoried 
var Sell {p in PROD, t in 1..T} >= 0, <= market[p,t]; # tons sold 

maximize Total_Profit: 
    sum {p in PROD, t in 1..T} (revenue[p,t]*Sell[p,t] - 
    prodcost[p]*Make[p,t] - invcost[p]*Inv[p,t]); 

subject to Time {t in 1..T}: 
    sum {p in PROD} (1/rate[p]) * Make[p,t] <= avail[t]; 

subject to Init_Inv {p in PROD}: Inv[p,0] = inv0[p]; 

subject to Balance {p in PROD, t in 1..T}: 
    Make[p,t] + Inv[p,t-1] = Sell[p,t] + Inv[p,t]; 


    public class Steel { 
     internal static int _nProd; 
     internal static int _nTime; 

     internal static double[] _avail; 
     internal static double[] _rate; 
     internal static double[] _inv0; 
     internal static double[] _prodCost; 
     internal static double[] _invCost; 

     internal static double[][] _revenue; 
     internal static double[][] _market; 

     internal static void ReadData(string fileName) { 
      InputDataReader reader = new InputDataReader(fileName); 

      _avail = reader.ReadDoubleArray(); 
      _rate  = reader.ReadDoubleArray(); 
      _inv0  = reader.ReadDoubleArray(); 
      _prodCost = reader.ReadDoubleArray(); 
      _invCost = reader.ReadDoubleArray(); 
      _revenue = reader.ReadDoubleArrayArray(); 
      _market = reader.ReadDoubleArrayArray(); 

      _nProd = _rate.Length; 
      _nTime = _avail.Length; 
     } 

     public static void Main(string[] args) { 
      try { 
      string filename = "../../../../examples/data/steel.dat"; 
      if (args.Length > 0) 
       filename = args[0]; 
      ReadData(filename); 

      Cplex cplex = new Cplex(); 

      // VARIABLES 
      INumVar[][] Make = new INumVar[_nProd][]; 
      for (int p = 0; p < _nProd; p++) { 
       Make[p] = cplex.NumVarArray(_nTime, 0.0, System.Double.MaxValue); 
      } 

      INumVar[][] Inv = new INumVar[_nProd][]; 
      for (int p = 0; p < _nProd; p++) { 
       Inv[p] = cplex.NumVarArray(_nTime, 0.0, System.Double.MaxValue); 
      } 

      INumVar[][] Sell = new INumVar[_nProd][]; 
      for (int p = 0; p < _nProd; p++) { 
       Sell[p] = new INumVar[_nTime]; 
       for (int t = 0; t < _nTime; t++) { 
        Sell[p][t] = cplex.NumVar(0.0, _market[p][t]); 
       } 
      } 

      // OBJECTIVE 
      ILinearNumExpr TotalRevenue = cplex.LinearNumExpr(); 
      ILinearNumExpr TotalProdCost = cplex.LinearNumExpr(); 
      ILinearNumExpr TotalInvCost = cplex.LinearNumExpr(); 

      for (int p = 0; p < _nProd; p++) { 
       for (int t = 1; t < _nTime; t++) { 
        TotalRevenue.AddTerm (_revenue[p][t], Sell[p][t]); 
        TotalProdCost.AddTerm(_prodCost[p], Make[p][t]); 
        TotalInvCost.AddTerm (_invCost[p], Inv[p][t]); 
       } 
      } 

      cplex.AddMaximize(cplex.Diff(TotalRevenue, 
              cplex.Sum(TotalProdCost, TotalInvCost))); 

      // TIME AVAILABILITY CONSTRAINTS 

      for (int t = 0; t < _nTime; t++) { 
       ILinearNumExpr availExpr = cplex.LinearNumExpr(); 
       for (int p = 0; p < _nProd; p++) { 
        availExpr.AddTerm(1.0/_rate[p], Make[p][t]); 
       } 
       cplex.AddLe(availExpr, _avail[t]); 
      } 

      // MATERIAL BALANCE CONSTRAINTS 

      for (int p = 0; p < _nProd; p++) { 
       cplex.AddEq(cplex.Sum(Make[p][0], _inv0[p]), 
          cplex.Sum(Sell[p][0], Inv[p][0])); 
       for (int t = 1; t < _nTime; t++) { 
        cplex.AddEq(cplex.Sum(Make[p][t], Inv[p][t-1]), 
           cplex.Sum(Sell[p][t], Inv[p][t])); 
       } 
      } 

      cplex.ExportModel("steel.lp"); 

      if (cplex.Solve()) { 
       System.Console.WriteLine(); 
       System.Console.WriteLine("Total Profit = " + cplex.ObjValue); 

       System.Console.WriteLine(); 
       System.Console.WriteLine("\tp\tt\tMake\tInv\tSell"); 

       for (int p = 0; p < _nProd; p++) { 
        for (int t = 0; t < _nTime; t++) { 
         System.Console.WriteLine("\t" + p +"\t" + t +"\t" + cplex.GetValue(Make[p][t]) + 
               "\t" + cplex.GetValue(Inv[p][t]) +"\t" + cplex.GetValue(Sell[p][t])); 
        } 
       } 
      } 
      cplex.End(); 
      } 
      catch (ILOG.Concert.Exception exc) { 
      System.Console.WriteLine("Concert exception '" + exc + "' caught"); 
      } 
      catch (System.IO.IOException exc) { 
      System.Console.WriteLine("Error reading file " + args[0] + ": " + exc); 
      } 
      catch (InputDataReader.InputDataReaderException exc) { 
      System.Console.WriteLine(exc); 
      } 
     } 
    } 

Answer 2

如果您使用的是C或C++，我可能會推薦使用GLPK。這是非常乾淨的代碼，它附帶了AMPL的一個子集的實現和一個解算器，對於您正在處理的大小的模型來說，它是完全足夠的。因此，您可以使用GNU Mathprog（AMPL方言）編寫模型，並直接將其輸入LP解算器。