MATLAB：特定線性程序的快速高效內存解決方案

我有一點編程經驗，所以我很確定我沒有以最佳方式編碼問題，所以我很樂意聽到任何提示。MATLAB：特定線性程序的快速高效內存解決方案

我有兩個參數：問題n的尺寸和約束B其中N = 2n的N x N矩陣。在我的情況下，B是對稱的，只有正值。我需要解決以下問題

Optimization problem

這就是我需要最大限度地受到由B(i,j)給出成對的距離約束的距離有一定的平均值。

他們辦法，我現在做的是一個linprog(-f,A,b)實施，其中

f = ones([1,n])/n; 
f = [f -f]

和

b = reshape(B',numel(B),[])

和A定義如下

A = zeros([N^2,N]); 
for i = 1:N 
    for j = 1:N 
    if i ~= j 
     A((i-1)*N + j,i) = 1; 
     A((i-1)*N + j,j) = -1; 
    end 
end 
end

然而，當n = 500即使是一個簡單的建設A需要相當長的時間，而不是說線性程序的解決方案需要多長時間。任何提示都非常感謝，請隨時重新標記。

2013-08-21 Ilya

它看起來像您的解決方案的維度是* 2n *。 – Jacob

@Jacob：你是對的，修正了 – Ilya

首先，嘗試構建A像這樣：

AI = eye(N); 
AV = ones(N, 1); 
A = kron(AI, AV) - kron(AV, AI);

我覺得應該由至少一個數量級比你創造它的方式更快地運行。

2013-08-21 16:33:09

感謝您的建議，但令人驚訝的是，它運行速度比我的帖子中原來對'A'的定義要慢。例如，當「n = 200」，因此「N = 400」時，原始代碼在0.1秒內構造「A」，而您提出的代碼在2秒內運行。 – Ilya

@Ilya真的嗎？ O_o讓我想一想... –

如果您有興趣，我可以提供m文件 – Ilya

除了以更有效的方式創建問題矩陣之外，您還可以使用glpk和glpkmex接口來查看MATLAB。我發現我的解決方案時間可以大幅減少。您可能會看到另一個數量級，這取決於問題的大小。

如果您是學者，您可以免費獲得CPLEX或Gurobi許可證，這將使您在解決方案時間內進一步減少，而無需大量解決方案參數。對於您描述的大小的問題，這可能是必要的。

2013-08-21 20:13:23

謝謝，我已經嘗試了gurobi，它其實非常好。 – Ilya

回答