source: trunk/Clp/src/ClpPrimalColumnDantzig.cpp @ 2470

Last change on this file since 2470 was 2385, checked in by unxusr, 8 months ago

formatting

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 6.8 KB
Line 
1/* $Id: ClpPrimalColumnDantzig.cpp 2385 2019-01-06 19:43:06Z 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 "CoinPragma.hpp"
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// Destructor
40//-------------------------------------------------------------------
41ClpPrimalColumnDantzig::~ClpPrimalColumnDantzig()
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 ClpPrimalColumnDantzig::pivotColumn(CoinIndexedVector *updates,
59  CoinIndexedVector * /*spareRow1*/,
60  CoinIndexedVector *spareRow2,
61  CoinIndexedVector *spareColumn1,
62  CoinIndexedVector *spareColumn2)
63{
64  assert(model_);
65  int iSection, j;
66  int number;
67  int *index;
68  double *updateBy;
69  double *reducedCost;
70
71  bool anyUpdates;
72
73  if (updates->getNumElements()) {
74    anyUpdates = true;
75  } else {
76    // sub flip - nothing to do
77    anyUpdates = false;
78  }
79  if (anyUpdates) {
80    model_->factorization()->updateColumnTranspose(spareRow2, updates);
81    // put row of tableau in rowArray and columnArray
82    model_->clpMatrix()->transposeTimes(model_, -1.0,
83      updates, spareColumn2, spareColumn1);
84    for (iSection = 0; iSection < 2; iSection++) {
85
86      reducedCost = model_->djRegion(iSection);
87
88      if (!iSection) {
89        number = updates->getNumElements();
90        index = updates->getIndices();
91        updateBy = updates->denseVector();
92      } else {
93        number = spareColumn1->getNumElements();
94        index = spareColumn1->getIndices();
95        updateBy = spareColumn1->denseVector();
96      }
97
98      for (j = 0; j < number; j++) {
99        int iSequence = index[j];
100        double value = reducedCost[iSequence];
101        value -= updateBy[j];
102        updateBy[j] = 0.0;
103        reducedCost[iSequence] = value;
104      }
105    }
106    updates->setNumElements(0);
107    spareColumn1->setNumElements(0);
108  }
109
110  // update of duals finished - now do pricing
111
112  double largest = model_->currentPrimalTolerance();
113  // we can't really trust infeasibilities if there is primal error
114  if (model_->largestDualError() > 1.0e-8)
115    largest *= model_->largestDualError() / 1.0e-8;
116
117  double bestDj = model_->dualTolerance();
118  int bestSequence = -1;
119
120  double bestFreeDj = model_->dualTolerance();
121  int bestFreeSequence = -1;
122
123  number = model_->numberRows() + model_->numberColumns();
124  int iSequence;
125  reducedCost = model_->djRegion();
126
127#ifndef CLP_PRIMAL_SLACK_MULTIPLIER
128  for (iSequence = 0; iSequence < number; iSequence++) {
129    // check flagged variable
130    if (!model_->flagged(iSequence)) {
131      double value = reducedCost[iSequence];
132      ClpSimplex::Status status = model_->getStatus(iSequence);
133
134      switch (status) {
135
136      case ClpSimplex::basic:
137      case ClpSimplex::isFixed:
138        break;
139      case ClpSimplex::isFree:
140      case ClpSimplex::superBasic:
141        if (fabs(value) > bestFreeDj) {
142          bestFreeDj = fabs(value);
143          bestFreeSequence = iSequence;
144        }
145        break;
146      case ClpSimplex::atUpperBound:
147        if (value > bestDj) {
148          bestDj = value;
149          bestSequence = iSequence;
150        }
151        break;
152      case ClpSimplex::atLowerBound:
153        if (value < -bestDj) {
154          bestDj = -value;
155          bestSequence = iSequence;
156        }
157      }
158    }
159  }
160#else
161  // Columns
162  int numberColumns = model_->numberColumns();
163  for (iSequence = 0; iSequence < numberColumns; iSequence++) {
164    // check flagged variable
165    if (!model_->flagged(iSequence)) {
166      double value = reducedCost[iSequence];
167      ClpSimplex::Status status = model_->getStatus(iSequence);
168
169      switch (status) {
170
171      case ClpSimplex::basic:
172      case ClpSimplex::isFixed:
173        break;
174      case ClpSimplex::isFree:
175      case ClpSimplex::superBasic:
176        if (fabs(value) > bestFreeDj) {
177          bestFreeDj = fabs(value);
178          bestFreeSequence = iSequence;
179        }
180        break;
181      case ClpSimplex::atUpperBound:
182        if (value > bestDj) {
183          bestDj = value;
184          bestSequence = iSequence;
185        }
186        break;
187      case ClpSimplex::atLowerBound:
188        if (value < -bestDj) {
189          bestDj = -value;
190          bestSequence = iSequence;
191        }
192      }
193    }
194  }
195  // Rows
196  for (; iSequence < number; iSequence++) {
197    // check flagged variable
198    if (!model_->flagged(iSequence)) {
199      double value = reducedCost[iSequence] * CLP_PRIMAL_SLACK_MULTIPLIER;
200      ClpSimplex::Status status = model_->getStatus(iSequence);
201
202      switch (status) {
203
204      case ClpSimplex::basic:
205      case ClpSimplex::isFixed:
206        break;
207      case ClpSimplex::isFree:
208      case ClpSimplex::superBasic:
209        if (fabs(value) > bestFreeDj) {
210          bestFreeDj = fabs(value);
211          bestFreeSequence = iSequence;
212        }
213        break;
214      case ClpSimplex::atUpperBound:
215        if (value > bestDj) {
216          bestDj = value;
217          bestSequence = iSequence;
218        }
219        break;
220      case ClpSimplex::atLowerBound:
221        if (value < -bestDj) {
222          bestDj = -value;
223          bestSequence = iSequence;
224        }
225      }
226    }
227  }
228#endif
229  // bias towards free
230  if (bestFreeSequence >= 0 && bestFreeDj > 0.1 * bestDj)
231    bestSequence = bestFreeSequence;
232  return bestSequence;
233}
234
235//-------------------------------------------------------------------
236// Clone
237//-------------------------------------------------------------------
238ClpPrimalColumnPivot *ClpPrimalColumnDantzig::clone(bool CopyData) const
239{
240  if (CopyData) {
241    return new ClpPrimalColumnDantzig(*this);
242  } else {
243    return new ClpPrimalColumnDantzig();
244  }
245}
246
247/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
248*/
Note: See TracBrowser for help on using the repository browser.