1/* $Id: ClpLinearObjective.cpp 1665 2011-01-04 17:55:54Z lou $ */
2// Copyright (C) 2003, 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#include "CoinIndexedVector.hpp"
8#include "ClpFactorization.hpp"
9#include "ClpSimplex.hpp"
10#include "ClpLinearObjective.hpp"
11#include "CoinHelperFunctions.hpp"
12
13//#############################################################################
14// Constructors / Destructor / Assignment
15//#############################################################################
16
17//-------------------------------------------------------------------
18// Default Constructor
19//-------------------------------------------------------------------
20ClpLinearObjective::ClpLinearObjective ()
21 : ClpObjective()
22{
23 type_ = 1;
24 objective_ = NULL;
25 numberColumns_ = 0;
26}
27
28//-------------------------------------------------------------------
29// Useful Constructor
30//-------------------------------------------------------------------
31ClpLinearObjective::ClpLinearObjective (const double * objective ,
32 int numberColumns)
33 : ClpObjective()
34{
35 type_ = 1;
36 numberColumns_ = numberColumns;
37 objective_ = CoinCopyOfArray(objective, numberColumns_, 0.0);
38}
39
40//-------------------------------------------------------------------
41// Copy constructor
42//-------------------------------------------------------------------
43ClpLinearObjective::ClpLinearObjective (const ClpLinearObjective & rhs)
44 : ClpObjective(rhs)
45{
46 numberColumns_ = rhs.numberColumns_;
47 objective_ = CoinCopyOfArray(rhs.objective_, numberColumns_);
48}
49/* Subset constructor. Duplicates are allowed
50 and order is as given.
51*/
52ClpLinearObjective::ClpLinearObjective (const ClpLinearObjective &rhs,
53 int numberColumns,
54 const int * whichColumn)
55 : ClpObjective(rhs)
56{
57 objective_ = NULL;
58 numberColumns_ = 0;
59 if (numberColumns > 0) {
60 // check valid lists
61 int numberBad = 0;
62 int i;
63 for (i = 0; i < numberColumns; i++)
64 if (whichColumn[i] < 0 || whichColumn[i] >= rhs.numberColumns_)
65 numberBad++;
66 if (numberBad)
67 throw CoinError("bad column list", "subset constructor",
68 "ClpLinearObjective");
69 numberColumns_ = numberColumns;
70 objective_ = new double[numberColumns_];
71 for (i = 0; i < numberColumns_; i++)
72 objective_[i] = rhs.objective_[whichColumn[i]];
73 }
74}
75
76
77//-------------------------------------------------------------------
78// Destructor
79//-------------------------------------------------------------------
80ClpLinearObjective::~ClpLinearObjective ()
81{
82 delete [] objective_;
83}
84
85//----------------------------------------------------------------
86// Assignment operator
87//-------------------------------------------------------------------
88ClpLinearObjective &
89ClpLinearObjective::operator=(const ClpLinearObjective& rhs)
90{
91 if (this != &rhs) {
92 ClpObjective::operator=(rhs);
93 numberColumns_ = rhs.numberColumns_;
94 delete [] objective_;
95 objective_ = CoinCopyOfArray(rhs.objective_, numberColumns_);
96 }
97 return *this;
98}
99
100// Returns gradient
101double *
102ClpLinearObjective::gradient(const ClpSimplex * /*model*/,
103 const double * /*solution*/, double & offset,
104 bool /*refresh*/,
105 int /*includeLinear*/)
106{
107 // not sure what to do about scaling
108 //assert (!model);
109 //assert (includeLinear==2); //otherwise need to return all zeros
110 offset = 0.0;
111 return objective_;
112}
113
114/* Returns reduced gradient.Returns an offset (to be added to current one).
115 */
116double
117ClpLinearObjective::reducedGradient(ClpSimplex * model, double * region,
118 bool /*useFeasibleCosts*/)
119{
120 int numberRows = model->numberRows();
121 //work space
122 CoinIndexedVector * workSpace = model->rowArray(0);
123
124 CoinIndexedVector arrayVector;
125 arrayVector.reserve(numberRows + 1);
126
127 int iRow;
128#ifdef CLP_DEBUG
129 workSpace->checkClear();
130#endif
131 double * array = arrayVector.denseVector();
132 int * index = arrayVector.getIndices();
133 int number = 0;
134 const double * cost = model->costRegion();
135 //assert (!useFeasibleCosts);
136 const int * pivotVariable = model->pivotVariable();
137 for (iRow = 0; iRow < numberRows; iRow++) {
138 int iPivot = pivotVariable[iRow];
139 double value = cost[iPivot];
140 if (value) {
141 array[iRow] = value;
142 index[number++] = iRow;
143 }
144 }
145 arrayVector.setNumElements(number);
146
147 int numberColumns = model->numberColumns();
148
149 // Btran basic costs
150 double * work = workSpace->denseVector();
151 model->factorization()->updateColumnTranspose(workSpace, &arrayVector);
152 ClpFillN(work, numberRows, 0.0);
153 // now look at dual solution
154 double * rowReducedCost = region + numberColumns;
155 double * dual = rowReducedCost;
156 double * rowCost = model->costRegion(0);
157 for (iRow = 0; iRow < numberRows; iRow++) {
158 dual[iRow] = array[iRow];
159 }
160 double * dj = region;
161 ClpDisjointCopyN(model->costRegion(1), numberColumns, dj);
162 model->transposeTimes(-1.0, dual, dj);
163 for (iRow = 0; iRow < numberRows; iRow++) {
164 // slack
165 double value = dual[iRow];
166 value += rowCost[iRow];
167 rowReducedCost[iRow] = value;
168 }
169 return 0.0;
170}
171/* Returns step length which gives minimum of objective for
172 solution + theta * change vector up to maximum theta.
173
174 arrays are numberColumns+numberRows
175*/
176double
177ClpLinearObjective::stepLength(ClpSimplex * model,
178 const double * solution,
179 const double * change,
180 double maximumTheta,
181 double & currentObj,
182 double & predictedObj,
183 double & thetaObj)
184{
185 const double * cost = model->costRegion();
186 double delta = 0.0;
187 int numberRows = model->numberRows();
188 int numberColumns = model->numberColumns();
189 currentObj = 0.0;
190 thetaObj = 0.0;
191 for (int iColumn = 0; iColumn < numberColumns + numberRows; iColumn++) {
192 delta += cost[iColumn] * change[iColumn];
193 currentObj += cost[iColumn] * solution[iColumn];
194 }
195 thetaObj = currentObj + delta * maximumTheta;
196 predictedObj = currentObj + delta * maximumTheta;
197 if (delta < 0.0) {
198 return maximumTheta;
199 } else {
200 printf("odd linear direction %g\n", delta);
201 return 0.0;
202 }
203}
204// Return objective value (without any ClpModel offset) (model may be NULL)
205double
206ClpLinearObjective::objectiveValue(const ClpSimplex * model, const double * solution) const
207{
208 const double * cost = objective_;
209 if (model && model->costRegion())
210 cost = model->costRegion();
211 double currentObj = 0.0;
212 for (int iColumn = 0; iColumn < numberColumns_; iColumn++) {
213 currentObj += cost[iColumn] * solution[iColumn];
214 }
215 return currentObj;
216}
217//-------------------------------------------------------------------
218// Clone
219//-------------------------------------------------------------------
220ClpObjective * ClpLinearObjective::clone() const
221{
222 return new ClpLinearObjective(*this);
223}
224/* Subset clone. Duplicates are allowed
225 and order is as given.
226*/
227ClpObjective *
228ClpLinearObjective::subsetClone (int numberColumns,
229 const int * whichColumns) const
230{
231 return new ClpLinearObjective(*this, numberColumns, whichColumns);
232}
233// Resize objective
234void
235ClpLinearObjective::resize(int newNumberColumns)
236{
237 if (numberColumns_ != newNumberColumns) {
238 int i;
239 double * newArray = new double[newNumberColumns];
240 if (objective_)
241 CoinMemcpyN(objective_, CoinMin(newNumberColumns, numberColumns_), newArray);
242 delete [] objective_;
243 objective_ = newArray;
244 for (i = numberColumns_; i < newNumberColumns; i++)
245 objective_[i] = 0.0;
246 numberColumns_ = newNumberColumns;
247 }
248
249}
250// Delete columns in objective
251void
252ClpLinearObjective::deleteSome(int numberToDelete, const int * which)
253{
254 if (objective_) {
255 int i ;
256 char * deleted = new char[numberColumns_];
257 int numberDeleted = 0;
258 CoinZeroN(deleted, numberColumns_);
259 for (i = 0; i < numberToDelete; i++) {
260 int j = which[i];
261 if (j >= 0 && j < numberColumns_ && !deleted[j]) {
262 numberDeleted++;
263 deleted[j] = 1;
264 }
265 }
266 int newNumberColumns = numberColumns_ - numberDeleted;
267 double * newArray = new double[newNumberColumns];
268 int put = 0;
269 for (i = 0; i < numberColumns_; i++) {
270 if (!deleted[i]) {
271 newArray[put++] = objective_[i];
272 }
273 }
274 delete [] objective_;
275 objective_ = newArray;
276 delete [] deleted;
277 numberColumns_ = newNumberColumns;
278 }
279}
280// Scale objective
281void
282ClpLinearObjective::reallyScale(const double * columnScale)
283{
284 for (int iColumn = 0; iColumn < numberColumns_; iColumn++) {
285 objective_[iColumn] *= columnScale[iColumn];
286 }
287}
288