[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [Help-glpk] Expressing constraints

**From**: |
Sam |

**Subject**: |
[Help-glpk] Expressing constraints |

**Date**: |
Fri, 08 Feb 2008 16:18:51 +1300 |

**User-agent**: |
Thunderbird 1.5.0.14 (Windows/20071210) |

Hi there

`I am a newbie to glpk and linear programming in general. I come from a
``computer science background, so I have some mathematical understanding,
``but its not what I would call great. I have read the glpk article at
``IBM
``(http://www-128.ibm.com/developerworks/linux/library/l-glpk1/index.html),
``which I found very useful, and have now starting formulating my own
``problems.
`

`The first was very simple and worked almost straight away (it was a
``variation of Giapetto's problem). The second I have been having trouble
``with, and that is why I'm writing to the list (apologies if this problem
``has already been dealt with). I'm not sure if the trouble I am
``experiencing is due to my limited understanding of linear programming,
``but I'm sure you will point me in the right direction.
`

`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!!
`
Thanks in advance :)
Sam

**[Help-glpk] Expressing constraints**,
*Sam* **<=**