1/* $Id: CoinPresolveUseless.cpp 1448 2011-06-19 15:34:41Z stefan $ */
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#include "CoinPresolveMatrix.hpp"
9#include "CoinPresolveUseless.hpp"
10#include "CoinHelperFunctions.hpp"
11
12#if PRESOLVE_DEBUG || PRESOLVE_CONSISTENCY
13#include "CoinPresolvePsdebug.hpp"
14#endif
15
16// WHAT HAPPENS IF COLS ARE DROPPED AS A RESULT??
17// should be like do_tighten.
18// not really - one could fix costed variables to appropriate bound.
19// ok, don't bother about it. If it is costed, it will be checked
20// when it is eliminated as an empty col; if it is costed in the
21// wrong direction, the problem is unbounded, otherwise it is pegged
22// at its bound. no special action need be taken here.
23const CoinPresolveAction *useless_constraint_action::presolve(CoinPresolveMatrix * prob,
24 const int *useless_rows,
25 int nuseless_rows,
26 const CoinPresolveAction *next)
27{
28 // may be modified by useless constraint
29 double *colels = prob->colels_;
30
31 // may be modified by useless constraint
32 int *hrow = prob->hrow_;
33
34 const CoinBigIndex *mcstrt = prob->mcstrt_;
35
36 // may be modified by useless constraint
37 int *hincol = prob->hincol_;
38
39 // double *clo = prob->clo_;
40 // double *cup = prob->cup_;
41
42 const double *rowels = prob->rowels_;
43 const int *hcol = prob->hcol_;
44 const CoinBigIndex *mrstrt = prob->mrstrt_;
45
46 // may be written by useless constraint
47 int *hinrow = prob->hinrow_;
48 // const int nrows = prob->nrows_;
49
50 double *rlo = prob->rlo_;
51 double *rup = prob->rup_;
52
53 action *actions = new action [nuseless_rows];
54
55# if PRESOLVE_DEBUG
56 std::cout << "Entering useless_constraint_action::presolve." << std::endl ;
57 presolve_check_sol(prob) ;
58# endif
59# if PRESOLVE_SUMMARY
60 printf("NUSELESS ROWS: %d\n", nuseless_rows);
61# endif
62
63 for (int i=0; i<nuseless_rows; ++i) {
64 int irow = useless_rows[i];
65 CoinBigIndex krs = mrstrt[irow];
66 CoinBigIndex kre = krs + hinrow[irow];
67 PRESOLVE_DETAIL_PRINT(printf("pre_useless %dR E\n",irow));
68
69 action *f = &actions[i];
70
71 f->row = irow;
72 f->ninrow = hinrow[irow];
73 f->rlo = rlo[irow];
74 f->rup = rup[irow];
75 f->rowcols = CoinCopyOfArray(&hcol[krs], hinrow[irow]);
76 f->rowels = CoinCopyOfArray(&rowels[krs], hinrow[irow]);
77
78 for (CoinBigIndex k=krs; k<kre; k++)
79 { presolve_delete_from_col(irow,hcol[k],mcstrt,hincol,hrow,colels) ;
80 if (hincol[hcol[k]] == 0)
81 { PRESOLVE_REMOVE_LINK(prob->clink_,hcol[k]) ; } }
82 hinrow[irow] = 0;
83 PRESOLVE_REMOVE_LINK(prob->rlink_,irow) ;
84
85 // just to make things squeeky
86 rlo[irow] = 0.0;
87 rup[irow] = 0.0;
88 }
89
90# if PRESOLVE_DEBUG
91 presolve_check_sol(prob) ;
92 std::cout << "Leaving useless_constraint_action::presolve." << std::endl ;
93# endif
94
95 next = new useless_constraint_action(nuseless_rows, actions, next);
96
97 return (next);
98}
99// Put constructors here
100useless_constraint_action::useless_constraint_action(int nactions,
101 const action *actions,
102 const CoinPresolveAction *next)
103 : CoinPresolveAction(next),
104 nactions_(nactions),
105 actions_(actions)
106{}
107useless_constraint_action::~useless_constraint_action()
108{
109 for (int i=0;i<nactions_;i++) {
110 deleteAction(actions_[i].rowcols, int *);
111 deleteAction(actions_[i].rowels, double *);
112 }
113 deleteAction(actions_, action *);
114}
115
116const char *useless_constraint_action::name() const
117{
118 return ("useless_constraint_action");
119}
120
121void useless_constraint_action::postsolve(CoinPostsolveMatrix *prob) const
122{
123 const action *const actions = actions_;
124 const int nactions = nactions_;
125
126 double *colels = prob->colels_;
127 int *hrow = prob->hrow_;
128 CoinBigIndex *mcstrt = prob->mcstrt_;
129 int *link = prob->link_;
130 int *hincol = prob->hincol_;
131
132 // double *rowduals = prob->rowduals_;
133 double *rowacts = prob->acts_;
134 const double *sol = prob->sol_;
135
136
137 CoinBigIndex &free_list = prob->free_list_;
138
139 double *rlo = prob->rlo_;
140 double *rup = prob->rup_;
141
142 for (const action *f = &actions[nactions-1]; actions<=f; f--) {
143
144 int irow = f->row;
145 int ninrow = f->ninrow;
146 const int *rowcols = f->rowcols;
147 const double *rowels = f->rowels;
148 double rowact = 0.0;
149
150 rup[irow] = f->rup;
151 rlo[irow] = f->rlo;
152
153 for (CoinBigIndex k=0; k<ninrow; k++) {
154 int jcol = rowcols[k];
155 // CoinBigIndex kk = mcstrt[jcol];
156
157 // append deleted row element to each col
158 {
159 CoinBigIndex kk = free_list;
160 assert(kk >= 0 && kk < prob->bulk0_) ;
161 free_list = link[free_list];
162 hrow[kk] = irow;
163 colels[kk] = rowels[k];
164 link[kk] = mcstrt[jcol];
165 mcstrt[jcol] = kk;
166 }
167
168 rowact += rowels[k] * sol[jcol];
169 hincol[jcol]++;
170 }
171# if PRESOLVE_CONSISTENCY
172 presolve_check_free_list(prob) ;
173# endif
174
175 // I don't know if this is always true
176 PRESOLVEASSERT(prob->getRowStatus(irow)==CoinPrePostsolveMatrix::basic);
177 // rcosts are unaffected since rowdual is 0
178
179 rowacts[irow] = rowact;
180 // leave until desctructor
181 //deleteAction(rowcols,int *);
182 //deleteAction(rowels,double *);
183 }
184
185 //deleteAction(actions_,action *);
186
187# if PRESOLVE_CONSISTENCY
188 presolve_check_threads(prob) ;
189# endif
190
191}
192