CoinUtils 2.11.4
Loading...
Searching...
No Matches
CoinSimpFactorization.hpp
Go to the documentation of this file.
1/* $Id$ */
2// Copyright (C) 2008, 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/*
7 This is a simple factorization of the LP Basis
8 */
9#ifndef CoinSimpFactorization_H
10#define CoinSimpFactorization_H
11
12#include <iostream>
13#include <string>
14#include <cassert>
15#include "CoinTypes.hpp"
16#include "CoinIndexedVector.hpp"
19
22public:
23 double *rowMax;
25 int *prevRow;
26 int *nextRow;
30 int *newCols;
31 //constructor
32 FactorPointers(int numRows, int numCols, int *UrowLengths_, int *UcolLengths_);
33 // destructor
35};
36
38 friend void CoinSimpFactorizationUnitTest(const std::string &mpsDir);
39
40public:
47
53 virtual CoinOtherFactorization *clone() const;
55
59 virtual void getAreas(int numberRows,
60 int numberColumns,
61 int maximumL,
62 int maximumU);
63
65 virtual void preProcess();
71 virtual int factor();
73 virtual void postProcess(const int *sequence, int *pivotVariable);
75 virtual void makeNonSingular(int *sequence, int numberColumns);
77
81 virtual inline int numberElements() const
82 {
84 }
86 double maximumCoefficient() const;
88
91
99 virtual int replaceColumn(CoinIndexedVector *regionSparse,
100 int pivotRow,
101 double pivotCheck,
102 bool checkBeforeModifying = false,
103 double acceptablePivot = 1.0e-8);
105
116 virtual int updateColumnFT(CoinIndexedVector *regionSparse,
117 CoinIndexedVector *regionSparse2,
118 bool noPermute = false);
119
122 virtual int updateColumn(CoinIndexedVector *regionSparse,
123 CoinIndexedVector *regionSparse2,
124 bool noPermute = false) const;
126 virtual int updateTwoColumnsFT(CoinIndexedVector *regionSparse1,
127 CoinIndexedVector *regionSparse2,
128 CoinIndexedVector *regionSparse3,
129 bool noPermute = false);
131 int upColumn(CoinIndexedVector *regionSparse,
132 CoinIndexedVector *regionSparse2,
133 bool noPermute = false, bool save = false) const;
138 virtual int updateColumnTranspose(CoinIndexedVector *regionSparse,
139 CoinIndexedVector *regionSparse2) const;
142 CoinIndexedVector *regionSparse2) const;
144
145
150 inline void clearArrays()
151 {
153 }
155 inline int *indices() const
156 {
157 return reinterpret_cast< int * >(elements_ + numberRows_ * numberRows_);
158 }
160 virtual inline int *permute() const
161 {
162 return pivotRow_;
163 }
165
172
174 void factorize(int numberOfRows,
175 int numberOfColumns,
176 const int colStarts[],
177 const int indicesRow[],
178 const double elements[]);
186 int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack);
188 int findPivotShCol(FactorPointers &pointers, int &r, int &s);
190 int findPivotSimp(FactorPointers &pointers, int &r, int &s);
192 void GaussEliminate(FactorPointers &pointers, int &r, int &s);
194 int findShortRow(const int column, const int length, int &minRow,
195 int &minRowLength, FactorPointers &pointers);
197 int findShortColumn(const int row, const int length, int &minCol,
198 int &minColLength, FactorPointers &pointers);
200 double findMaxInRrow(const int row, FactorPointers &pointers);
202 void pivoting(const int pivotRow, const int pivotColumn,
203 const double invPivot, FactorPointers &pointers);
205 void updateCurrentRow(const int pivotRow, const int row,
206 const double multiplier, FactorPointers &pointers,
207 int &newNonZeros);
211 void increaseRowSize(const int row, const int newSize);
213 void increaseColSize(const int column, const int newSize, const bool b);
215 void enlargeUrow(const int numNewElements);
217 void enlargeUcol(const int numNewElements, const bool b);
219 int findInRow(const int row, const int column);
221 int findInColumn(const int column, const int row);
223 void removeRowFromActSet(const int row, FactorPointers &pointers);
225 void removeColumnFromActSet(const int column, FactorPointers &pointers);
233 void Lxeqb(double *b) const;
235 void Lxeqb2(double *b1, double *b2) const;
237 void Uxeqb(double *b, double *sol) const;
239 void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const;
241 void xLeqb(double *b) const;
243 void xUeqb(double *b, double *sol) const;
245 int LUupdate(int newBasicCol);
247 void newEta(int row, int numNewElements);
251 void Hxeqb(double *b) const;
253 void Hxeqb2(double *b1, double *b2) const;
255 void xHeqb(double *b) const;
257 void ftran(double *b, double *sol, bool save) const;
259 void ftran2(double *b1, double *sol1, double *b2, double *sol2) const;
261 void btran(double *b, double *sol) const;
263
265protected:
268 int checkPivot(double saveFromU, double oldPivot) const;
270protected:
276 double *workArea2_;
278 double *workArea3_;
283
285 double *auxVector_;
288
290 double *vecKeep_;
294 mutable int keepSize_;
295
301 double *Lrows_;
308
314 double *Lcolumns_;
321
326#ifdef COIN_SIMP_CAPACITY
328 int *UrowCapacities_;
329#endif
331 double *Urows_;
346
351#ifdef COIN_SIMP_CAPACITY
353 int *UcolCapacities_;
354#endif
356 double *Ucolumns_;
373
376
389
399 double *Eta_;
408
416 double maxU_;
420 double maxA_;
428};
429#endif
430
431/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
432*/
Abstract base class which also has some scalars so can be used from Dense or Simp.
int numberPivots_
Number pivots since last factorization.
int numberRows_
Number of Rows in factorization.
virtual CoinFactorizationDouble * elements() const
Returns array to put basis elements in.
CoinFactorizationDouble * elements_
Elements of factorization and updates length is maxR*maxR+maxSpace will always be long enough so can ...
int numberColumns_
Number of Columns in factorization.
int numberRows() const
Number of Rows after factorization.
virtual int * pivotRow() const
Returns pivot row.
int numberColumns() const
Total number of columns in factorization.
Sparse Matrix Base Class.
friend void CoinSimpFactorizationUnitTest(const std::string &mpsDir)
int keepSize_
number of nonzeros
int * UrowInd_
Indices in the rows of U.
int findInRow(const int row, const int column)
finds a given row in a column
void increaseColSize(const int column, const int newSize, const bool b)
allocates more space for a column of U
void enlargeUrow(const int numNewElements)
allocates more space for rows of U
void copyRowPermutations()
makes a copy of row permutations
int UcolEnd_
last used position in Ucolumns_
int * LcolLengths_
Lengths of the columns of L.
int * secRowPosition_
position of row after permutation during LUupdate
void increaseRowSize(const int row, const int newSize)
allocates more space for a row of U
int * colSlack_
indicator of slack variables
void removeRowFromActSet(const int row, FactorPointers &pointers)
declares a row inactive
int * rowPosition_
position of row after permutation
int findShortRow(const int column, const int length, int &minRow, int &minRowLength, FactorPointers &pointers)
finds short row that intersects a given column
int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack)
finds a pivot element using Markowitz count
virtual ~CoinSimpFactorization()
Destructor.
virtual int numberElements() const
Total number of elements in factorization.
int * EtaInd_
columns of eta vectors
int firstColInU_
first column in U
virtual void makeNonSingular(int *sequence, int numberColumns)
Makes a non-singular basis by replacing variables.
virtual int updateColumn(CoinIndexedVector *regionSparse, CoinIndexedVector *regionSparse2, bool noPermute=false) const
This version has same effect as above with FTUpdate==false so number returned is always >=0.
virtual void preProcess()
PreProcesses column ordered copy of basis.
void copyUbyColumns()
copies U by columns
int LUupdate(int newBasicCol)
updates factorization after a Simplex iteration
int EtaMaxCap_
Capacity of Eta_.
void xLeqb(double *b) const
solves x L = b
double maxGrowth_
bound on the growth rate
int * colPosition_
position of column after permutation
virtual int factor()
Does most of factorization returning status 0 - OK -99 - needs more memory -1 - singular - use number...
double * invOfPivots_
inverse values of the elements of diagonal of U
void initialSomeNumbers()
initializes some numbers
CoinSimpFactorization & operator=(const CoinSimpFactorization &other)
= copy
int maxEtaRows_
maximum number of eta vectors
int * UcolInd_
Indices in the columns of U.
void copyLbyRows()
copies L by rows
void Hxeqb(double *b) const
solves H x = b, where H is a product of eta matrices
int * prevRowInU_
previous row in U
void gutsOfDestructor()
The real work of destructor.
int * nextRowInU_
next row in U
void enlargeUcol(const int numNewElements, const bool b)
allocates more space for columns of U
double * vecKeep_
vector to keep for LUupdate
int * indVector_
array of indices
int * auxInd_
auxiliary vector
double updateTol_
maximum size for the diagonal of U after update
int * secRowOfU_
permutations of rows during LUupdate
int * nextColInU_
next column in U
int findShortColumn(const int row, const int length, int &minCol, int &minColLength, FactorPointers &pointers)
finds short column that intersects a given row
int minIncrease_
minimum storage increase
double * Lcolumns_
L by columns.
virtual int updateTwoColumnsFT(CoinIndexedVector *regionSparse1, CoinIndexedVector *regionSparse2, CoinIndexedVector *regionSparse3, bool noPermute=false)
does FTRAN on two columns
int * LcolStarts_
Starts of the columns of L.
double * Eta_
elements of eta vectors
int UcolMaxCap_
maximum capacity of Ucolumns_
int * EtaLengths_
Lengths of eta vectors.
int * prevColInU_
previous column in U
void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const
same as above but with two rhs
virtual int updateColumnFT(CoinIndexedVector *regionSparse, CoinIndexedVector *regionSparse2, bool noPermute=false)
Updates one column (FTRAN) from regionSparse2 Tries to do FT update number returned is negative if no...
int * indices() const
Returns array to put basis indices in.
int * LcolInd_
indices in the columns of L
int upColumn(CoinIndexedVector *regionSparse, CoinIndexedVector *regionSparse2, bool noPermute=false, bool save=false) const
does updatecolumn if save==true keeps column for replace column
virtual CoinOtherFactorization * clone() const
Clone.
bool doSuhlHeuristic_
do Shul heuristic
virtual int replaceColumn(CoinIndexedVector *regionSparse, int pivotRow, double pivotCheck, bool checkBeforeModifying=false, double acceptablePivot=1.0e-8)
Replaces one Column to basis, returns 0=OK, 1=Probably OK, 2=singular, 3=no room If checkBeforeModify...
double * auxVector_
auxiliary vector
int upColumnTranspose(CoinIndexedVector *regionSparse, CoinIndexedVector *regionSparse2) const
does updateColumnTranspose, the other is a wrapper
void GaussEliminate(FactorPointers &pointers, int &r, int &s)
does Gauss elimination
void gutsOfCopy(const CoinSimpFactorization &other)
The real work of copy.
void gutsOfInitialize()
The real work of constructor.
int numberSlacks_
number of slacks in basis
void xHeqb(double *b) const
solves x H = b
int EtaSize_
number of elements in Eta_
int * rowOfU_
permutations of rows
int * LrowStarts_
Starts of the rows of L.
void factorize(int numberOfRows, int numberOfColumns, const int colStarts[], const int indicesRow[], const double elements[])
calls factorization
int mainLoopFactor(FactorPointers &pointers)
main loop of factorization
int * UcolStarts_
Starts of the columns of U.
int * UrowStarts_
Starts of the rows of U.
double maximumCoefficient() const
Returns maximum absolute value in factorization.
double * denseVector_
work array (should be initialized to zero)
void Uxeqb(double *b, double *sol) const
solves U x = b
double findMaxInRrow(const int row, FactorPointers &pointers)
finds maximum absolute value in a row
void increaseLsize()
allocates more space for L
void ftran(double *b, double *sol, bool save) const
does FTRAN
int firstNumberSlacks_
number of slacks in irst basis
int findPivotSimp(FactorPointers &pointers, int &r, int &s)
finds a pivot in the first column available
CoinSimpFactorization(const CoinSimpFactorization &other)
Copy constructor.
void btran(double *b, double *sol) const
does BTRAN
void updateCurrentRow(const int pivotRow, const int row, const double multiplier, FactorPointers &pointers, int &newNonZeros)
part of pivoting
virtual int updateColumnTranspose(CoinIndexedVector *regionSparse, CoinIndexedVector *regionSparse2) const
Updates one column (BTRAN) from regionSparse2 regionSparse starts as zero and is zero at end Note - i...
int * EtaStarts_
Starts of eta vectors.
int * UrowLengths_
Lengths of the rows of U.
int pivotCandLimit_
maximum number of candidates for pivot
void allocateSomeArrays()
allocates several working arrays
void allocateSpaceForU()
allocates space for U
void clearArrays()
Get rid of all memory.
int * LrowLengths_
Lengths of the rows of L.
int findInColumn(const int column, const int row)
finds a given column in a row
virtual void postProcess(const int *sequence, int *pivotVariable)
Does post processing on valid factorization - putting variables on correct rows.
int lastColInU_
last column in U
void pivoting(const int pivotRow, const int pivotColumn, const double invPivot, FactorPointers &pointers)
does pivoting
int UrowMaxCap_
maximum capacity of Urows
virtual int * permute() const
Returns permute in.
int checkPivot(double saveFromU, double oldPivot) const
Returns accuracy status of replaceColumn returns 0=OK, 1=Probably OK, 2=singular.
int * EtaPosition_
position of Eta vector
void removeColumnFromActSet(const int column, FactorPointers &pointers)
declares a column inactive
int LcolCap_
maximum capacity of L
virtual void getAreas(int numberRows, int numberColumns, int maximumL, int maximumU)
Gets space for a factorization.
void Lxeqb2(double *b1, double *b2) const
same as above but with two rhs
int * LrowInd_
indices in the rows of L
void xUeqb(double *b, double *sol) const
solves x U = b
int LrowSize_
Size of Lrows_;.
int LrowCap_
Capacity of Lrows_.
void Lxeqb(double *b) const
solves L x = b
int * colOfU_
permutation of columns
int * UcolLengths_
Lengths of the columns of U.
CoinSimpFactorization()
Default constructor.
void newEta(int row, int numNewElements)
creates a new eta vector
int findPivotShCol(FactorPointers &pointers, int &r, int &s)
finds a pivot in a shortest column
double * Ucolumns_
U by columns.
int LcolSize_
numbers of elements in L
int * vecLabels_
array of labels (should be initialized to zero)
int * indKeep_
indices of this vector
int UrowEnd_
number of used places in Urows
void ftran2(double *b1, double *sol1, double *b2, double *sol2) const
same as above but with two columns
void Hxeqb2(double *b1, double *b2) const
same as above but with two rhs
pointers used during factorization
FactorPointers(int numRows, int numCols, int *UrowLengths_, int *UcolLengths_)