1 /* $Id: CoinPresolveZeros.cpp 2083 2019-01-06 19:38:09Z unxusr $ */
2 // Copyright (C) 2002, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5
6 #include <stdio.h>
7 #include <math.h>
8
9 #include "CoinHelperFunctions.hpp"
10 #include "CoinPresolveMatrix.hpp"
11 #include "CoinPresolveZeros.hpp"
12
13 #if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
14 #include "CoinPresolvePsdebug.hpp"
15 #endif
16
17 namespace { // begin unnamed file-local namespace
18
19 /*
20 Count the number of zeros in the columns listed in checkcols. Trim back
21 checkcols to just the columns with zeros.
22 */
count_col_zeros(int & ncheckcols,int * checkcols,const CoinBigIndex * mcstrt,const double * colels,const int * hincol)23 int count_col_zeros(int &ncheckcols, int *checkcols,
24 const CoinBigIndex *mcstrt, const double *colels,
25 const int *hincol)
26 {
27 int nzeros = 0;
28 int zeroCols = 0;
29
30 for (int ndx = 0; ndx < ncheckcols; ndx++) {
31 const int j = checkcols[ndx];
32 const CoinBigIndex kcs = mcstrt[j];
33 const CoinBigIndex kce = kcs + hincol[j];
34 int zerosj = 0;
35
36 for (CoinBigIndex kcol = kcs; kcol < kce; ++kcol) {
37 if (fabs(colels[kcol]) < ZTOLDP) {
38 zerosj++;
39 }
40 }
41 if (zerosj) {
42 checkcols[zeroCols++] = j;
43 nzeros += zerosj;
44 }
45 }
46 ncheckcols = zeroCols;
47 return (nzeros);
48 }
49
50 /*
51 Count the number of zeros. Intended for the case where all columns 0 ..
52 ncheckcols should be scanned. Typically ncheckcols is the number of columns
53 in the matrix. Leave a list of columns with explicit zeros at the front of
54 checkcols, with the count in ncheckcols.
55 */
count_col_zeros2(int & ncheckcols,int * checkcols,const CoinBigIndex * mcstrt,const double * colels,const int * hincol)56 int count_col_zeros2(int &ncheckcols, int *checkcols,
57 const CoinBigIndex *mcstrt, const double *colels,
58 const int *hincol)
59 {
60 int nzeros = 0;
61 int zeroCols = 0;
62
63 for (int j = 0; j < ncheckcols; j++) {
64 const CoinBigIndex kcs = mcstrt[j];
65 CoinBigIndex kce = kcs + hincol[j];
66
67 int zerosj = 0;
68 for (CoinBigIndex k = kcs; k < kce; ++k) {
69 if (fabs(colels[k]) < ZTOLDP) {
70 zerosj++;
71 }
72 }
73 if (zerosj) {
74 checkcols[zeroCols++] = j;
75 nzeros += zerosj;
76 }
77 }
78 ncheckcols = zeroCols;
79 return (nzeros);
80 }
81
82 /*
83 Searches the cols in checkcols for zero entries.
84 Creates a dropped_zero entry for each one; doesn't check for out-of-memory.
85 Returns number of zeros found.
86 */
drop_col_zeros(int ncheckcols,const int * checkcols,const CoinBigIndex * mcstrt,double * colels,int * hrow,int * hincol,presolvehlink * clink,dropped_zero * actions)87 int drop_col_zeros(int ncheckcols, const int *checkcols,
88 const CoinBigIndex *mcstrt, double *colels, int *hrow,
89 int *hincol, presolvehlink *clink,
90 dropped_zero *actions)
91 {
92 int nactions = 0;
93
94 /*
95 Physically remove explicit zeros. To maintain loose packing, move the
96 element at the end of the column into the empty space. Of course, that
97 element could also be zero, so recheck the position.
98 */
99 for (int i = 0; i < ncheckcols; i++) {
100 int col = checkcols[i];
101 const CoinBigIndex kcs = mcstrt[col];
102 CoinBigIndex kce = kcs + hincol[col];
103
104 #if PRESOLVE_DEBUG > 1
105 std::cout << " scanning column " << col << "...";
106 #endif
107
108 for (CoinBigIndex k = kcs; k < kce; ++k) {
109 if (fabs(colels[k]) < ZTOLDP) {
110 actions[nactions].col = col;
111 actions[nactions].row = hrow[k];
112
113 #if PRESOLVE_DEBUG > 2
114 std::cout << " (" << hrow[k] << "," << col << ") ";
115 #endif
116
117 nactions++;
118
119 kce--;
120 colels[k] = colels[kce];
121 hrow[k] = hrow[kce];
122 hincol[col]--;
123
124 --k;
125 }
126 }
127 #if PRESOLVE_DEBUG > 1
128 if (nactions)
129 std::cout << std::endl;
130 #endif
131
132 if (hincol[col] == 0)
133 PRESOLVE_REMOVE_LINK(clink, col);
134 }
135 return (nactions);
136 }
137
138 /*
139 Scan rows to remove explicit zeros.
140
141 This will, in general, scan a row once for each explicit zero in the row,
142 but will remove all zeros the first time through. It's tempting to try and
143 do something about this, but given the relatively small number of explicit
144 zeros created by presolve, the bookkeeping likely exceeds the gain.
145 */
drop_row_zeros(int nzeros,const dropped_zero * zeros,const CoinBigIndex * mrstrt,double * rowels,int * hcol,int * hinrow,presolvehlink * rlink)146 void drop_row_zeros(int nzeros, const dropped_zero *zeros,
147 const CoinBigIndex *mrstrt, double *rowels, int *hcol,
148 int *hinrow, presolvehlink *rlink)
149 {
150 for (int i = 0; i < nzeros; i++) {
151 int row = zeros[i].row;
152 const CoinBigIndex krs = mrstrt[row];
153 CoinBigIndex kre = krs + hinrow[row];
154
155 #if PRESOLVE_DEBUG > 2
156 std::cout
157 << " scanning row " << row << " for a(" << row << "," << zeros[i].col
158 << ") ...";
159 bool found = false;
160 #endif
161
162 for (CoinBigIndex k = krs; k < kre; k++) {
163 if (fabs(rowels[k]) < ZTOLDP) {
164
165 #if PRESOLVE_DEBUG > 2
166 std::cout << " (" << row << "," << hcol[k] << ") ";
167 found = true;
168 #endif
169
170 rowels[k] = rowels[kre - 1];
171 hcol[k] = hcol[kre - 1];
172 kre--;
173 hinrow[row]--;
174
175 --k;
176 }
177 }
178
179 #if PRESOLVE_DEBUG > 2
180 if (found)
181 std::cout
182 << " found; " << hinrow[row] << " coeffs remaining." << std::endl;
183 #endif
184
185 if (hinrow[row] == 0)
186 PRESOLVE_REMOVE_LINK(rlink, row);
187 }
188 }
189
190 } // end unnamed file-local namespace
191
192 /*
193 Scan the columns listed in checkcols for explicit zeros and eliminate them.
194
195 For the special case where all columns should be scanned (ncheckcols ==
196 prob->ncols_), there is no need to initialise checkcols.
197 */
198 const CoinPresolveAction
199 *
presolve(CoinPresolveMatrix * prob,int * checkcols,int ncheckcols,const CoinPresolveAction * next)200 drop_zero_coefficients_action::presolve(CoinPresolveMatrix *prob,
201 int *checkcols,
202 int ncheckcols,
203 const CoinPresolveAction *next)
204 {
205 double *colels = prob->colels_;
206 int *hrow = prob->hrow_;
207 CoinBigIndex *mcstrt = prob->mcstrt_;
208 int *hincol = prob->hincol_;
209 presolvehlink *clink = prob->clink_;
210 presolvehlink *rlink = prob->rlink_;
211
212 #if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
213 #if PRESOLVE_DEBUG > 0
214 std::cout
215 << "Entering drop_zero_action::presolve, " << ncheckcols
216 << " columns to scan." << std::endl;
217 #endif
218 presolve_consistent(prob);
219 presolve_links_ok(prob);
220 presolve_check_sol(prob);
221 presolve_check_nbasic(prob);
222 #endif
223
224 /*
225 Scan for zeros.
226 */
227 int nzeros;
228 if (ncheckcols == prob->ncols_) {
229 nzeros = count_col_zeros2(ncheckcols, checkcols, mcstrt, colels, hincol);
230 } else {
231 nzeros = count_col_zeros(ncheckcols, checkcols, mcstrt, colels, hincol);
232 }
233 #if PRESOLVE_DEBUG > 1
234 std::cout
235 << " drop_zero_action: " << nzeros << " zeros in " << ncheckcols
236 << " columns." << std::endl;
237 #endif
238 /*
239 Do we have zeros to remove? If so, get to it.
240 */
241 if (nzeros != 0) {
242 /*
243 We have zeros to remove. drop_col_zeros will scan the columns and remove
244 zeros, adding records of the dropped entries to zeros. The we need to clean
245 the row representation.
246 */
247 dropped_zero *zeros = new dropped_zero[nzeros];
248
249 nzeros = drop_col_zeros(ncheckcols, checkcols, mcstrt, colels,
250 hrow, hincol, clink, zeros);
251
252 double *rowels = prob->rowels_;
253 int *hcol = prob->hcol_;
254 CoinBigIndex *mrstrt = prob->mrstrt_;
255 int *hinrow = prob->hinrow_;
256 drop_row_zeros(nzeros, zeros, mrstrt, rowels, hcol, hinrow, rlink);
257 next = new drop_zero_coefficients_action(nzeros, zeros, next);
258 }
259
260 #if PRESOLVE_CONSISTENCY > 0 || PRESOLVE_DEBUG > 0
261 presolve_consistent(prob);
262 presolve_links_ok(prob);
263 presolve_check_sol(prob);
264 presolve_check_nbasic(prob);
265 #endif
266 #if PRESOLVE_DEBUG > 0 || COIN_PRESOLVE_TUNING > 0
267 std::cout
268 << "Leaving drop_zero_action::presolve, dropped " << nzeros
269 << " zeroes." << std::endl;
270 #endif
271
272 return (next);
273 }
274
275 /*
276 This wrapper initialises checkcols for the case where the entire matrix
277 should be scanned. Typically used from the presolve driver as part of final
278 cleanup.
279 */
280 const CoinPresolveAction
281 *
drop_zero_coefficients(CoinPresolveMatrix * prob,const CoinPresolveAction * next)282 drop_zero_coefficients(CoinPresolveMatrix *prob,
283 const CoinPresolveAction *next)
284 {
285 int ncheck = prob->ncols_;
286 int *checkcols = new int[ncheck];
287
288 if (prob->anyProhibited()) {
289 ncheck = 0;
290 for (int i = 0; i < prob->ncols_; i++)
291 if (!prob->colProhibited(i))
292 checkcols[ncheck++] = i;
293 }
294
295 const CoinPresolveAction *retval = drop_zero_coefficients_action::presolve(prob, checkcols, ncheck, next);
296
297 delete[] checkcols;
298 return (retval);
299 }
300
postsolve(CoinPostsolveMatrix * prob) const301 void drop_zero_coefficients_action::postsolve(CoinPostsolveMatrix *prob) const
302 {
303 const int nzeros = nzeros_;
304 const dropped_zero *const zeros = zeros_;
305
306 double *colels = prob->colels_;
307 int *hrow = prob->hrow_;
308 CoinBigIndex *mcstrt = prob->mcstrt_;
309 int *hincol = prob->hincol_;
310 CoinBigIndex *link = prob->link_;
311 CoinBigIndex &free_list = prob->free_list_;
312
313 for (const dropped_zero *z = &zeros[nzeros - 1]; zeros <= z; z--) {
314 const int i = z->row;
315 const int j = z->col;
316
317 CoinBigIndex k = free_list;
318 assert(k >= 0 && k < prob->bulk0_);
319 free_list = link[free_list];
320 hrow[k] = i;
321 colels[k] = 0.0;
322 link[k] = mcstrt[j];
323 mcstrt[j] = k;
324
325 hincol[j]++;
326 }
327
328 #if PRESOLVE_CONSISTENCY > 0
329 presolve_check_free_list(prob);
330 #endif
331 }
332
333 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
334 */
335