在ILP中尋找最多需要太多時間，爲什麼？

簡而言之，我們現在試圖將IQP轉換爲ILP。舊的實施花了大約2天時間，現在用線性工具完成 - 它應該加速。基本上問題是最大化（大約50個二元變量）：在ILP中尋找最多需要太多時間，爲什麼？

$$ \ sum_ {g = 1}^{5} sum_ {p = 1}^{10}（S [p] x [g] [p] -Tiredness [G] [p] -Sleepness [G] [p]）$$

更新

我認爲大衛是在正確的軌道上，但是當我試圖最大限度地與表達獎金 - 變數，他們每次都是零，爲什麼？在某些代碼下方，分數可能類似S[1..10]=[1,2,3,4,5,6,7,8,9,10];。如果X1，X2是兩個變量

int S[1..10] = ...; // Scores per player =s 

dvar int x1[1..10] in 0..1; 
dvar int x2[1..10] in 0..1; 
dvar int x3[1..10] in 0..1; 
dvar int x4[1..10] in 0..1; 
dvar int x5[1..10] in 0..1; 

dvar int b1[1..10] in 0..100; 
dvar int b2[1..10] in 0..100; 


//ERR: the values of b1 and b2 should be maximized... 
// WHY not here so? 

maximize 
sum(i in 1..10) 
(
S[i] * 
    (
    (x1[i]+x2[i]+x3[i]+x4[i]+x5[i]) 
    - 1/10 * (b1 +b2) 
    ) 
); 

subject to 
{ 
    //We must play in 5 games. 
    //It means that there are 5 players in each game. 
    sum(i in 1..10) x1[i]==5; 
    sum(i in 1..10) x2[i]==5; 
    sum(i in 1..10) x3[i]==5; 
    sum(i in 1..10) x4[i]==5; 
    sum(i in 1..10) x5[i]==5; 

    // IQP problem into ILP -problem 

    forall (i in 1..10) 
    { 
     //ERROR HERE! 
     //it returns zero for b1 and b2, they should be maximized... 
     //I am trying to use the tip by David here, see his answer. 

     // EQ1: x2[i] * (x1[i]+x3[i]) 
     b1 <= 2*x2[i]; 
     b1 <= x1[i]+x3[i]; 

     // EQ2: x4[i] * (x3[i]+x5[i]+x1[i]) 
     b2 <= 3*x4[i]; 
     b2 <= x3[i]+x5[i]+x1[i]; 

    } 

};

來源

2011-11-08 hhh

這並不奇怪，它很慢，因爲這不是一個線性規劃問題（但是一個* integer *線性規劃問題），而且你有50個變量，而不是20個。你試圖解決什麼問題？ – jpalecek

所以你需要將玩家分配給遊戲，對吧？在ILP問題中，您沒有限制遊戲中的玩家數量，這樣好嗎？ – jpalecek

表達式像

x1 * x2

是二次。你有一個50變量整數二次規劃問題。此外，您的目標函數不是凹面的，因此CPLEX將會特別困難。
不過，既然你都0-1的變量，你可以通過添加一個額外的變量轉換成線性問題這一點，說獎金與正係數和處罰對於那些具有負係數的表達，他們將在目標函數，而不是二次項和添加以下約束

bonus <= x1 
bonus <= x2

或在負係數

penalty >= x1 + x2 - 1

由於你是的情況下最大化，cplex將強制獎金或罰款在最佳解決方案的正確值。的懲罰和獎勵的變量應該被宣佈爲非負

dvar float+ penalty; 
dvar float+ bonus;

這樣做對所有的二次表情和你的問題將成爲一個線性整數問題，解決得更快。

來源

2011-11-08 16:44:31

@hhh：那是因爲這個答案有點不對。因爲它在你的目標函數中具有負值係數，所以它不是*獎金*，而是* *罰款，你試圖*最小化*。約束也改變了，我建議'懲罰> = 0'和'懲罰> = x1 [y] + x3 [y] - 2 + 2 * x2 [y]'。 – jpalecek

@DavidNehme：...但不正確。對於刑罰情況，需要對界限進行調整。想象當x2爲0時（你需要另一個約束消失）或1（你想要相反）時會發生什麼。對於獎金案例，它的工作原理是這樣的，對於懲罰來說，事實並非如此。 – jpalecek

@jpalecek再次感謝。現在這應該工作。在懲罰案例中，如果x1或x2是0，那麼懲罰可以是零，但是如果兩者都不爲零，那麼懲罰必須至少爲1，並且目標應該將其推到1.在獎勵案例中，獎勵必須爲0除非x1和x2都是1.如果它們都是1，則目標應該將它推到1. –

在ILP中尋找最多需要太多時間，爲什麼？

回答

相關問題