[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 <=