3

我对线性规划进行了研究，我需要解决一个复杂的（数百个变量和约束）问题。有很多方法可以在独立求解器中解决 LP（这不是问题）。但是，我需要从 C# 应用程序中解决它。我尽我所能找到如何在 C# 代码中解决 LP 的方法，但我发现（并且可用）的唯一东西是 CPLEX 和它的 .NET Concert 库。这看起来很不错（实际上我现在使用它并且效果很好）但是一些大型复杂问题的制定是一场真正的噩梦！可以用 AMPL 写成 10 行并且任何人都可以理解的内容，在 C# 中需要大约 200 行。

您是否知道任何 C# 库可以允许以某种有效（友好）的方式提供问题模型定义？（CPLEX 接受 LP 格式，但是当您尝试解决具有大量变量的问题然后算法运行很长时间时，它可能会增长到数百兆字节）或者我听说有可能将 AMPL 转换为 LP 格式然后解决它由 CPLEX C# 库提供，但听起来效率不高 :-)

简而言之，我有 C# 项目。我需要解决 LP 问题。我需要非常有效地解决它......所有这些都以某种相当简单的方式（而不是数百条混乱的线在for循环中添加变量和约束等）。

4

2 回答 2

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);
          }
       }
    }
于 2013-03-21T00:06:31.660 回答
0

如果您使用的是 C 或 C++，我可能会推荐GLPK。这是非常干净的代码，它附带了 AMPL 的某个子集的实现和一个求解器，对于您正在使用的大小的模型来说完全足够了。因此，您可以用 GNU Mathprog（它的 AMPL 方言）编写模型，然后直接将其输入 LP 求解器。

于 2013-03-21T08:47:52.813 回答