source: trunk/PresolveZeros.cpp @ 144

Last change on this file since 144 was 144, checked in by forrest, 17 years ago

Allow for nonlinear variables in presolve

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.3 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3
4#include <stdio.h>
5#include <math.h>
6
7#include "CoinHelperFunctions.hpp"
8#include "PresolveMatrix.hpp"
9#include "PresolveZeros.hpp"
10
11
12// searches the cols in checkcols for zero entries.
13// creates a dropped_zero entry for each one; doesn't check for out-of-memory.
14// returns number of zeros found.
15static int drop_col_zeros(int ncheckcols, int *checkcols,
16                           const CoinBigIndex *mcstrt, double *colels, int *hrow,
17                           int *hincol,
18                           dropped_zero *actions)
19{
20  typedef dropped_zero action;
21  int nactions = 0;
22  int i;
23
24  for (i=0; i<ncheckcols; i++) {
25    int col = checkcols[i];
26    CoinBigIndex kcs = mcstrt[col];
27    CoinBigIndex kce = mcstrt[col] + hincol[col];
28    CoinBigIndex k;
29
30    for (k=kcs; k<kce; ++k) {
31      if (fabs(colels[k]) < ZTOLDP) {
32        actions[nactions].col = col;
33        actions[nactions].row = hrow[k];
34        nactions++;
35
36#if     DEBUG_PRESOLVE
37        if (nactions == 1)
38          printf("ZEROS:  ");
39        printf("(%d,%d) ", hrow[k], col);
40#endif
41
42        colels[k] = colels[kce-1];
43        hrow[k]   = hrow[kce-1];
44        kce--;
45        hincol[col]--;
46
47        --k;    // redo this position
48      }
49    }
50  }
51
52#if     DEBUG_PRESOLVE
53  if (nactions)
54    printf("\n");
55#endif
56
57  return (nactions);
58}
59
60// very similar to col, but without the buffer and reads zeros
61// didn't bother to change the param names
62void drop_row_zeros(int nzeros, const dropped_zero *zeros,
63                    const CoinBigIndex *mcstrt, double *colels, int *hrow,
64                    int *hincol)
65{
66  int i;
67  for (i=0; i<nzeros; i++) {
68    int col = zeros[i].row;
69    CoinBigIndex kcs = mcstrt[col];
70    CoinBigIndex kce = mcstrt[col] + hincol[col];
71    CoinBigIndex k;
72
73    for (k=kcs; k<kce; k++) {
74      if (fabs(colels[k]) < ZTOLDP) {
75        colels[k] = colels[kce-1];
76        hrow[k]   = hrow[kce-1];
77        kce--;
78        hincol[col]--;
79
80        --k;    // redo this position
81      }
82    }
83  }
84}
85
86
87const PresolveAction *drop_zero_coefficients_action::presolve(PresolveMatrix *prob,
88                                                               int *checkcols,
89                                                               int ncheckcols,
90                                                               const PresolveAction *next)
91{
92  double *colels        = prob->colels_;
93  int *hrow             = prob->hrow_;
94  CoinBigIndex *mcstrt          = prob->mcstrt_;
95  int *hincol           = prob->hincol_;
96  int ncols             = prob->ncols_;
97
98  //  int i;
99  dropped_zero * zeros = new dropped_zero[ncols];
100
101  int nzeros = drop_col_zeros(ncheckcols, checkcols,
102                              mcstrt, colels, hrow, hincol,
103                              zeros);
104
105  if (nzeros == 0) {
106    delete [] zeros;
107    return (next);
108  } else {
109    double *rowels      = prob->rowels_;
110    int *hcol           = prob->hcol_;
111    CoinBigIndex *mrstrt                = prob->mrstrt_;
112    int *hinrow         = prob->hinrow_;
113    //    int nrows             = prob->nrows_;
114
115#if     PRESOLVE_SUMMARY
116    printf("NZEROS:  %d\n", nzeros);
117#endif
118
119    // make the row rep consistent
120    drop_row_zeros(nzeros, zeros, mrstrt, rowels, hcol, hinrow);
121
122    dropped_zero *zeros1 = new dropped_zero[nzeros];
123    ClpDisjointCopyN(zeros, nzeros, zeros1);
124
125    delete [] zeros;
126    return (new drop_zero_coefficients_action(nzeros, zeros1, next));
127  }
128}
129
130
131const PresolveAction *drop_zero_coefficients(PresolveMatrix *prob,
132                                              const PresolveAction *next)
133{
134  int ncheck            = prob->ncols_;
135  int *checkcols        = new int[ncheck];
136
137  if (!prob->anyProhibited()) {
138    for (int i=0; i<ncheck; i++)
139      checkcols[i] = i;
140  } else {
141    // some prohibited
142    ncheck=0;
143    for (int i=0; i<prob->ncols_; i++)
144      if (!prob->colProhibited(i))
145        checkcols[ncheck++] = i;
146  }
147
148  const PresolveAction *retval = drop_zero_coefficients_action::presolve(prob,
149                                                         checkcols, ncheck,
150                                                         next);
151  delete[]checkcols;
152  return (retval);
153}
154
155void drop_zero_coefficients_action::postsolve(PostsolveMatrix *prob) const
156{
157  const int nzeros      = nzeros_;
158  const dropped_zero *const zeros = zeros_;
159
160  double *colels        = prob->colels_;
161  int *hrow             = prob->hrow_;
162  CoinBigIndex *mcstrt          = prob->mcstrt_;
163  int *hincol           = prob->hincol_;
164  int *link             = prob->link_;
165  CoinBigIndex free_list                = prob->free_list_;
166
167  for (const dropped_zero *z = &zeros[nzeros-1]; zeros<=z; z--) {
168    int irow    = z->row;
169    int jcol    = z->col;
170
171    {
172      CoinBigIndex k = free_list;
173      free_list = link[free_list];
174      check_free_list(free_list);
175
176      hrow[k] = irow;
177      colels[k] = 0.0;
178      link[k] = mcstrt[jcol];
179      mcstrt[jcol] = k;
180    }
181   
182    hincol[jcol]++;
183  }
184
185  prob->free_list_ = free_list;
186} 
Note: See TracBrowser for help on using the repository browser.