source: trunk/ClpPrimalColumnDantzig.cpp @ 284

Last change on this file since 284 was 259, checked in by forrest, 16 years ago

Hopefully improving primal and presolve

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