|
| From: | Andrew Makhorin |
| Subject: | Re: [Help-glpk] Modelling Advice Request - Project Tasks |
| Date: | Thu, 21 Jan 2010 04:03:31 +0300 |
> I am modelling a project in which doing some tasks before others
> will save time. I think that the model is correct - but even though I
> have only entered the savings for 1 task into the objective function,
> it is taking too long to run. I believe that the problem lies in my
> "before1" and "before2" conditions, each of which contain 15^4=50625
> modelling variables. These conditions are needed to enable the
> before[] variable, where before[a,b]=1 means that task a will be
> completed before task b.
> The variable position[] is working correctly (position[5]=3 means
> that task five will be done third). I could eliminate the huge amount
> of work being done in the "before1" and "before2" conditions if I
> could make use of these position variables. Could anyone advise me how
> I can achieve the following, please?
You problem is a linear ordering problem; see, for example:
http://heur.uv.es/optsicom/LOLIB/
It can be efficiently solved using the row generation technique.
I have got a glpk-based code to solve this problem, so if you are
interested, I could post it to you.
Below here is the solution of your problem, where x[i,j] = 1 means that
task i precedes task j.
Data
15
0 2 0 2 0 0 0 0 1 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 3
4 0 0 0 1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 2 0 0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0 1 0 0 1 1 1
0 0 0 1 0 0 0 1 0 0 2 0 0 0 1
0 2 0 0 0 0 0 0 0 0 0 0 0 0 3
0 0 0 0 4 0 0 0 0 0 1 0 0 0 0
0 1 2 0 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 0 0 4 0 0 0 1
1 0 1 0 0 0 0 1 0 1 0 1 0 0 0
3 0 0 1 0 0 0 0 0 0 1 0 0 0 0
0 0 2 0 0 0 0 0 0 0 0 3 0 0 0
0 0 1 0 0 1 1 1 0 0 0 1 0 0 0
0 0 0 0 0 2 0 0 0 0 0 2 1 0 0
Reading LOP instance data from `file.txt'...
Data
Digraph has 15 nodes
17 lines were read
GLPK Simplex Optimizer, v4.43
0 rows, 105 columns, 0 non-zeros
~ 0: obj = 6.800000000e+01 infeas = 0.000e+00
OPTIMAL SOLUTION FOUND
GLPK Integer Optimizer, v4.43
0 rows, 105 columns, 0 non-zeros
105 integer variables, all of which are binary
Integer optimization begins...
+ 0: mip = not found yet <= +inf (1; 0)
+ 155: >>>>> 6.200000000e+01 <= 6.200000000e+01 0.0% (1; 0)
+ 155: mip = 6.200000000e+01 <= tree is empty 0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Problem:
Rows: 105
Columns: 210 (210 integer, 210 binary)
Non-zeros: 210
Status: INTEGER OPTIMAL
Objective: 62 (MAXimum)
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 x[1,2] * 0 0 1
2 x[1,3] * 0 0 1
3 x[1,4] * 0 0 1
4 x[1,5] * 0 0 1
5 x[1,6] * 0 0 1
6 x[1,7] * 0 0 1
7 x[1,8] * 0 0 1
8 x[1,9] * 0 0 1
9 x[1,10] * 0 0 1
10 x[1,11] * 0 0 1
11 x[1,12] * 0 0 1
12 x[1,13] * 0 0 1
13 x[1,14] * 0 0 1
14 x[1,15] * 0 0 1
15 x[2,1] * 1 0 1
16 x[2,3] * 1 0 1
17 x[2,4] * 0 0 1
18 x[2,5] * 0 0 1
19 x[2,6] * 0 0 1
20 x[2,7] * 0 0 1
21 x[2,8] * 0 0 1
22 x[2,9] * 0 0 1
23 x[2,10] * 0 0 1
24 x[2,11] * 1 0 1
25 x[2,12] * 1 0 1
26 x[2,13] * 1 0 1
27 x[2,14] * 0 0 1
28 x[2,15] * 1 0 1
29 x[3,1] * 1 0 1
30 x[3,2] * 0 0 1
31 x[3,4] * 0 0 1
32 x[3,5] * 0 0 1
33 x[3,6] * 0 0 1
34 x[3,7] * 0 0 1
35 x[3,8] * 0 0 1
36 x[3,9] * 0 0 1
37 x[3,10] * 0 0 1
38 x[3,11] * 0 0 1
39 x[3,12] * 1 0 1
40 x[3,13] * 0 0 1
41 x[3,14] * 0 0 1
42 x[3,15] * 0 0 1
43 x[4,1] * 1 0 1
44 x[4,2] * 1 0 1
45 x[4,3] * 1 0 1
46 x[4,5] * 1 0 1
47 x[4,6] * 0 0 1
48 x[4,7] * 0 0 1
49 x[4,8] * 0 0 1
50 x[4,9] * 0 0 1
51 x[4,10] * 1 0 1
52 x[4,11] * 1 0 1
53 x[4,12] * 1 0 1
54 x[4,13] * 1 0 1
55 x[4,14] * 0 0 1
56 x[4,15] * 1 0 1
57 x[5,1] * 1 0 1
58 x[5,2] * 1 0 1
59 x[5,3] * 1 0 1
60 x[5,4] * 0 0 1
61 x[5,6] * 0 0 1
62 x[5,7] * 0 0 1
63 x[5,8] * 0 0 1
64 x[5,9] * 0 0 1
65 x[5,10] * 1 0 1
66 x[5,11] * 1 0 1
67 x[5,12] * 1 0 1
68 x[5,13] * 1 0 1
69 x[5,14] * 0 0 1
70 x[5,15] * 1 0 1
71 x[6,1] * 1 0 1
72 x[6,2] * 1 0 1
73 x[6,3] * 1 0 1
74 x[6,4] * 1 0 1
75 x[6,5] * 1 0 1
76 x[6,7] * 0 0 1
77 x[6,8] * 1 0 1
78 x[6,9] * 0 0 1
79 x[6,10] * 1 0 1
80 x[6,11] * 1 0 1
81 x[6,12] * 1 0 1
82 x[6,13] * 1 0 1
83 x[6,14] * 0 0 1
84 x[6,15] * 1 0 1
85 x[7,1] * 1 0 1
86 x[7,2] * 1 0 1
87 x[7,3] * 1 0 1
88 x[7,4] * 1 0 1
89 x[7,5] * 1 0 1
90 x[7,6] * 1 0 1
91 x[7,8] * 1 0 1
92 x[7,9] * 0 0 1
93 x[7,10] * 1 0 1
94 x[7,11] * 1 0 1
95 x[7,12] * 1 0 1
96 x[7,13] * 1 0 1
97 x[7,14] * 0 0 1
98 x[7,15] * 1 0 1
99 x[8,1] * 1 0 1
100 x[8,2] * 1 0 1
101 x[8,3] * 1 0 1
102 x[8,4] * 1 0 1
103 x[8,5] * 1 0 1
104 x[8,6] * 0 0 1
105 x[8,7] * 0 0 1
106 x[8,9] * 0 0 1
107 x[8,10] * 1 0 1
108 x[8,11] * 1 0 1
109 x[8,12] * 1 0 1
110 x[8,13] * 1 0 1
111 x[8,14] * 0 0 1
112 x[8,15] * 1 0 1
113 x[9,1] * 1 0 1
114 x[9,2] * 1 0 1
115 x[9,3] * 1 0 1
116 x[9,4] * 1 0 1
117 x[9,5] * 1 0 1
118 x[9,6] * 1 0 1
119 x[9,7] * 1 0 1
120 x[9,8] * 1 0 1
121 x[9,10] * 1 0 1
122 x[9,11] * 1 0 1
123 x[9,12] * 1 0 1
124 x[9,13] * 1 0 1
125 x[9,14] * 0 0 1
126 x[9,15] * 1 0 1
127 x[10,1] * 1 0 1
128 x[10,2] * 1 0 1
129 x[10,3] * 1 0 1
130 x[10,4] * 0 0 1
131 x[10,5] * 0 0 1
132 x[10,6] * 0 0 1
133 x[10,7] * 0 0 1
134 x[10,8] * 0 0 1
135 x[10,9] * 0 0 1
136 x[10,11] * 1 0 1
137 x[10,12] * 1 0 1
138 x[10,13] * 1 0 1
139 x[10,14] * 0 0 1
140 x[10,15] * 1 0 1
141 x[11,1] * 1 0 1
142 x[11,2] * 0 0 1
143 x[11,3] * 1 0 1
144 x[11,4] * 0 0 1
145 x[11,5] * 0 0 1
146 x[11,6] * 0 0 1
147 x[11,7] * 0 0 1
148 x[11,8] * 0 0 1
149 x[11,9] * 0 0 1
150 x[11,10] * 0 0 1
151 x[11,12] * 1 0 1
152 x[11,13] * 1 0 1
153 x[11,14] * 0 0 1
154 x[11,15] * 1 0 1
155 x[12,1] * 1 0 1
156 x[12,2] * 0 0 1
157 x[12,3] * 0 0 1
158 x[12,4] * 0 0 1
159 x[12,5] * 0 0 1
160 x[12,6] * 0 0 1
161 x[12,7] * 0 0 1
162 x[12,8] * 0 0 1
163 x[12,9] * 0 0 1
164 x[12,10] * 0 0 1
165 x[12,11] * 0 0 1
166 x[12,13] * 0 0 1
167 x[12,14] * 0 0 1
168 x[12,15] * 0 0 1
169 x[13,1] * 1 0 1
170 x[13,2] * 0 0 1
171 x[13,3] * 1 0 1
172 x[13,4] * 0 0 1
173 x[13,5] * 0 0 1
174 x[13,6] * 0 0 1
175 x[13,7] * 0 0 1
176 x[13,8] * 0 0 1
177 x[13,9] * 0 0 1
178 x[13,10] * 0 0 1
179 x[13,11] * 0 0 1
180 x[13,12] * 1 0 1
181 x[13,14] * 0 0 1
182 x[13,15] * 0 0 1
183 x[14,1] * 1 0 1
184 x[14,2] * 1 0 1
185 x[14,3] * 1 0 1
186 x[14,4] * 1 0 1
187 x[14,5] * 1 0 1
188 x[14,6] * 1 0 1
189 x[14,7] * 1 0 1
190 x[14,8] * 1 0 1
191 x[14,9] * 1 0 1
192 x[14,10] * 1 0 1
193 x[14,11] * 1 0 1
194 x[14,12] * 1 0 1
195 x[14,13] * 1 0 1
196 x[14,15] * 1 0 1
197 x[15,1] * 1 0 1
198 x[15,2] * 0 0 1
199 x[15,3] * 1 0 1
200 x[15,4] * 0 0 1
201 x[15,5] * 0 0 1
202 x[15,6] * 0 0 1
203 x[15,7] * 0 0 1
204 x[15,8] * 0 0 1
205 x[15,9] * 0 0 1
206 x[15,10] * 0 0 1
207 x[15,11] * 0 0 1
208 x[15,12] * 1 0 1
209 x[15,13] * 1 0 1
210 x[15,14] * 0 0 1
End of output
| [Prev in Thread] | Current Thread | [Next in Thread] |