[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 (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 (, 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;

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;


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 :)

reply via email to

[Prev in Thread] Current Thread [Next in Thread]