Giving priority to some variables in linear programming

Question

I have to optimize an objective using binary integer linear programming, my objective function is:

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

For solving the problem efficiently I want to use some heuristics, according to one of the heuristics, some variables(xi) have more chance to be part of the answer (Xi=1), so my goal is to give priority (preference) to such variables to solve the problem faster than usual way, I know the solution may be sub-optimal but our main concern is time.

So my question are:

• How to prioritize this variables in the LP model?
• Can we multiply coefficients of this variables by constant (C>1) in order to increase their priority? or decrease priority of other variables by multiply their coefficients by another constant (D<1)?

• If we use the approach of question #2, do we have to do that just with objective function coefficients or both of objective function coefficients and constraints coefficients should be altered related to those variables?

• It should be noted that in the approach of question #2, after solving the LP model, we rollback any of changes in the coefficients according to the solution (Which variables are in the solution).

Thanks in advance

Answer 1

If you know that xi will be part of solution, you should include it as 1 into initial point x0 you pass to bintprog. The same for xj known to be likely not part of solution should be included as 0. If initial point is very close to the solution, this will reduce time to find it.

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

Another option is to relax BILP problem to LP problem with adding two extra conditions

 x <= 1
-x <= 0

and then using rounded solution for this problem as initial point for BILP problem.

Here authors state that bintprog performs well only on small problems. As I use Octave instead of Matlab, I tried GNU Linear Programming Kit (glpk). I tried to solve BILP problem from Matlab documentation and here is a script

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)

These are found solutions:

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

I had to perform 10000 iterations to make performance difference visible as the problem is still quite small. LP solution is faster comparing to BILP solution, and they are quite close.

Answer 2

According to CPLEX Performance Tuning for Mixed Integer Programs and Issuing priority orders we can set priority orders to increase or decrease priority of some variables in CPLEX, this approach is as follows:

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

fsl is priority array for problem variables. Because CPLEX can generate a priority order automatically, based on problem-data characteristics, we can leave the prioritization decision to CPLEX as follows:

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

After using priorities, my problem is solved, the solution is valid and converging to solution is faster than before!