優先解決一些變量線性規劃

Question

我必須優化使用二進制整數線性規劃的目標，我的目標函數是：

Maximize f= (c1 * x1) + (c2 * x2) +(c3 * x3) + ... + (c10000 * x10000) 
Subject to some constraints 

爲了解決該問題有效地我想用一些啓發根據啓發式之一，有些變量(xi)有更多機會成爲答案的一部分(Xi=1)，所以我的目標是給予優先（偏好）這樣的變量以比平常更快的方式解決問題，我知道解決方案可能是次優的但我們主要關心的是時間。

所以我的問題是：

• 如何在LP model這個變量的優先級？
• 我們可以將這個變量的係數乘以constant (C>1)以便增加它們的優先級？或者通過將它們的係數乘以另一個constant (D<1)來減少其他變量的優先級？

• 如果我們使用的問題＃2的方法，做我們必須做的是只是目標函數係數或的兩個目標函數係數和約束係數應當改變有關這些變量？

• 應該指出，在問題＃2的方法中，在求解LP模型之後，我們根據解決方案（解決方案中的哪些變量）回滾係數中的任何變化。

在此先感謝

Answer 1

根據CPLEX Performance Tuning for Mixed Integer Programs和Issuing priority orders我們可以設置優先順序增加或減少CPLEX一些變量的優先級，這種方法如下：

options = cplexoptimset('cplex'); 
options.mip.ordertype=fsl; 
[x,fval,exitflag,output] = cplexbilp(f, Aineq, bineq, Aeq, beq,[],options); 

fsl是問題的變量優先陣列。 因爲CPLEX可以自動生成的優先順序，根據問題的數據特徵，我們可以把優先級決定CPLEX如下：

value branching priority order 
===== ======================== 

    0  no automatic priority order will be generated (default) 
    1  decreasing cost coefficients among the variables 
    2  increasing bound range among the variables 
    3  increasing cost per matrix coefficient count among the variables 

使用的優先級後，我的問題解決了，解決的辦法是有效的，收斂解決方案比以前更快！

Answer 2

如果你知道xi將成爲解決方案的一部分，你應該把它作爲1到初始點x0傳遞給bintprog。對於已知可能不是解決方案的一部分的xj應該包括爲0。如果初始點非常接近解決方案，這將減少找到它的時間。

x = bintprog(f,A,b,Aeq,beq,x0); 

另一種選擇是放鬆BILP問題與添加兩個額外條件

x <= 1 
-x <= 0 

，然後使用針對此問題作爲初始點BILP問題圓形溶液到LP問題。

Here作者指出bintprog僅在小問題上表現良好。當我使用Octave而不是Matlab時，我嘗試了GNU線性編程套件（glpk）。我試圖從MATLAB documentation解決BILP問題，這裏是一個腳本

close all; clear all; 

f = [25,35,28,20,40,-10,-20,-40,-18,-36,-72,-11,-22,-44,-9,-18,-36,-10,-20]'; 
A = zeros(14,19); 
A(1,1:19) = [25 35 28 20 40 5 10 20 7 14 28 6 12 24 4 8 16 8 16]; 
A(2,1) = 1; A(2,6) = -1; A(2,7) = -1; A(2,8) = -1; 
A(3,2) = 1; A(3,9) = -1; A(3,10) = -1; A(3,11) = -1; 
A(4,3) = 1; A(4,12) = -1; A(4,13) = -1; A(4,14) = -1; 
A(5,4) = 1; A(5,15) = -1; A(5,16) = -1; A(5,17) = -1; 
A(6,5) = 1; A(6,18) = -1; A(6,19) = -1; 
A(7,1) = -5; A(7,6) = 1; A(7,7) = 2; A(7,8) = 4; 
A(8,2) = -4; A(8,9) = 1; A(8,10) = 2; A(8,11) = 4; 
A(9,3) = -5; A(9,12) = 1; A(9,13) = 2; A(9,14) = 4; 
A(10,4) = -7; A(10,15) = 1; A(10,16) = 2; A(10,17) = 4; 
A(11,5) = -3; A(11,18) = 1; A(11,19) = 2; 
A(12,2) = 1; A(12,5) = 1; 
A(13,1) = 1; A(13,2) = -1; A(13,3) = -1; 
A(14,3) = -1; A(14,4) = -1; A(14,5) = -1; 
b = [125 0 0 0 0 0 0 0 0 0 0 1 0 -2]'; 
lb = zeros(size(f)); 
ub = ones(size(f)); 
ctype = repmat("U" , size(b))'; # inequality constraint 
sense = 1; # minimization 
param.msglev = 0; 

vartype = repmat("C" , size(f)); # continuous variables 
tic 
for i = 1:10000 
[xopt, fmin, errnum, extra] = glpk (f, A, b, lb, ub, ctype, vartype, sense, param); 
end 
toc 
fprintf('Solution %s with value %f\n', mat2str(xopt), fmin) 

vartype = repmat("I" , size(f)); # integer variables 
tic 
for i = 1:10000 
[xopt, fmin, errnum, extra] = glpk (f, A, b, lb, ub, ctype, vartype, sense, param); 
end 
toc 
fprintf('Solution %s with value %f\n', mat2str(xopt), fmin) 

這些被發現的解決方案：

Elapsed time is 7.9 seconds. 
Solution [0;0.301587301587301;1;1;0;0;0;0;0;0.603174603174603;0;1;1;0.5;1;1;1;0;0] with value -81.158730 
Elapsed time is 11.5 seconds. 
Solution [0;0;1;1;0;0;0;0;0;0;0;1;0;1;1;1;1;0;0] with value -70.000000 

我不得不執行10000次迭代，使性能差異明顯的問題還是相當小。與BILP解決方案相比，LP解決方案更快，而且它們非常接近。