source: trunk/PresolveZeros.cpp @ 61

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

Still trying to clean up VC++ and min/max

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.1 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 ncols             = prob->ncols_;
135  int *checkcols        = new int[ncols];
136
137  for (int i=0; i<ncols; i++)
138    checkcols[i] = i;
139
140  const PresolveAction *retval = drop_zero_coefficients_action::presolve(prob,
141                                                         checkcols, ncols,
142                                                         next);
143  delete[]checkcols;
144  return (retval);
145}
146
147void drop_zero_coefficients_action::postsolve(PostsolveMatrix *prob) const
148{
149  const int nzeros      = nzeros_;
150  const dropped_zero *const zeros = zeros_;
151
152  double *colels        = prob->colels_;
153  int *hrow             = prob->hrow_;
154  CoinBigIndex *mcstrt          = prob->mcstrt_;
155  int *hincol           = prob->hincol_;
156  int *link             = prob->link_;
157  CoinBigIndex free_list                = prob->free_list_;
158
159  for (const dropped_zero *z = &zeros[nzeros-1]; zeros<=z; z--) {
160    int irow    = z->row;
161    int jcol    = z->col;
162
163    {
164      CoinBigIndex k = free_list;
165      free_list = link[free_list];
166      check_free_list(free_list);
167
168      hrow[k] = irow;
169      colels[k] = 0.0;
170      link[k] = mcstrt[jcol];
171      mcstrt[jcol] = k;
172    }
173   
174    hincol[jcol]++;
175  }
176
177  prob->free_list_ = free_list;
178} 
Note: See TracBrowser for help on using the repository browser.