2

I have a linear program written in MathProg. My unknown binary variable is a two-dimensional array defined as:

var x{i in V, l in L}, >=0, <=1;

where V and L are sets of integers.

The value of some variables, however, are known in advance and I would like to specify this for the solver in order to reduce the size of the ILP. For example I know that x[4,l] when l=2 is 1 and for any other values of l is zero. Currently, I specify this as as a constraint:

s.t. initial4{i in V: i=4}:   sum{l in L}(l*x[i,l]) = 2;

I was wondering if this is the efficient way of specifying the values of a subset of unknowns in advance.

Ideally, I would like to place such information in a separate file together with the data section rather than in the model file.

Vadim Kotov
  • 8,084
  • 8
  • 48
  • 62
Ari
  • 7,251
  • 11
  • 40
  • 70

1 Answers1

2

Create an upper bound and lower bound for each variable:

var x{i in index_set}, >=x_L[i], <=x_U[i];

and adjust the lower and upper bounds for the known values.

Here is a MathProg snippet fixing x[2] to zero:

set index_set;

param x_L{index_set};
param x_U{index_set};

var x{i in index_set}, >=x_L[i], <=x_U[i];

s.t.

dummy:
  sum{i in index_set} x[i] = 2;

solve;

display x;

data;

set index_set := 1, 2, 3;

param x_L default 0;
param x_U default 1 :=
2 0;

end;

From the (filtered) output it is clear that the preprocessor is smart enough to fix x[2] to 0:

glpsol --math test.mod 

OPTIMAL SOLUTION FOUND BY LP PREPROCESSOR

x[1].val = 1
x[2].val = 0
x[3].val = 1
Ali
  • 56,466
  • 29
  • 168
  • 265
  • Thanks for the reply. I am using GLPK and wrote my model in GNU's MathProg. Unfortunately, MathProg doesn't have the keyword "let". – Ari May 16 '12 at 19:48
  • Great. I like this better than my solution. I think the summary of your answer is to create an upper bound and lower bound for every variable: var x{i in index_set}, >=x_L[i], <=x_U[i]; and adjust the lower and upper bounds for the known values. – Ari May 17 '12 at 17:40
  • Yes, exactly. I edited my answer and not it starts with your summary. Thanks for pointing it out. Good luck! – Ali May 17 '12 at 19:08