TomSym Location of GSM Transmitters - Revision history

Mbot at 13:33, 8 November 2011

2011-11-08T13:33:41Z

← Older revision		Revision as of 09:33, 8 November 2011
Line 133:		Line 133:
	<pre>		<pre>
	Problem type appears to be: mip		Problem type appears to be: mip
	Time for symbolic processing: 0.~~019762~~ seconds		Time for symbolic processing: 0.018398 seconds
	Starting numeric solver		Starting numeric solver
	===== * * * =================================================================== * * *		===== * * * =================================================================== * * *
Line 146:		Line 146:

	FuncEv 5		FuncEv 5
	~~CPU time: 0.046800 sec.~~ Elapsed time: 0.~~017000~~ sec.		Elapsed time: 0.005000 sec.
	Build at locations 2 4 6 7		Build at locations 2 4 6 7
	Cover communities 2 3 5 6 7 8 9 10 11 12 13 14 15		Cover communities 2 3 5 6 7 8 9 10 11 12 13 14 15

	</pre>		</pre>

Mbot at 21:24, 2 November 2011

2011-11-02T21:24:55Z

← Older revision		Revision as of 17:24, 2 November 2011
Line 11:		Line 11:
	Map of the region to cover		Map of the region to cover

			<pre>
	+--------+-------+----------+--------+		+--------+-------+----------+--------+
	\| \| * 7 / \|		\| \| * 7 / \|
Line 30:		Line 31:
	\| \ / \| +		\| \ / \| +
	+-------------+-+----------+---------+		+-------------+-+----------+---------+
			</pre>

	Inhabitants of the communities		Inhabitants of the communities

			<pre>
	+--------------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+		+--------------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
	\|Community \| 1\| 2\| 3\| 4\| 5\| 6\| 7\| 8\| 9\|10\|11\|12\|13\|14\|15\|		\|Community \| 1\| 2\| 3\| 4\| 5\| 6\| 7\| 8\| 9\|10\|11\|12\|13\|14\|15\|
Line 38:		Line 41:
	\|Population (in 1000)\| 2\| 4\|13\| 6\| 9\| 4\| 8\|12\|10\|11\| 6\|14\| 9\| 3\| 6\|		\|Population (in 1000)\| 2\| 4\|13\| 6\| 9\| 4\| 8\|12\|10\|11\| 6\|14\| 9\| 3\| 6\|
	+--------------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+		+--------------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
			</pre>

	Cost and communities covered for every site		Cost and communities covered for every site

			<pre>
	+-------------------+-----+-----+-----+-----+-----+---------+-------+		+-------------------+-----+-----+-----+-----+-----+---------+-------+
	\|Site \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \|		\|Site \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \|
Line 48:		Line 53:
	\| \| \| \| 8,10\| 8,9 \| 12 \| 11,12,15\| 14,15 \|		\| \| \| \| 8,10\| 8,9 \| 12 \| 11,12,15\| 14,15 \|
	+-------------------+-----+-----+--------+-------+------+-----------+		+-------------------+-----+-----+--------+-------+------+-----------+
			</pre>

	==Variables==		==Variables==

			<pre>
	budget Money available		budget Money available
	cost Cost to build site		cost Cost to build site
Line 57:		Line 64:
	var1 30 plus		var1 30 plus
	var2 30 minus		var2 30 minus
			</pre>

	==Reference==		==Reference==

Mbot: Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== A mobile phone operator decides to equip a currently uncovered geographical zon..."

2011-11-02T21:02:01Z

Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== A mobile phone operator decides to equip a currently uncovered geographical zon..."

New page

{{Part Of Manual|title=the TomSym Manual|link=[[TomSym|TomSym Manual]]}}

==Problem description==

A mobile phone operator decides to equip a currently uncovered geographical zone. The management allocates a budget of $ 10 million to equip this region. A study shows that only 7 locations are possible for the construction of the transmitters and it is also known that every transmitter only covers a certain number of communities. The figure below represents a schematic map of the region with the division into communities and the possible locations for transmitters. Every potential site is indicated by four stars and a number, every community is represented by a polygon. The number in the center of a polygon is the number of the community.

Certain geographical and topological constraints add to the construction cost and reduce the reach of the GSM transmitters. The table below lists the communities covered and the cost for every site.

For every community the number of inhabitants is known (see table). Where should the transmitters be built to cover the largest population with the given budget limit of $ 10M?

Map of the region to cover

+--------+-------+----------+--------+
| | * 7 / |
| 1 | 4 *3* / |
| * * /--\ /* 11 |
+-------*1* |/ 10 \/*6* |
| *\ / \ / -*--+-------+
| \ / \--/ \ |
| \ /\ | \ 15 |
| 2 / \ 8 |* \ |
| / \ *5* 12 *\ +
| / \ |* *7*\ /|
| / 5 \ | * \/ |
+-----*-+ * \|-----+----- / |
| *2* \ -*4*---+ | \ 14|
| * \ / * / | \ |
| \/ / 9 | \ |
| 3 \ 6 / | 13 \|
| \ / | +
+-------------+-+----------+---------+

Inhabitants of the communities

+--------------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|Community | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|
+--------------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|Population (in 1000)| 2| 4|13| 6| 9| 4| 8|12|10|11| 6|14| 9| 3| 6|
+--------------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Cost and communities covered for every site

+-------------------+-----+-----+-----+-----+-----+---------+-------+
|Site | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------------------+-----+-----+-----+-----+-----+---------+-------+
|Cost (in million $)| 1.8 | 1.3 | 4.0 | 3.5 | 3.8 | 2.6 | 2.1 |
|Communities covered|1,2,4|2,3,5| 4,7 | 5,6 | 8,9 | 7,10 | 12,13 |
| | | | 8,10| 8,9 | 12 | 11,12,15| 14,15 |
+-------------------+-----+-----+--------+-------+------+-----------+

==Variables==

budget Money available
cost Cost to build site
connections Communities covered by a site
population People living in communities
var1 30 plus
var2 30 minus

==Reference==

Applications of optimization... Gueret, Prins, Seveaux

<source lang="matlab">
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.2.0$
% Written Oct 7, 2005. Last modified Apr 8, 2009.
</source>

==Problem setup==

<source lang="matlab">
budget = 10e6;
cost = [1.8 1.3 4.0 3.5 3.8 2.6 2.1]'*1e6;

connections = [ 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0;...
0 1 1 0 1 0 0 0 0 0 0 0 0 0 0;...
0 0 0 1 0 0 1 1 0 1 0 0 0 0 0;...
0 0 0 0 1 1 0 1 1 0 0 0 0 0 0;...
0 0 0 0 0 0 0 1 1 0 0 1 0 0 0;...
0 0 0 0 0 0 1 0 0 1 1 1 0 0 1;...
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1];

population = [ 2 4 13 6 9 4 8 12 10 11 6 ...
14 9 3 6]'*1000;

p = length(cost); %number of locations to build
c = length(population); %areas to cover

covered = tom('covered',c,1,'int');
build = tom('build',p,1,'int');

% All variables are binary.
bnds = {0 <= covered <= 1, 0 <= build <= 1};

% Coverage constraint
con1 = {(connections'*build) >= covered};

% Budget constraint
con2 = {cost'*build <= budget};

% Objective
objective = -population'*covered;

constraints = {bnds, con1, con2};
options = struct;
options.solver = 'cplex';
options.name = 'Location of GSM Transmitters';
sol = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
disp(['Build at locations ' num2str(find(sol.build'))])
disp(['Cover communities ' num2str(find(sol.covered'))])
end

% MODIFICATION LOG
%
% 051130 med Created.
% 060116 per Added documentation.
% 060126 per Moved disp to end
% 090308 med Converted to tomSym
</source>

<pre>
Problem type appears to be: mip
Time for symbolic processing: 0.019762 seconds
Starting numeric solver
===== * * * =================================================================== * * *
TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31
=====================================================================================
Problem: --- 1: Location of GSM Transmitters f_k -109000.000000000000000000
f(x_0) 0.000000000000000000

Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found

FuncEv 5
CPU time: 0.046800 sec. Elapsed time: 0.017000 sec.
Build at locations 2 4 6 7
Cover communities 2 3 5 6 7 8 9 10 11 12 13 14 15

</pre>