Re: [Help-glpk] Expressing constraints

[Andrew Makhorin]

> The problem is as follows:  A wireless network design has been approved
> that contains 18 sites.  Each of these sites has been evaluated and a 
> transmit power has been estimated.  There are two types of wireless 
> nodes, A and B.  A costs $450 and can transmit at levels 1-15.  B costs 
> $250, but can only transmit at levels 8-18.  Minimize the cost of the 
> nodes while taking the transmit power in to account.

> I model this as the following:

> /* Sets */
> set NODES;

> /* Parameters */
> param power {i in NODES};

> /* Decision variables */
> var a_node {i in NODES},binary;
> var b_node {i in NODES},binary;

> /* Objective function */
> minimize z : sum{i in NODES} a_node[i] * 450 + sum{j in NODES} b_node[j] 
> * 250;

> /* Constraints */
> s.t. that{i in NODES} : a_node[i] + b_node[i] = 1;

> /* This is where I am having trouble */
> s.t. a_value{i in NODES} : if (power[i] >= 1 and power[i] < 8) then 
> a_node[i] = 1;
> s.t. b_value{i in NODES}:  if (power[i] > 15 and power[i] <= 18) then 
> b_node[i] = 1;

> data;
> set NODES := 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18;

> param power :=
> 1    8
> 2    5
> 3    9
> 4    4
> 5    12
> 6    11
> 7    7
> 8    13
> 9    18
> 10    14
> 11    7
> 12    9
> 13    15
> 14    12
> 15    7
> 16    4
> 17    13
> 18    11;

> end;

> I am having trouble expressing the transmit power constraint.  If what I 
> understand from the documentation is correct, then a constraint must be 
> a linear expression and hence cannot contain boolean operators or 
> conditional statements.  Have I done the right thing using two binary 
> variables, and if so, how can I express the transmit power constraint as 
> a linear expression? 

> The main thing I don't understand is how to relate a parameter such as 
> power to a variable in a constraint, such that the constraint only 
> applies to that variable, and not to the whole problem.  Is this 
> possible, or am I violating the laws of linear programming!!

Your model seems to be incorrectly formulated in the sense that it is
not optimization problem. Power is a parameter, i.e. known quantity,
and as it follows from constraints a_value and b_value (although they
are not valid constraints in mathprog) values of variables a_node and
b_node are immediately defined by power, so there is nothing to optimize.

As to modeling techniques used in mip, you can look at some example
models included in the glpk distribution.