rev |
line source |
alpar@9
|
1 /* glpscl.c (problem scaling routines) */
|
alpar@9
|
2
|
alpar@9
|
3 /***********************************************************************
|
alpar@9
|
4 * This code is part of GLPK (GNU Linear Programming Kit).
|
alpar@9
|
5 *
|
alpar@9
|
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
|
alpar@9
|
7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
|
alpar@9
|
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
|
alpar@9
|
9 * E-mail: <mao@gnu.org>.
|
alpar@9
|
10 *
|
alpar@9
|
11 * GLPK is free software: you can redistribute it and/or modify it
|
alpar@9
|
12 * under the terms of the GNU General Public License as published by
|
alpar@9
|
13 * the Free Software Foundation, either version 3 of the License, or
|
alpar@9
|
14 * (at your option) any later version.
|
alpar@9
|
15 *
|
alpar@9
|
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
|
alpar@9
|
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
alpar@9
|
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
|
alpar@9
|
19 * License for more details.
|
alpar@9
|
20 *
|
alpar@9
|
21 * You should have received a copy of the GNU General Public License
|
alpar@9
|
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
|
alpar@9
|
23 ***********************************************************************/
|
alpar@9
|
24
|
alpar@9
|
25 #include "glpapi.h"
|
alpar@9
|
26
|
alpar@9
|
27 /***********************************************************************
|
alpar@9
|
28 * min_row_aij - determine minimal |a[i,j]| in i-th row
|
alpar@9
|
29 *
|
alpar@9
|
30 * This routine returns minimal magnitude of (non-zero) constraint
|
alpar@9
|
31 * coefficients in i-th row of the constraint matrix.
|
alpar@9
|
32 *
|
alpar@9
|
33 * If the parameter scaled is zero, the original constraint matrix A is
|
alpar@9
|
34 * assumed. Otherwise, the scaled constraint matrix R*A*S is assumed.
|
alpar@9
|
35 *
|
alpar@9
|
36 * If i-th row of the matrix is empty, the routine returns 1. */
|
alpar@9
|
37
|
alpar@9
|
38 static double min_row_aij(glp_prob *lp, int i, int scaled)
|
alpar@9
|
39 { GLPAIJ *aij;
|
alpar@9
|
40 double min_aij, temp;
|
alpar@9
|
41 xassert(1 <= i && i <= lp->m);
|
alpar@9
|
42 min_aij = 1.0;
|
alpar@9
|
43 for (aij = lp->row[i]->ptr; aij != NULL; aij = aij->r_next)
|
alpar@9
|
44 { temp = fabs(aij->val);
|
alpar@9
|
45 if (scaled) temp *= (aij->row->rii * aij->col->sjj);
|
alpar@9
|
46 if (aij->r_prev == NULL || min_aij > temp)
|
alpar@9
|
47 min_aij = temp;
|
alpar@9
|
48 }
|
alpar@9
|
49 return min_aij;
|
alpar@9
|
50 }
|
alpar@9
|
51
|
alpar@9
|
52 /***********************************************************************
|
alpar@9
|
53 * max_row_aij - determine maximal |a[i,j]| in i-th row
|
alpar@9
|
54 *
|
alpar@9
|
55 * This routine returns maximal magnitude of (non-zero) constraint
|
alpar@9
|
56 * coefficients in i-th row of the constraint matrix.
|
alpar@9
|
57 *
|
alpar@9
|
58 * If the parameter scaled is zero, the original constraint matrix A is
|
alpar@9
|
59 * assumed. Otherwise, the scaled constraint matrix R*A*S is assumed.
|
alpar@9
|
60 *
|
alpar@9
|
61 * If i-th row of the matrix is empty, the routine returns 1. */
|
alpar@9
|
62
|
alpar@9
|
63 static double max_row_aij(glp_prob *lp, int i, int scaled)
|
alpar@9
|
64 { GLPAIJ *aij;
|
alpar@9
|
65 double max_aij, temp;
|
alpar@9
|
66 xassert(1 <= i && i <= lp->m);
|
alpar@9
|
67 max_aij = 1.0;
|
alpar@9
|
68 for (aij = lp->row[i]->ptr; aij != NULL; aij = aij->r_next)
|
alpar@9
|
69 { temp = fabs(aij->val);
|
alpar@9
|
70 if (scaled) temp *= (aij->row->rii * aij->col->sjj);
|
alpar@9
|
71 if (aij->r_prev == NULL || max_aij < temp)
|
alpar@9
|
72 max_aij = temp;
|
alpar@9
|
73 }
|
alpar@9
|
74 return max_aij;
|
alpar@9
|
75 }
|
alpar@9
|
76
|
alpar@9
|
77 /***********************************************************************
|
alpar@9
|
78 * min_col_aij - determine minimal |a[i,j]| in j-th column
|
alpar@9
|
79 *
|
alpar@9
|
80 * This routine returns minimal magnitude of (non-zero) constraint
|
alpar@9
|
81 * coefficients in j-th column of the constraint matrix.
|
alpar@9
|
82 *
|
alpar@9
|
83 * If the parameter scaled is zero, the original constraint matrix A is
|
alpar@9
|
84 * assumed. Otherwise, the scaled constraint matrix R*A*S is assumed.
|
alpar@9
|
85 *
|
alpar@9
|
86 * If j-th column of the matrix is empty, the routine returns 1. */
|
alpar@9
|
87
|
alpar@9
|
88 static double min_col_aij(glp_prob *lp, int j, int scaled)
|
alpar@9
|
89 { GLPAIJ *aij;
|
alpar@9
|
90 double min_aij, temp;
|
alpar@9
|
91 xassert(1 <= j && j <= lp->n);
|
alpar@9
|
92 min_aij = 1.0;
|
alpar@9
|
93 for (aij = lp->col[j]->ptr; aij != NULL; aij = aij->c_next)
|
alpar@9
|
94 { temp = fabs(aij->val);
|
alpar@9
|
95 if (scaled) temp *= (aij->row->rii * aij->col->sjj);
|
alpar@9
|
96 if (aij->c_prev == NULL || min_aij > temp)
|
alpar@9
|
97 min_aij = temp;
|
alpar@9
|
98 }
|
alpar@9
|
99 return min_aij;
|
alpar@9
|
100 }
|
alpar@9
|
101
|
alpar@9
|
102 /***********************************************************************
|
alpar@9
|
103 * max_col_aij - determine maximal |a[i,j]| in j-th column
|
alpar@9
|
104 *
|
alpar@9
|
105 * This routine returns maximal magnitude of (non-zero) constraint
|
alpar@9
|
106 * coefficients in j-th column of the constraint matrix.
|
alpar@9
|
107 *
|
alpar@9
|
108 * If the parameter scaled is zero, the original constraint matrix A is
|
alpar@9
|
109 * assumed. Otherwise, the scaled constraint matrix R*A*S is assumed.
|
alpar@9
|
110 *
|
alpar@9
|
111 * If j-th column of the matrix is empty, the routine returns 1. */
|
alpar@9
|
112
|
alpar@9
|
113 static double max_col_aij(glp_prob *lp, int j, int scaled)
|
alpar@9
|
114 { GLPAIJ *aij;
|
alpar@9
|
115 double max_aij, temp;
|
alpar@9
|
116 xassert(1 <= j && j <= lp->n);
|
alpar@9
|
117 max_aij = 1.0;
|
alpar@9
|
118 for (aij = lp->col[j]->ptr; aij != NULL; aij = aij->c_next)
|
alpar@9
|
119 { temp = fabs(aij->val);
|
alpar@9
|
120 if (scaled) temp *= (aij->row->rii * aij->col->sjj);
|
alpar@9
|
121 if (aij->c_prev == NULL || max_aij < temp)
|
alpar@9
|
122 max_aij = temp;
|
alpar@9
|
123 }
|
alpar@9
|
124 return max_aij;
|
alpar@9
|
125 }
|
alpar@9
|
126
|
alpar@9
|
127 /***********************************************************************
|
alpar@9
|
128 * min_mat_aij - determine minimal |a[i,j]| in constraint matrix
|
alpar@9
|
129 *
|
alpar@9
|
130 * This routine returns minimal magnitude of (non-zero) constraint
|
alpar@9
|
131 * coefficients in the constraint matrix.
|
alpar@9
|
132 *
|
alpar@9
|
133 * If the parameter scaled is zero, the original constraint matrix A is
|
alpar@9
|
134 * assumed. Otherwise, the scaled constraint matrix R*A*S is assumed.
|
alpar@9
|
135 *
|
alpar@9
|
136 * If the matrix is empty, the routine returns 1. */
|
alpar@9
|
137
|
alpar@9
|
138 static double min_mat_aij(glp_prob *lp, int scaled)
|
alpar@9
|
139 { int i;
|
alpar@9
|
140 double min_aij, temp;
|
alpar@9
|
141 min_aij = 1.0;
|
alpar@9
|
142 for (i = 1; i <= lp->m; i++)
|
alpar@9
|
143 { temp = min_row_aij(lp, i, scaled);
|
alpar@9
|
144 if (i == 1 || min_aij > temp)
|
alpar@9
|
145 min_aij = temp;
|
alpar@9
|
146 }
|
alpar@9
|
147 return min_aij;
|
alpar@9
|
148 }
|
alpar@9
|
149
|
alpar@9
|
150 /***********************************************************************
|
alpar@9
|
151 * max_mat_aij - determine maximal |a[i,j]| in constraint matrix
|
alpar@9
|
152 *
|
alpar@9
|
153 * This routine returns maximal magnitude of (non-zero) constraint
|
alpar@9
|
154 * coefficients in the constraint matrix.
|
alpar@9
|
155 *
|
alpar@9
|
156 * If the parameter scaled is zero, the original constraint matrix A is
|
alpar@9
|
157 * assumed. Otherwise, the scaled constraint matrix R*A*S is assumed.
|
alpar@9
|
158 *
|
alpar@9
|
159 * If the matrix is empty, the routine returns 1. */
|
alpar@9
|
160
|
alpar@9
|
161 static double max_mat_aij(glp_prob *lp, int scaled)
|
alpar@9
|
162 { int i;
|
alpar@9
|
163 double max_aij, temp;
|
alpar@9
|
164 max_aij = 1.0;
|
alpar@9
|
165 for (i = 1; i <= lp->m; i++)
|
alpar@9
|
166 { temp = max_row_aij(lp, i, scaled);
|
alpar@9
|
167 if (i == 1 || max_aij < temp)
|
alpar@9
|
168 max_aij = temp;
|
alpar@9
|
169 }
|
alpar@9
|
170 return max_aij;
|
alpar@9
|
171 }
|
alpar@9
|
172
|
alpar@9
|
173 /***********************************************************************
|
alpar@9
|
174 * eq_scaling - perform equilibration scaling
|
alpar@9
|
175 *
|
alpar@9
|
176 * This routine performs equilibration scaling of rows and columns of
|
alpar@9
|
177 * the constraint matrix.
|
alpar@9
|
178 *
|
alpar@9
|
179 * If the parameter flag is zero, the routine scales rows at first and
|
alpar@9
|
180 * then columns. Otherwise, the routine scales columns and then rows.
|
alpar@9
|
181 *
|
alpar@9
|
182 * Rows are scaled as follows:
|
alpar@9
|
183 *
|
alpar@9
|
184 * n
|
alpar@9
|
185 * a'[i,j] = a[i,j] / max |a[i,j]|, i = 1,...,m.
|
alpar@9
|
186 * j=1
|
alpar@9
|
187 *
|
alpar@9
|
188 * This makes the infinity (maximum) norm of each row of the matrix
|
alpar@9
|
189 * equal to 1.
|
alpar@9
|
190 *
|
alpar@9
|
191 * Columns are scaled as follows:
|
alpar@9
|
192 *
|
alpar@9
|
193 * m
|
alpar@9
|
194 * a'[i,j] = a[i,j] / max |a[i,j]|, j = 1,...,n.
|
alpar@9
|
195 * i=1
|
alpar@9
|
196 *
|
alpar@9
|
197 * This makes the infinity (maximum) norm of each column of the matrix
|
alpar@9
|
198 * equal to 1. */
|
alpar@9
|
199
|
alpar@9
|
200 static void eq_scaling(glp_prob *lp, int flag)
|
alpar@9
|
201 { int i, j, pass;
|
alpar@9
|
202 double temp;
|
alpar@9
|
203 xassert(flag == 0 || flag == 1);
|
alpar@9
|
204 for (pass = 0; pass <= 1; pass++)
|
alpar@9
|
205 { if (pass == flag)
|
alpar@9
|
206 { /* scale rows */
|
alpar@9
|
207 for (i = 1; i <= lp->m; i++)
|
alpar@9
|
208 { temp = max_row_aij(lp, i, 1);
|
alpar@9
|
209 glp_set_rii(lp, i, glp_get_rii(lp, i) / temp);
|
alpar@9
|
210 }
|
alpar@9
|
211 }
|
alpar@9
|
212 else
|
alpar@9
|
213 { /* scale columns */
|
alpar@9
|
214 for (j = 1; j <= lp->n; j++)
|
alpar@9
|
215 { temp = max_col_aij(lp, j, 1);
|
alpar@9
|
216 glp_set_sjj(lp, j, glp_get_sjj(lp, j) / temp);
|
alpar@9
|
217 }
|
alpar@9
|
218 }
|
alpar@9
|
219 }
|
alpar@9
|
220 return;
|
alpar@9
|
221 }
|
alpar@9
|
222
|
alpar@9
|
223 /***********************************************************************
|
alpar@9
|
224 * gm_scaling - perform geometric mean scaling
|
alpar@9
|
225 *
|
alpar@9
|
226 * This routine performs geometric mean scaling of rows and columns of
|
alpar@9
|
227 * the constraint matrix.
|
alpar@9
|
228 *
|
alpar@9
|
229 * If the parameter flag is zero, the routine scales rows at first and
|
alpar@9
|
230 * then columns. Otherwise, the routine scales columns and then rows.
|
alpar@9
|
231 *
|
alpar@9
|
232 * Rows are scaled as follows:
|
alpar@9
|
233 *
|
alpar@9
|
234 * a'[i,j] = a[i,j] / sqrt(alfa[i] * beta[i]), i = 1,...,m,
|
alpar@9
|
235 *
|
alpar@9
|
236 * where:
|
alpar@9
|
237 * n n
|
alpar@9
|
238 * alfa[i] = min |a[i,j]|, beta[i] = max |a[i,j]|.
|
alpar@9
|
239 * j=1 j=1
|
alpar@9
|
240 *
|
alpar@9
|
241 * This allows decreasing the ratio beta[i] / alfa[i] for each row of
|
alpar@9
|
242 * the matrix.
|
alpar@9
|
243 *
|
alpar@9
|
244 * Columns are scaled as follows:
|
alpar@9
|
245 *
|
alpar@9
|
246 * a'[i,j] = a[i,j] / sqrt(alfa[j] * beta[j]), j = 1,...,n,
|
alpar@9
|
247 *
|
alpar@9
|
248 * where:
|
alpar@9
|
249 * m m
|
alpar@9
|
250 * alfa[j] = min |a[i,j]|, beta[j] = max |a[i,j]|.
|
alpar@9
|
251 * i=1 i=1
|
alpar@9
|
252 *
|
alpar@9
|
253 * This allows decreasing the ratio beta[j] / alfa[j] for each column
|
alpar@9
|
254 * of the matrix. */
|
alpar@9
|
255
|
alpar@9
|
256 static void gm_scaling(glp_prob *lp, int flag)
|
alpar@9
|
257 { int i, j, pass;
|
alpar@9
|
258 double temp;
|
alpar@9
|
259 xassert(flag == 0 || flag == 1);
|
alpar@9
|
260 for (pass = 0; pass <= 1; pass++)
|
alpar@9
|
261 { if (pass == flag)
|
alpar@9
|
262 { /* scale rows */
|
alpar@9
|
263 for (i = 1; i <= lp->m; i++)
|
alpar@9
|
264 { temp = min_row_aij(lp, i, 1) * max_row_aij(lp, i, 1);
|
alpar@9
|
265 glp_set_rii(lp, i, glp_get_rii(lp, i) / sqrt(temp));
|
alpar@9
|
266 }
|
alpar@9
|
267 }
|
alpar@9
|
268 else
|
alpar@9
|
269 { /* scale columns */
|
alpar@9
|
270 for (j = 1; j <= lp->n; j++)
|
alpar@9
|
271 { temp = min_col_aij(lp, j, 1) * max_col_aij(lp, j, 1);
|
alpar@9
|
272 glp_set_sjj(lp, j, glp_get_sjj(lp, j) / sqrt(temp));
|
alpar@9
|
273 }
|
alpar@9
|
274 }
|
alpar@9
|
275 }
|
alpar@9
|
276 return;
|
alpar@9
|
277 }
|
alpar@9
|
278
|
alpar@9
|
279 /***********************************************************************
|
alpar@9
|
280 * max_row_ratio - determine worst scaling "quality" for rows
|
alpar@9
|
281 *
|
alpar@9
|
282 * This routine returns the worst scaling "quality" for rows of the
|
alpar@9
|
283 * currently scaled constraint matrix:
|
alpar@9
|
284 *
|
alpar@9
|
285 * m
|
alpar@9
|
286 * ratio = max ratio[i],
|
alpar@9
|
287 * i=1
|
alpar@9
|
288 * where:
|
alpar@9
|
289 * n n
|
alpar@9
|
290 * ratio[i] = max |a[i,j]| / min |a[i,j]|, 1 <= i <= m,
|
alpar@9
|
291 * j=1 j=1
|
alpar@9
|
292 *
|
alpar@9
|
293 * is the scaling "quality" of i-th row. */
|
alpar@9
|
294
|
alpar@9
|
295 static double max_row_ratio(glp_prob *lp)
|
alpar@9
|
296 { int i;
|
alpar@9
|
297 double ratio, temp;
|
alpar@9
|
298 ratio = 1.0;
|
alpar@9
|
299 for (i = 1; i <= lp->m; i++)
|
alpar@9
|
300 { temp = max_row_aij(lp, i, 1) / min_row_aij(lp, i, 1);
|
alpar@9
|
301 if (i == 1 || ratio < temp) ratio = temp;
|
alpar@9
|
302 }
|
alpar@9
|
303 return ratio;
|
alpar@9
|
304 }
|
alpar@9
|
305
|
alpar@9
|
306 /***********************************************************************
|
alpar@9
|
307 * max_col_ratio - determine worst scaling "quality" for columns
|
alpar@9
|
308 *
|
alpar@9
|
309 * This routine returns the worst scaling "quality" for columns of the
|
alpar@9
|
310 * currently scaled constraint matrix:
|
alpar@9
|
311 *
|
alpar@9
|
312 * n
|
alpar@9
|
313 * ratio = max ratio[j],
|
alpar@9
|
314 * j=1
|
alpar@9
|
315 * where:
|
alpar@9
|
316 * m m
|
alpar@9
|
317 * ratio[j] = max |a[i,j]| / min |a[i,j]|, 1 <= j <= n,
|
alpar@9
|
318 * i=1 i=1
|
alpar@9
|
319 *
|
alpar@9
|
320 * is the scaling "quality" of j-th column. */
|
alpar@9
|
321
|
alpar@9
|
322 static double max_col_ratio(glp_prob *lp)
|
alpar@9
|
323 { int j;
|
alpar@9
|
324 double ratio, temp;
|
alpar@9
|
325 ratio = 1.0;
|
alpar@9
|
326 for (j = 1; j <= lp->n; j++)
|
alpar@9
|
327 { temp = max_col_aij(lp, j, 1) / min_col_aij(lp, j, 1);
|
alpar@9
|
328 if (j == 1 || ratio < temp) ratio = temp;
|
alpar@9
|
329 }
|
alpar@9
|
330 return ratio;
|
alpar@9
|
331 }
|
alpar@9
|
332
|
alpar@9
|
333 /***********************************************************************
|
alpar@9
|
334 * gm_iterate - perform iterative geometric mean scaling
|
alpar@9
|
335 *
|
alpar@9
|
336 * This routine performs iterative geometric mean scaling of rows and
|
alpar@9
|
337 * columns of the constraint matrix.
|
alpar@9
|
338 *
|
alpar@9
|
339 * The parameter it_max specifies the maximal number of iterations.
|
alpar@9
|
340 * Recommended value of it_max is 15.
|
alpar@9
|
341 *
|
alpar@9
|
342 * The parameter tau specifies a minimal improvement of the scaling
|
alpar@9
|
343 * "quality" on each iteration, 0 < tau < 1. It means than the scaling
|
alpar@9
|
344 * process continues while the following condition is satisfied:
|
alpar@9
|
345 *
|
alpar@9
|
346 * ratio[k] <= tau * ratio[k-1],
|
alpar@9
|
347 *
|
alpar@9
|
348 * where ratio = max |a[i,j]| / min |a[i,j]| is the scaling "quality"
|
alpar@9
|
349 * to be minimized, k is the iteration number. Recommended value of tau
|
alpar@9
|
350 * is 0.90. */
|
alpar@9
|
351
|
alpar@9
|
352 static void gm_iterate(glp_prob *lp, int it_max, double tau)
|
alpar@9
|
353 { int k, flag;
|
alpar@9
|
354 double ratio = 0.0, r_old;
|
alpar@9
|
355 /* if the scaling "quality" for rows is better than for columns,
|
alpar@9
|
356 the rows are scaled first; otherwise, the columns are scaled
|
alpar@9
|
357 first */
|
alpar@9
|
358 flag = (max_row_ratio(lp) > max_col_ratio(lp));
|
alpar@9
|
359 for (k = 1; k <= it_max; k++)
|
alpar@9
|
360 { /* save the scaling "quality" from previous iteration */
|
alpar@9
|
361 r_old = ratio;
|
alpar@9
|
362 /* determine the current scaling "quality" */
|
alpar@9
|
363 ratio = max_mat_aij(lp, 1) / min_mat_aij(lp, 1);
|
alpar@9
|
364 #if 0
|
alpar@9
|
365 xprintf("k = %d; ratio = %g\n", k, ratio);
|
alpar@9
|
366 #endif
|
alpar@9
|
367 /* if improvement is not enough, terminate scaling */
|
alpar@9
|
368 if (k > 1 && ratio > tau * r_old) break;
|
alpar@9
|
369 /* otherwise, perform another iteration */
|
alpar@9
|
370 gm_scaling(lp, flag);
|
alpar@9
|
371 }
|
alpar@9
|
372 return;
|
alpar@9
|
373 }
|
alpar@9
|
374
|
alpar@9
|
375 /***********************************************************************
|
alpar@9
|
376 * NAME
|
alpar@9
|
377 *
|
alpar@9
|
378 * scale_prob - scale problem data
|
alpar@9
|
379 *
|
alpar@9
|
380 * SYNOPSIS
|
alpar@9
|
381 *
|
alpar@9
|
382 * #include "glpscl.h"
|
alpar@9
|
383 * void scale_prob(glp_prob *lp, int flags);
|
alpar@9
|
384 *
|
alpar@9
|
385 * DESCRIPTION
|
alpar@9
|
386 *
|
alpar@9
|
387 * The routine scale_prob performs automatic scaling of problem data
|
alpar@9
|
388 * for the specified problem object. */
|
alpar@9
|
389
|
alpar@9
|
390 static void scale_prob(glp_prob *lp, int flags)
|
alpar@9
|
391 { static const char *fmt =
|
alpar@9
|
392 "%s: min|aij| = %10.3e max|aij| = %10.3e ratio = %10.3e\n";
|
alpar@9
|
393 double min_aij, max_aij, ratio;
|
alpar@9
|
394 xprintf("Scaling...\n");
|
alpar@9
|
395 /* cancel the current scaling effect */
|
alpar@9
|
396 glp_unscale_prob(lp);
|
alpar@9
|
397 /* report original scaling "quality" */
|
alpar@9
|
398 min_aij = min_mat_aij(lp, 1);
|
alpar@9
|
399 max_aij = max_mat_aij(lp, 1);
|
alpar@9
|
400 ratio = max_aij / min_aij;
|
alpar@9
|
401 xprintf(fmt, " A", min_aij, max_aij, ratio);
|
alpar@9
|
402 /* check if the problem is well scaled */
|
alpar@9
|
403 if (min_aij >= 0.10 && max_aij <= 10.0)
|
alpar@9
|
404 { xprintf("Problem data seem to be well scaled\n");
|
alpar@9
|
405 /* skip scaling, if required */
|
alpar@9
|
406 if (flags & GLP_SF_SKIP) goto done;
|
alpar@9
|
407 }
|
alpar@9
|
408 /* perform iterative geometric mean scaling, if required */
|
alpar@9
|
409 if (flags & GLP_SF_GM)
|
alpar@9
|
410 { gm_iterate(lp, 15, 0.90);
|
alpar@9
|
411 min_aij = min_mat_aij(lp, 1);
|
alpar@9
|
412 max_aij = max_mat_aij(lp, 1);
|
alpar@9
|
413 ratio = max_aij / min_aij;
|
alpar@9
|
414 xprintf(fmt, "GM", min_aij, max_aij, ratio);
|
alpar@9
|
415 }
|
alpar@9
|
416 /* perform equilibration scaling, if required */
|
alpar@9
|
417 if (flags & GLP_SF_EQ)
|
alpar@9
|
418 { eq_scaling(lp, max_row_ratio(lp) > max_col_ratio(lp));
|
alpar@9
|
419 min_aij = min_mat_aij(lp, 1);
|
alpar@9
|
420 max_aij = max_mat_aij(lp, 1);
|
alpar@9
|
421 ratio = max_aij / min_aij;
|
alpar@9
|
422 xprintf(fmt, "EQ", min_aij, max_aij, ratio);
|
alpar@9
|
423 }
|
alpar@9
|
424 /* round scale factors to nearest power of two, if required */
|
alpar@9
|
425 if (flags & GLP_SF_2N)
|
alpar@9
|
426 { int i, j;
|
alpar@9
|
427 for (i = 1; i <= lp->m; i++)
|
alpar@9
|
428 glp_set_rii(lp, i, round2n(glp_get_rii(lp, i)));
|
alpar@9
|
429 for (j = 1; j <= lp->n; j++)
|
alpar@9
|
430 glp_set_sjj(lp, j, round2n(glp_get_sjj(lp, j)));
|
alpar@9
|
431 min_aij = min_mat_aij(lp, 1);
|
alpar@9
|
432 max_aij = max_mat_aij(lp, 1);
|
alpar@9
|
433 ratio = max_aij / min_aij;
|
alpar@9
|
434 xprintf(fmt, "2N", min_aij, max_aij, ratio);
|
alpar@9
|
435 }
|
alpar@9
|
436 done: return;
|
alpar@9
|
437 }
|
alpar@9
|
438
|
alpar@9
|
439 /***********************************************************************
|
alpar@9
|
440 * NAME
|
alpar@9
|
441 *
|
alpar@9
|
442 * glp_scale_prob - scale problem data
|
alpar@9
|
443 *
|
alpar@9
|
444 * SYNOPSIS
|
alpar@9
|
445 *
|
alpar@9
|
446 * void glp_scale_prob(glp_prob *lp, int flags);
|
alpar@9
|
447 *
|
alpar@9
|
448 * DESCRIPTION
|
alpar@9
|
449 *
|
alpar@9
|
450 * The routine glp_scale_prob performs automatic scaling of problem
|
alpar@9
|
451 * data for the specified problem object.
|
alpar@9
|
452 *
|
alpar@9
|
453 * The parameter flags specifies scaling options used by the routine.
|
alpar@9
|
454 * Options can be combined with the bitwise OR operator and may be the
|
alpar@9
|
455 * following:
|
alpar@9
|
456 *
|
alpar@9
|
457 * GLP_SF_GM perform geometric mean scaling;
|
alpar@9
|
458 * GLP_SF_EQ perform equilibration scaling;
|
alpar@9
|
459 * GLP_SF_2N round scale factors to nearest power of two;
|
alpar@9
|
460 * GLP_SF_SKIP skip scaling, if the problem is well scaled.
|
alpar@9
|
461 *
|
alpar@9
|
462 * The parameter flags may be specified as GLP_SF_AUTO, in which case
|
alpar@9
|
463 * the routine chooses scaling options automatically. */
|
alpar@9
|
464
|
alpar@9
|
465 void glp_scale_prob(glp_prob *lp, int flags)
|
alpar@9
|
466 { if (flags & ~(GLP_SF_GM | GLP_SF_EQ | GLP_SF_2N | GLP_SF_SKIP |
|
alpar@9
|
467 GLP_SF_AUTO))
|
alpar@9
|
468 xerror("glp_scale_prob: flags = 0x%02X; invalid scaling option"
|
alpar@9
|
469 "s\n", flags);
|
alpar@9
|
470 if (flags & GLP_SF_AUTO)
|
alpar@9
|
471 flags = (GLP_SF_GM | GLP_SF_EQ | GLP_SF_SKIP);
|
alpar@9
|
472 scale_prob(lp, flags);
|
alpar@9
|
473 return;
|
alpar@9
|
474 }
|
alpar@9
|
475
|
alpar@9
|
476 /* eof */
|