source: branches/devel-1/ClpPrimalColumnDantzig.cpp @ 36

Last change on this file since 36 was 19, checked in by ladanyi, 18 years ago

reordering Clp

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 5.0 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#if defined(_MSC_VER)
4// Turn off compiler warning about long names
5#  pragma warning(disable:4786)
6#endif
7
8#include <cstdio>
9
10#include "CoinIndexedVector.hpp"
11
12#include "ClpSimplex.hpp"
13#include "ClpPrimalColumnDantzig.hpp"
14#include "ClpFactorization.hpp"
15#include "ClpPackedMatrix.hpp"
16
17//#############################################################################
18// Constructors / Destructor / Assignment
19//#############################################################################
20
21//-------------------------------------------------------------------
22// Default Constructor
23//-------------------------------------------------------------------
24ClpPrimalColumnDantzig::ClpPrimalColumnDantzig () 
25: ClpPrimalColumnPivot()
26{
27  type_=1;
28}
29
30//-------------------------------------------------------------------
31// Copy constructor
32//-------------------------------------------------------------------
33ClpPrimalColumnDantzig::ClpPrimalColumnDantzig (const ClpPrimalColumnDantzig & source) 
34: ClpPrimalColumnPivot(source)
35{ 
36
37}
38
39//-------------------------------------------------------------------
40// Destructor
41//-------------------------------------------------------------------
42ClpPrimalColumnDantzig::~ClpPrimalColumnDantzig ()
43{
44
45}
46
47//----------------------------------------------------------------
48// Assignment operator
49//-------------------------------------------------------------------
50ClpPrimalColumnDantzig &
51ClpPrimalColumnDantzig::operator=(const ClpPrimalColumnDantzig& rhs)
52{
53  if (this != &rhs) {
54    ClpPrimalColumnPivot::operator=(rhs);
55  }
56  return *this;
57}
58
59// Returns pivot column, -1 if none
60int 
61ClpPrimalColumnDantzig::pivotColumn(CoinIndexedVector * updates,
62                                    CoinIndexedVector * spareRow1,
63                                    CoinIndexedVector * spareRow2,
64                                    CoinIndexedVector * spareColumn1,
65                                    CoinIndexedVector * spareColumn2)
66{
67  assert(model_);
68  int iSection,j;
69  int number;
70  int * index;
71  double * updateBy;
72  double * reducedCost;
73  double dj = model_->dualIn();
74
75  bool anyUpdates;
76
77  if (updates->getNumElements()) {
78    // would have to have two goes for devex, three for steepest
79    anyUpdates=true;
80    // add in pivot contribution
81    if (model_->pivotRow()>=0) 
82      updates->add(model_->pivotRow(),-dj);
83  } else if (model_->pivotRow()>=0) {
84    updates->insert(model_->pivotRow(),-dj);
85    anyUpdates=true;
86  } else {
87    // sub flip - nothing to do
88    anyUpdates=false;
89  }
90
91  if (anyUpdates) {
92    model_->factorization()->updateColumnTranspose(spareRow2,updates);
93    // put row of tableau in rowArray and columnArray
94    model_->clpMatrix()->transposeTimes(model_,-1.0,
95                                        updates,spareColumn2,spareColumn1);
96    for (iSection=0;iSection<2;iSection++) {
97     
98      reducedCost=model_->djRegion(iSection);
99     
100      if (!iSection) {
101        number = updates->getNumElements();
102        index = updates->getIndices();
103        updateBy = updates->denseVector();
104      } else {
105        number = spareColumn1->getNumElements();
106        index = spareColumn1->getIndices();
107        updateBy = spareColumn1->denseVector();
108      }
109     
110      for (j=0;j<number;j++) {
111        int iSequence = index[j];
112        double value = reducedCost[iSequence];
113        value -= updateBy[iSequence];
114        updateBy[iSequence]=0.0;
115        reducedCost[iSequence] = value;
116      }
117     
118    }
119    updates->setNumElements(0);
120    spareColumn1->setNumElements(0);
121  }
122
123
124  // update of duals finished - now do pricing
125
126  double largest=model_->currentPrimalTolerance();
127  // we can't really trust infeasibilities if there is primal error
128  if (model_->largestDualError()>1.0e-8)
129    largest *= model_->largestDualError()/1.0e-8;
130
131 
132
133  double bestDj = model_->dualTolerance();
134  int bestSequence=-1;
135
136  double bestFreeDj = model_->dualTolerance();
137  int bestFreeSequence=-1;
138 
139  number = model_->numberRows()+model_->numberColumns();
140  int iSequence;
141  reducedCost=model_->djRegion();
142
143  for (iSequence=0;iSequence<number;iSequence++) {
144    double value = reducedCost[iSequence];
145    if (!model_->fixed(iSequence)) {
146      ClpSimplex::Status status = model_->getStatus(iSequence);
147     
148      switch(status) {
149
150      case ClpSimplex::basic:
151        break;
152      case ClpSimplex::isFree:
153      case ClpSimplex::superBasic:
154        if (fabs(value)>bestFreeDj) { 
155          bestFreeDj = fabs(value);
156          bestFreeSequence = iSequence;
157        }
158        break;
159      case ClpSimplex::atUpperBound:
160        if (value>bestDj) {
161          bestDj = value;
162          bestSequence = iSequence;
163        }
164        break;
165      case ClpSimplex::atLowerBound:
166        if (value<-bestDj) {
167          bestDj = -value;
168          bestSequence = iSequence;
169        }
170      }
171    }
172  }
173  // bias towards free
174  if (bestFreeSequence>=0&&bestFreeDj > 0.1*bestDj) 
175    bestSequence = bestFreeSequence;
176  return bestSequence;
177}
178 
179//-------------------------------------------------------------------
180// Clone
181//-------------------------------------------------------------------
182ClpPrimalColumnPivot * ClpPrimalColumnDantzig::clone(bool CopyData) const
183{
184  if (CopyData) {
185    return new ClpPrimalColumnDantzig(*this);
186  } else {
187    return new ClpPrimalColumnDantzig();
188  }
189}
190
Note: See TracBrowser for help on using the repository browser.