BCP_matrix.cpp
Go to the documentation of this file.
1 // Copyright (C) 2000, International Business Machines
2 // Corporation and others. All Rights Reserved.
3 #include <numeric>
4 #include <algorithm>
5 #include <functional>
6 
7 using std::sort;
8 using std::copy;
9 using std::transform;
10 using std::bind2nd;
11 using std::partial_sum;
12 using std::rotate;
13 using std::fill;
14 
15 #include "BCP_error.hpp"
16 #include "BCP_matrix.hpp"
17 
18 //#############################################################################
19 
20 BCP_lp_relax::BCP_lp_relax(const BCP_lp_relax& mat) :
21  CoinPackedMatrix(mat),
22  _Objective(mat._Objective),
23  _ColLowerBound(mat._ColLowerBound),
24  _ColUpperBound(mat._ColUpperBound),
25  _RowLowerBound(mat._RowLowerBound),
26  _RowUpperBound(mat._RowUpperBound) {}
27 
28 //-----------------------------------------------------------------------------
29 
30 BCP_lp_relax&
31 BCP_lp_relax::operator=(const BCP_lp_relax& mat)
32 {
33  CoinPackedMatrix::operator=(mat);
34  _Objective = mat._Objective;
35  _ColLowerBound = mat._ColLowerBound;
36  _ColUpperBound = mat._ColUpperBound;
37  _RowLowerBound = mat._RowLowerBound;
38  _RowUpperBound = mat._RowUpperBound;
39  return *this;
40 }
41 
42 //-----------------------------------------------------------------------------
43 
44 void
45 BCP_lp_relax::reserve(const int MaxColNum, const int MaxRowNum,
46  const int MaxNonzeros)
47 {
48  CoinPackedMatrix::reserve(isColOrdered() ? MaxColNum : MaxRowNum,
49  MaxNonzeros);
50  _Objective.reserve(MaxColNum);
51  _ColLowerBound.reserve(MaxColNum);
52  _ColUpperBound.reserve(MaxColNum);
53  _RowLowerBound.reserve(MaxRowNum);
54  _RowUpperBound.reserve(MaxRowNum);
55 }
56 
57 //-----------------------------------------------------------------------------
58 
59 void
60 BCP_lp_relax::clear() {
61  CoinPackedMatrix::clear();
62  _ColLowerBound.clear(); _ColUpperBound.clear(); _Objective.clear();
63  _RowLowerBound.clear(); _RowUpperBound.clear();
64 }
65 
66 //-----------------------------------------------------------------------------
67 
68 void
69 BCP_lp_relax::copyOf(const CoinPackedMatrix& m,
70  const double* OBJ, const double* CLB, const double* CUB,
71  const double* RLB, const double* RUB)
72 {
73  clear();
74  const int colnum = m.getNumCols();
75  const int rownum = m.getNumRows();
76  _ColLowerBound.insert(_ColLowerBound.end(), CLB, CLB+colnum);
77  _ColUpperBound.insert(_ColUpperBound.end(), CUB, CUB+colnum);
78  _Objective.insert(_Objective.end(), OBJ, OBJ+colnum);
79  _RowLowerBound.insert(_RowLowerBound.end(), RLB, RLB+rownum);
80  _RowUpperBound.insert(_RowUpperBound.end(), RUB, RUB+rownum);
81 
82  CoinPackedMatrix::copyOf(m);
83 }
84 
85 //-----------------------------------------------------------------------------
86 
87 void
88 BCP_lp_relax::assign(CoinPackedMatrix& m,
89  double*& OBJ, double*& CLB, double*& CUB,
90  double*& RLB, double*& RUB)
91 {
92  clear();
93  const int colnum = m.getNumCols();
94  const int rownum = m.getNumRows();
95  _ColLowerBound.insert(_ColLowerBound.end(), CLB, CLB+colnum);
96  delete[] CLB;
97  CLB = 0;
98  _ColUpperBound.insert(_ColUpperBound.end(), CUB, CUB+colnum);
99  delete[] CUB;
100  CUB = 0;
101  _Objective.insert(_Objective.end(), OBJ, OBJ+colnum);
102  delete[] OBJ;
103  OBJ = 0;
104  _RowLowerBound.insert(_RowLowerBound.end(), RLB, RLB+rownum);
105  delete[] RLB;
106  RLB = 0;
107  _RowUpperBound.insert(_RowUpperBound.end(), RUB, RUB+rownum);
108  delete[] RUB;
109  RUB = 0;
110 
111  CoinPackedMatrix::gutsOfDestructor();
112  CoinPackedMatrix::swap(m);
113 }
114 
115 //-----------------------------------------------------------------------------
116 #if 0
117 void
118 BCP_lp_relax::add_col_set(const BCP_col_set& Cols)
119 {
120  rightAppendPackedMatrix(Cols);
121  _Objective.append(Cols.Objective());
122  _ColLowerBound.append(Cols.LowerBound());
123  _ColUpperBound.append(Cols.UpperBound());
124 }
125 
126 //-----------------------------------------------------------------------------
127 
128 void
129 BCP_lp_relax::add_row_set(const BCP_row_set& Rows)
130 {
131  bottomAppendPackedMatrix(Rows);
132  _RowLowerBound.append(Rows.LowerBound());
133  _RowUpperBound.append(Rows.UpperBound());
134 }
135 #endif
136 //-----------------------------------------------------------------------------
137 
138 void
139 BCP_lp_relax::erase_col_set(const BCP_vec<int>& pos)
140 {
141  deleteCols(pos.size(), pos.begin());
142  _Objective.erase_by_index(pos);
143  _ColLowerBound.erase_by_index(pos);
144  _ColUpperBound.erase_by_index(pos);
145 }
146 
147 //-----------------------------------------------------------------------------
148 
149 void
150 BCP_lp_relax::erase_row_set(const BCP_vec<int>& pos)
151 {
152  deleteRows(pos.size(), pos.begin());
153  _RowLowerBound.erase_by_index(pos);
154  _RowUpperBound.erase_by_index(pos);
155 }
156 
157 //-----------------------------------------------------------------------------
158 #if 0
159 double
160 BCP_lp_relax::dot_product_col(const int index,
161  const BCP_vec<double>& col) const
162 {
163  if (! isColOrdered())
164  throw BCP_fatal_error("\
165 LP: dot_product_col() called for a row ordered matrix...\n");
166  return dot_product(index, col);
167 }
168 
169 double
170 BCP_lp_relax::dot_product_col(const int index,
171  const double* col) const
172 {
173  if (_Ordering != ColWise)
174  throw BCP_fatal_error("\
175 LP: dot_product_col() called for a row ordered matrix...\n");
176  return dot_product(index, col);
177 }
178 
179 //-----------------------------------------------------------------------------
180 
181 double
182 BCP_lp_relax::dot_product_row(const int index,
183  const BCP_vec<double>& row) const
184 {
185  if (_Ordering != RowWise)
186  throw BCP_fatal_error("\
187 LP: dot_product_col() called for a col ordered matrix...\n");
188  return dot_product(index, row);
189 }
190 
191 double
192 BCP_lp_relax::dot_product_row(const int index,
193  const double* row) const
194 {
195  if (_Ordering != RowWise)
196  throw BCP_fatal_error("\
197 LP: dot_product_col() called for a col ordered matrix...\n");
198  return dot_product(index, row);
199 }
200 #endif
201 
202 //#############################################################################
203 
204 void
205 BCP_lp_relax::BCP_createColumnOrderedMatrix(BCP_vec<BCP_row*>& rows,
206  BCP_vec<double>& CLB,
207  BCP_vec<double>& CUB,
208  BCP_vec<double>& OBJ)
209 {
210  int i, nzcnt = 0;
211  const int rownum = rows.size();
212 
213  for (i = 0; i < rownum; ++i)
214  nzcnt += rows[i]->getNumElements();
215  CoinPackedMatrix::clear();
216  CoinPackedMatrix::reserve(rownum, nzcnt);
217  CoinPackedMatrix::setDimensions(0, CLB.size());
218  _RowLowerBound.reserve(rownum);
219  _RowUpperBound.reserve(rownum);
220  for (i = 0; i < rownum; ++i) {
221  BCP_row* row = rows[i];
222  CoinPackedMatrix::appendMajorVector(*row);
223  _RowLowerBound.unchecked_push_back(row->LowerBound());
224  _RowUpperBound.unchecked_push_back(row->UpperBound());
225  }
226  _ColLowerBound.swap(CLB);
227  _ColUpperBound.swap(CUB);
228  _Objective.swap(OBJ);
229 }
230 
231 //-----------------------------------------------------------------------------
232 
233 BCP_lp_relax::BCP_lp_relax(BCP_vec<BCP_row*>& rows,
234  BCP_vec<double>& CLB, BCP_vec<double>& CUB,
235  BCP_vec<double>& OBJ) :
236  CoinPackedMatrix(false /*rowordered*/, 0, 0, 0, NULL, NULL, NULL, NULL)
237 {
238  BCP_createColumnOrderedMatrix(rows, CLB, CUB, OBJ);
239 }
240 
241 //-----------------------------------------------------------------------------
242 
243 BCP_lp_relax::BCP_lp_relax(BCP_vec<BCP_row*>& rows,
244  BCP_vec<double>& CLB, BCP_vec<double>& CUB,
245  BCP_vec<double>& OBJ,
246  double extra_gap, double extra_major) :
247  CoinPackedMatrix(false /*rowordered*/, 0, 0, 0, NULL, NULL, NULL, NULL)
248 {
249  setExtraGap(extra_gap);
250  setExtraMajor(extra_major);
251  BCP_createColumnOrderedMatrix(rows, CLB, CUB, OBJ);
252 }
253 
254 //#############################################################################
255 
256 void
257 BCP_lp_relax::BCP_createRowOrderedMatrix(BCP_vec<BCP_col*>& cols,
258  BCP_vec<double>& RLB,
259  BCP_vec<double>& RUB)
260 {
261  int i, nzcnt = 0;
262  const int colnum = cols.size();
263 
264  for (i = 0; i < colnum; ++i)
265  nzcnt += cols[i]->getNumElements();
266  CoinPackedMatrix::clear();
267  CoinPackedMatrix::reserve(colnum, nzcnt);
268  CoinPackedMatrix::setDimensions(RLB.size(), 0);
269  _ColLowerBound.reserve(colnum);
270  _ColUpperBound.reserve(colnum);
271  _Objective.reserve(colnum);
272  for (i = 0; i < colnum; ++i) {
273  BCP_col* col = cols[i];
274  CoinPackedMatrix::appendMajorVector(*col);
275  _ColLowerBound.unchecked_push_back(col->LowerBound());
276  _ColUpperBound.unchecked_push_back(col->UpperBound());
277  _Objective.unchecked_push_back(col->Objective());
278  }
279  _RowLowerBound.swap(RLB);
280  _RowUpperBound.swap(RUB);
281 }
282 
283 //-----------------------------------------------------------------------------
284 
285 BCP_lp_relax::BCP_lp_relax(BCP_vec<BCP_col*>& cols,
286  BCP_vec<double>& RLB, BCP_vec<double>& RUB) :
287  CoinPackedMatrix(true /*colordered*/, 0, 0, 0, NULL, NULL, NULL, NULL)
288 {
289  BCP_createRowOrderedMatrix(cols, RLB, RUB);
290 }
291 
292 //-----------------------------------------------------------------------------
293 
294 BCP_lp_relax::BCP_lp_relax(BCP_vec<BCP_col*>& cols,
295  BCP_vec<double>& RLB, BCP_vec<double>& RUB,
296  double extra_gap, double extra_major) :
297  CoinPackedMatrix(true /*colordered*/, 0, 0, 0, NULL, NULL, NULL, NULL)
298 {
299  setExtraGap(extra_gap);
300  setExtraMajor(extra_major);
301  BCP_createRowOrderedMatrix(cols, RLB, RUB);
302 }
303 
304 //-----------------------------------------------------------------------------
305 
306 BCP_lp_relax::BCP_lp_relax(const bool colordered,
307  const BCP_vec<int>& VB, const BCP_vec<int>& EI,
308  const BCP_vec<double>& EV,
309  const BCP_vec<double>& OBJ,
310  const BCP_vec<double>& CLB,
311  const BCP_vec<double>& CUB,
312  const BCP_vec<double>& RLB,
313  const BCP_vec<double>& RUB) :
314  CoinPackedMatrix(),
315  _Objective(OBJ), _ColLowerBound(CLB), _ColUpperBound(CUB),
316  _RowLowerBound(RLB), _RowUpperBound(RUB)
317 {
318  const int minor = colordered ? RLB.size() : CLB.size();
319  const int major = colordered ? CLB.size() : RLB.size();
320  CoinPackedMatrix::copyOf(colordered, minor, major, EI.size(),
321  EV.begin(), EI.begin(), VB.begin(), 0);
322 }
323 
324 //-----------------------------------------------------------------------------
325 
326 BCP_lp_relax::BCP_lp_relax(const bool colordered,
327  const int rownum, const int colnum, const int nznum,
328  int*& VB, int*& EI, double*& EV,
329  double*& OBJ, double*& CLB, double*& CUB,
330  double*& RLB, double*& RUB) :
331  CoinPackedMatrix(),
332  _Objective(OBJ, OBJ+colnum),
333  _ColLowerBound(CLB, CLB+colnum), _ColUpperBound(CUB, CUB+colnum),
334  _RowLowerBound(RLB, RLB+rownum), _RowUpperBound(RUB, RUB+rownum)
335 {
336  const int minor = colordered ? rownum : colnum;
337  const int major = colordered ? colnum : rownum;
338  int * nullp = 0;
339  CoinPackedMatrix::assignMatrix(colordered, minor, major, nznum,
340  EV, EI, VB, nullp);
341  delete[] OBJ; OBJ = 0;
342  delete[] CLB; CLB = 0;
343  delete[] CUB; CUB = 0;
344  delete[] RLB; RLB = 0;
345  delete[] RUB; RUB = 0;
346 }
BCP_row::LowerBound
double LowerBound() const
Return the lower bound.
Definition: BCP_matrix.hpp:167
BCP_lp_relax::_ColUpperBound
BCP_vec< double > _ColUpperBound
The upper bounds on the variables.
Definition: BCP_matrix.hpp:276
BCP_col
This class holds a column in a compressed form.
Definition: BCP_matrix.hpp:26
BCP_lp_relax::erase_row_set
void erase_row_set(const BCP_vec< int > &pos)
Remove the rows whose indices are listed in pos from the LP relaxation.
Definition: BCP_matrix.cpp:150
BCP_lp_relax::_RowUpperBound
BCP_vec< double > _RowUpperBound
The upper bounds on the cuts.
Definition: BCP_matrix.hpp:280
BCP_col::LowerBound
double LowerBound() const
Return the lower bound.
Definition: BCP_matrix.hpp:46
BCP_lp_relax::rownum
size_t rownum() const
The number of rows.
Definition: BCP_matrix.hpp:290
BCP_col::UpperBound
double UpperBound() const
Return the upper bound.
Definition: BCP_matrix.hpp:48
Couenne::pos
pos
position where the operator should be printed when printing the expression
Definition: CouenneTypes.hpp:30
BCP_vec::clear
void clear()
Delete every entry.
Definition: BCP_vector_general.hpp:318
BCP_lp_relax::clear
void clear()
Clear the LP relaxation.
Definition: BCP_matrix.cpp:60
BCP_lp_relax::colnum
size_t colnum() const
The number of columns.
Definition: BCP_matrix.hpp:288
BCP_lp_relax::BCP_lp_relax
BCP_lp_relax(const bool colordered=true)
Create an empty LP relaxation with given ordering.
Definition: BCP_matrix.hpp:377
BCP_vec::begin
iterator begin()
Return an iterator to the beginning of the object.
Definition: BCP_vector.hpp:99
BCP_lp_relax::BCP_createRowOrderedMatrix
void BCP_createRowOrderedMatrix(BCP_vec< BCP_col * > &cols, BCP_vec< double > &RLB, BCP_vec< double > &RUB)
Definition: BCP_matrix.cpp:257
BCP_vec::reserve
void reserve(const size_t n)
Reallocate the object to make space for n entries.
Definition: BCP_vector_general.hpp:112
BCP_lp_relax::erase_col_set
void erase_col_set(const BCP_vec< int > &pos)
Remove the columns whose indices are listed in pos from the LP relaxation.
Definition: BCP_matrix.cpp:139
BCP_lp_relax::copyOf
void copyOf(const CoinPackedMatrix &m, const double *OBJ, const double *CLB, const double *CUB, const double *RLB, const double *RUB)
Set up the LP relaxation by making a copy of the arguments.
Definition: BCP_matrix.cpp:69
BCP_lp_relax::_ColLowerBound
BCP_vec< double > _ColLowerBound
The lower bounds on the variables.
Definition: BCP_matrix.hpp:274
BCP_vec::erase_by_index
void erase_by_index(const BCP_vec< int > &positions)
Erase the entries indexed by indices.
Definition: BCP_vector_general.hpp:414
BCP_col::Objective
double Objective() const
Return the objective coefficient.
Definition: BCP_matrix.hpp:44
BCP_vec::insert
void insert(iterator position, const void *first, const size_t num)
Insert num entries starting from memory location first into the vector from position pos...
Definition: BCP_vector_general.hpp:176
BCP_lp_relax::assign
void assign(CoinPackedMatrix &m, double *&OBJ, double *&CLB, double *&CUB, double *&RLB, double *&RUB)
Set up the LP relaxation by taking over the pointers in the arguments.
Definition: BCP_matrix.cpp:88
BCP_lp_relax::_Objective
BCP_vec< double > _Objective
The objective coefficients of the variables.
Definition: BCP_matrix.hpp:272
BCP_error.hpp
BCP_fatal_error
Currently there isn&#39;t any error handling in BCP.
Definition: BCP_error.hpp:20
BCP_row::UpperBound
double UpperBound() const
Return the upper bound.
Definition: BCP_matrix.hpp:169
BCP_vec::size
size_t size() const
Return the current number of entries.
Definition: BCP_vector.hpp:116
BCP_vec::end
iterator end()
Return an iterator to the end of the object.
Definition: BCP_vector.hpp:104
BCP_vec< int >
BCP_vec::unchecked_push_back
void unchecked_push_back(const_reference x)
Append x to the end of the vector.
Definition: BCP_vector_general.hpp:308
BCP_lp_relax::operator=
BCP_lp_relax & operator=(const BCP_lp_relax &mat)
Copy the content of x into the LP relaxation.
Definition: BCP_matrix.cpp:31
m
void fint * m
Definition: BonBqpdSolver.cpp:27
BCP_lp_relax::_RowLowerBound
BCP_vec< double > _RowLowerBound
The lower bounds on the cuts.
Definition: BCP_matrix.hpp:278
BCP_lp_relax::reserve
void reserve(const int MaxColNum, const int MaxRowNum, const int MaxNonzeros)
Reserve space in the LP relaxation for at least MaxColNum columns, MaxRowNum rows and MaxNonzeros non...
Definition: BCP_matrix.cpp:45
BCP_vec::append
void append(const BCP_vec< T > &x)
Append the entries in x to the end of the vector.
Definition: BCP_vector.hpp:169
BCP_vec::swap
void swap(BCP_vec< T > &x)
Exchange the contents of the object with that of x.
Definition: BCP_vector_general.hpp:124
BCP_lp_relax
An object of type BCP_lp_relax holds the description of an lp relaxation.
Definition: BCP_matrix.hpp:267
BCP_matrix.hpp
BCP_lp_relax::BCP_createColumnOrderedMatrix
void BCP_createColumnOrderedMatrix(BCP_vec< BCP_row * > &rows, BCP_vec< double > &CLB, BCP_vec< double > &CUB, BCP_vec< double > &OBJ)
Definition: BCP_matrix.cpp:205
BCP_row
This class holds a row in a compressed form.
Definition: BCP_matrix.hpp:152
Generated by   doxygen 1.8.5