高效的方法如何解决线性规划

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解算器。