2013-03-20 3 views
3

선형 프로그래밍에 대한 연구를하고 복잡한 (수백 가지 변수 및 제약 조건) 문제를 해결해야합니다. 자립형 솔버에서 LP (문제는 아닙니다)를 해결하는 방법에는 여러 가지가 있습니다. 그러나 C# 응용 프로그램에서 해결해야합니다. C# 코드 내에서 LP를 해결하는 방법을 찾기 위해 최선을 다했지만 CPLEX와 .NET Concert 라이브러리 만 찾았습니다 (사용 가능했습니다). 이것은 꽤 잘 보인다. (실제로 나는 그것을 사용한다. 그리고 그것은 잘 작동한다.) 그러나 어떤 큰 복잡한 문제의 공식화는 진짜 악몽이다! AMPL로 10 열로 작성 될 수 있고 누구에게나 이해할 수있는 것은 C#에서 약 200 행이 필요합니다.효율적인 방법 선형 프로그래밍을 해결하는 방법

효율적이고 (우호적 인) 방법으로 문제 모델 정의를 제공 할 수있는 라이브러리를 알고 계십니까? (CPLEX에서는 LP 형식을 사용할 수 있지만 많은 변수로 문제를 풀려고하면 수십 메가 바이트까지 커질 수 있으며 알고리즘은 여러 기간 동안 실행됩니다.) 또는 AMPL을 LP 형식으로 변환 한 다음 해결할 가능성에 대해 들었습니다. 그것 CPLEX C# 라이브러리에 의해 효율적으로 소리하지 않습니다 :-)

요컨대, 나는 C# 프로젝트 있습니다. 나는 LP 문제를 해결할 필요가있다. 나는 그것을 매우 효율적으로 해결할 필요가있다. 모든 것을 합리적으로 간단한 방법으로 (for-cycle 등에서 변수와 제약을 추가하는 수많은 혼란이 아닌).

+3

Microsoft는 [Solver Foundation] (http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx)을 제공합니다. 나는 그것을 사용한 적이 없기 때문에 당신의 문제가 해결되는지 말할 수 없다. 여전히 가치가있을 것입니다. –

+0

아마도 SO에 적합하지 않을 수 있습니다. "내가 좋아하는 API를 찾았습니다"라는 질문에 기초한 질문은 다른 사람들이 대답 할 수 없습니다. "라이브러리"에 대한 검색 엔진으로 SO 질문을 사용하는 것은 권장하지 않습니다. –

+0

여기에 중복되거나 비슷한 질문이있을 수 있습니다 : http://stackoverflow.com/questions/3363143/good-linear-programming-library-for-c –

답변

1

아마이 대답은 당신이 찾고있는 답변이 아니지만 .NET 용 Concert는 선형 프로그램을 모델링하는 좋은 방법입니다. 나는 당신이 단순히 AMPL과 Concert for .NET의 차이점을 과장하고 있다고 생각한다. 다음은 AMPL 책 예제의 AMPL에있는 SteelT.mod와 CPLEX에 포함 된 steel.cs의 일부입니다. 이것은 대략 동일한 코드와 일치합니다. 데이터 읽기 및 호출과 같은 몇 가지 사항이 누락되었지만 AMPL의 별도 파일에 작성해야합니다. 122 줄입니다.

예, 범용 프로그래밍 언어 용 API이기 때문에 AMPL보다 어렵습니다. C#을 사용해야하고 CPLEX에 액세스 할 수 있으면 충분할 것입니다. 또한 정수 프로그램의 분기 및 바운드 트리에 대한 액세스와 같이 AMPL보다 뛰어난 기능을 제공합니다.

CPLEX 자체에 포함 된 콘서트 예제가 많이 있습니다.

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); 
      } 
     } 
    } 
+0

당신은 다소 옳습니다. 콘서트 모델 공식을 읽거나 수정하기가 어렵습니다. 그리고 공식이 정말로 자연스러운 것이 아니기 때문에 (수학적 관점에서 볼 때) 몇 초 안에 확인할 수있는 AMPL과 비교하여 실수를 매우 쉽게 (사이클, 인덱스 등) 만들 수 있으며 거의 즉시 실수. 그러나 나는 콘서트가 지금까지 내가 찾은 최고의 해결책이라는 것에 동의한다. – Marek

0

C 또는 C++를 사용하는 경우 GLPK을 권장 할 수 있습니다. 그것은 매우 깨끗한 코드이며, AMPL의 특정 하위 집합과 함께 작업하는 크기의 모델에 대해 충분히 만족되는 해석기를 구현합니다. 따라서 GNU Mathprog (AMPL 언어)에서 모델을 작성하고이를 LP 솔버로 직접 공급할 수 있습니다.

+0

나는 GLPK에 C# 래퍼가 추가되어야한다고 생각한다. 나는이 패키지가 "GLPK #"라고 생각한다. 나는 그것을 결코 시도하지 않았다. 그래서 나는 그 품질을 정말로 보증 할 수 없다. – tmyklebu