source: trunk/PresolveZeros.cpp @ 57

Last change on this file since 57 was 57, checked in by forrest, 18 years ago

Yet more changes for Visual C++

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